Parallel heuristics for scalable community detection

被引:125
作者
Lu, Hao [1 ]
Halappanavar, Mahantesh [2 ]
Kalyanaraman, Ananth [1 ]
机构
[1] Washington State Univ, Sch Elect Engn & Comp Sci, Pullman, WA 99164 USA
[2] Pacific NW Natl Lab, Fundamental & Computat Sci Directorate, Richland, WA 99352 USA
关键词
Community detection; Parallel graph heuristics; Graph coloring; Graph clustering; NETWORKS;
D O I
10.1016/j.parco.2015.03.003
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Community detection has become a fundamental operation in numerous graph-theoretic applications. It is used to reveal natural divisions that exist within real world networks without imposing prior size or cardinality constraints on the set of communities. Despite its potential for application, there is only limited support for community detection on large-scale parallel computers, largely owing to the irregular and inherently sequential nature of the underlying heuristics. In this paper, we present parallelization heuristics for fast community detection using the Louvain method as the serial template. The Louvain method is a multi-phase, iterative heuristic for modularity optimization. Originally developed by Blondel etal. (2008), the method has become increasingly popular owing to its ability to detect high modularity community partitions in a fast and memory-efficient manner. However, the method is also inherently sequential, thereby limiting its scalability. Here, we observe certain key properties of this method that present challenges for its parallelization, and consequently propose heuristics that are designed to break the sequential barrier. For evaluation purposes, we implemented our heuristics using OpenMP multithreading, and tested them over real world graphs derived from multiple application domains (e.g., internet, citation, biological). Compared to the serial Louvain implementation, our parallel implementation is able to produce community outputs with a higher modularity for most of the inputs tested, in comparable number or fewer iterations, while providing absolute speedups of up to 16x using 32 threads. (C) 2015 The Authors and Battelle Memorial Institute. Published by Elsevier B.V.
引用
收藏
页码:19 / 37
页数:19
相关论文
共 25 条
[1]  
[Anonymous], 2013, Dynamics On and Of Complex Networks
[2]   Graph coarsening and clustering on the GPU [J].
Auer, B. O. Fagginger ;
Bisseliag, R. H. .
GRAPH PARTITIONING AND GRAPH CLUSTERING, 2013, 588 :223-240
[3]  
Bader David., 2009, SIAM AN10 Minisymposium on Analyzing Massive Real-World Graphs, P12
[4]  
Bader David A, 2012, Graph Partitioning and Graph Clustering
[5]  
Batagelj V., 2002, Generalized cores. CoRR cs.DS/0202039, V5, P1
[6]   Tolerating the community detection resolution limit with edge weighting [J].
Berry, Jonathan W. ;
Hendrickson, Bruce ;
LaViolette, Randall A. ;
Phillips, Cynthia A. .
PHYSICAL REVIEW E, 2011, 83 (05)
[7]   Fast unfolding of communities in large networks [J].
Blondel, Vincent D. ;
Guillaume, Jean-Loup ;
Lambiotte, Renaud ;
Lefebvre, Etienne .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2008,
[8]   On modularity clustering [J].
Brandes, Ulrik ;
Delling, Daniel ;
Gaertler, Marco ;
Goerke, Robert ;
Hoefer, Martin ;
Nikoloski, Zoran ;
Wagner, Dorothea .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2008, 20 (02) :172-188
[9]   Graph coloring algorithms for multi-core and massively multithreaded architectures [J].
Catalyuerek, Uemit V. ;
Feo, John ;
Gebremedhin, Assefaw H. ;
Halappanavar, Mahantesh ;
Pothen, Alex .
PARALLEL COMPUTING, 2012, 38 (10-11) :576-594
[10]  
Clauset A, 2004, PHYS REV E, V70, DOI 10.1103/PhysRevE.70.066111