Scaling and Quality of Modularity Optimization Methods for Graph Clustering

被引:15
作者
Ghosh, Sayan [1 ]
Halappanavar, Mahantesh [1 ]
Tumeo, Antonino [1 ]
Kalyanaraman, Ananth [2 ]
机构
[1] Pacific Northwest Natl Lab, Richland, WA 99352 USA
[2] Washington State Univ, Pullman, WA 99164 USA
来源
2019 IEEE HIGH PERFORMANCE EXTREME COMPUTING CONFERENCE (HPEC) | 2019年
关键词
D O I
10.1109/hpec.2019.8916299
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Real-world graphs exhibit structures known as "communities" or "clusters" consisting of a group of vertices with relatively high connectivity between them, as compared to the rest of the vertices in the network. Graph clustering or community detection is a fundamental graph operation used to analyze real-world graphs occurring in the areas of computational biology, cybersecurity, electrical grids, etc. Similar to other graph algorithms, owing to irregular memory accesses and inherently sequential nature, current algorithms for community detection are challenging to parallelize. However, in order to analyze large networks, it is important to develop scalable parallel implementations of graph clustering that are capable of exploiting the architectural features of modern supercomputers. In response to the 2019 Streaming Graph Challenge, we present quality and performance analysis of our distributed-memory community detection using Vite, which is our distributed memory implementation of the popular Louvain method, on the ALCF Theta supercomputer. Clustering methods such as Louvain that rely on modularity maximization are known to suffer from the resolution limit problem, preventing identification of clusters of certain sizes. Hence, we also include quality analysis of our shared-memory implementation of the Fast-tracking Resistance method, in comparison with Louvain on the challenge datasets. Furthermore, we introduce an edge-balanced graph distribution for our distributed memory implementation, that significantly reduces communication, offering up to 80% improvement in the overall execution time. In addition to performance/quality analysis, we also include details on the power/energy consumption, and memory traffic of the distributed-memory clustering implementation using real-world graphs with over a billion edges.
引用
收藏
页数:6
相关论文
共 14 条
[1]  
[Anonymous], 2006, PHYSICS0608255 ARXIV
[2]  
[Anonymous], 2015, TECH REP
[3]   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,
[4]  
Davis T, 2018, SUITESPARSE MATRIX C
[5]   Resolution limit in community detection [J].
Fortunato, Santo ;
Barthelemy, Marc .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (01) :36-41
[6]   Community detection in graphs [J].
Fortunato, Santo .
PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS, 2010, 486 (3-5) :75-174
[7]   Distributed Louvain Algorithm for Graph Community Detection [J].
Ghosh, Sayan ;
Halappanavar, Mahantesh ;
Tumeo, Antonino ;
Kalyanaraman, Ananth ;
Lu, Hao ;
Chavarria-Miranda, Daniel ;
Khan, Arif ;
Gebremedhin, Assefaw H. .
2018 32ND IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS), 2018, :885-895
[8]   HIERARCHICAL MULTIRESOLUTION METHOD TO OVERCOME THE RESOLUTION LIMIT IN COMPLEX NETWORKS [J].
Granell, Clara ;
Gomez, Sergio ;
Arenas, Alex .
INTERNATIONAL JOURNAL OF BIFURCATION AND CHAOS, 2012, 22 (07)
[9]  
Kao E, 2017, IEEE HIGH PERF EXTR
[10]   Parallel heuristics for scalable community detection [J].
Lu, Hao ;
Halappanavar, Mahantesh ;
Kalyanaraman, Ananth .
PARALLEL COMPUTING, 2015, 47 :19-37