Scalable Parallel Algorithms and Implementations for Large-scale Graph Analyses

Thesis (Ph.D.), Computer Science, Washington State UniversityScientific fields nowadays have adopted graph analytics into their discovery process. Different graphs have been generated from many different applied domains, such as social sciences, life sciences and business. Many of these application domains have become data-intensive, thereby emphasizing the need for scalability in computation. Addressing scalability is particularly a significant challenge for graph computations due to their inherent irregularity. In this dissertation, we address two graph problems---viz. community detection and balanced graph coloring. Community detection is a well-studied problem that has multiple applications in several domains. Given a G(V,E), the problem of community detection is one of identifying closely-knit subgroups of vertices (``communities''). For the most widely-used formulation, which is one of maximizing a metric called ``modularity''. The Louvain method is one of the most widely used iterative community detection heuristic for modularity optimization, developed by Blondel et al. in 2008. Here, we observe certain key properties of this method that present challenges for its parallelization, and consequently propose heuristics that are designed to break those sequential barriers. Our approach, which we call Grappolo, demonstrates scaling on standard multicore platforms and emerging manycore platforms. The other problem we address is balanced graph coloring. The goal for graph coloring is to assign colors to vertices such that no two adjacent vertices are assigned the same color (distance-1 coloring). Coloring can be used to identify independent tasks in parallel computing. Classical coloring heuristics attempt to reduce the number of colors used but the colorings generated in practice tend to have a skewed distribution in size, which could negatively impact parallel performance. Here, we propose multiple classes of heuristics to generate distance-1 colorings and partial distance-2 colorings (for bipartite graphs) with the dual objective of minimizing the number of color classes while ensuring that the color classes are balanced in size. We demonstrate the effectiveness of these heuristics on improving the performance of parallel community detection. Different heuristics and design techniques presented in this dissertation can potentially be adapted into the broader context of parallelizing other graph operations that also have a similar irregular, and/or iterative structure to their computation.Washington State University, Computer Scienc