More Web Proxy on the site http://driver.im/

research-article

Public Access

Prune the Unnecessary: Parallel Pull-Push Louvain Algorithms with Automatic Edge Pruning

Authors:

Jesmin Jahan Tithi,

Andrzej Stasiak,

Sriram Aananthakrishnan,

Fabrizio PetriniAuthors Info & Claims

ICPP '20: Proceedings of the 49th International Conference on Parallel Processing

Article No.: 44, Pages 1 - 11

https://doi.org/10.1145/3404397.3404455

Published: 17 August 2020 Publication History

All formats PDF

Abstract

Community detection algorithms try to identify the underlying community structure (i.e., clearly distinguishable closely interacting groups of vertices) in a graph representing complex systems such as social networks, protein-protein interaction networks, and the World-Wide-Web. The Louvain algorithm iteratively moves vertices from one community to another to construct disjoint sets of vertices to form communities such that the vertices within the same community have more edges within themselves compared to their connections to the vertices outside the community. A property of the Louvain algorithm is that the number of vertex moves drops significantly just after the first few iterations because the community-membership also stabilizes quickly. In this paper, we present a parallel pull-and-push Louvain algorithm that exploits this property to prune unnecessary edge explorations without sacrificing the quality of the solution. We present a collection of parallel Louvain algorithms that prune many edges and vertices, speeding up convergence by an order of magnitude over the previously best-known implementation of the Louvain algorithm from Grappolo, while producing similar or better results.

References

[1]

[n.d.]. https://scikit-learn.org/stable/modules/generated/sklearn.metrics.normalized_mutual_info_score.html.

[2]

Sanjukta Bhowmick and Sriram Srinivasan. 2013. A template for parallelizing the louvain method for modularity maximization. In Dynamics On and Of Complex Networks, Volume 2. Springer, 111–124.

[3]

Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008, 10(2008), P10008.

[4]

Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Görke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. 2006. Maximizing modularity is hard. arXiv preprint physics/0608255(2006).

[5]

Jingchun Chen and Bo Yuan. 2006. Detecting functional modules in the yeast protein–protein interaction network. Bioinformatics 22, 18 (2006), 2283–2290.

Digital Library

[6]

Yon Dourisboure, Filippo Geraci, and Marco Pellegrini. 2007. Extraction and classification of dense communities in the web. In Proceedings of the 16th international conference on World Wide Web. ACM, 461–470.

Digital Library

[7]

Karthi Duraisamy, Hao Lu, Partha Pratim Pande, and Aananth Kalyanaraman. 2017. Accelerating graph community detection with approximate updates via an energy-efficient NoC. In 2017 54th ACM/EDAC/IEEE Design Automation Conference (DAC). IEEE, 1–6.

Digital Library

[8]

Santo Fortunato. 2010. Community detection in graphs. Physics reports 486(2010).

[9]

Sayan Ghosh, Mahantesh Halappanavar, Antonino Tumeo, Ananth Kalyanaraman, Hao Lu, Daniel Chavarria-Miranda, Arif Khan, and Assefaw Gebremedhin. 2018. Distributed louvain algorithm for graph community detection. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE.

[10]

Hao Lu, Mahantesh Halappanavar, and Ananth Kalyanaraman. 2015. Parallel heuristics for scalable community detection. Parallel Comput. 47(2015), 19–37.

Digital Library

[11]

Mark EJ Newman. 2004. Fast algorithm for detecting community structure in networks. Physical review E 69, 6 (2004), 066133.

[12]

Naoto Ozaki, Hiroshi Tezuka, and Mary Inaba. 2016. A Simple Acceleration Method for the Louvain Algorithm. International Journal of Computer and Electrical Engineering 8, 3(2016), 207.

[13]

Ajay Panyala, Omer Subasi, Mahantesh Halappanavar, Ananth Kalyanaraman, Daniel Chavarria-Miranda, and Sriram Krishnamoorthy. 2017. Approximate computing techniques for iterative graph algorithms. In 2017 IEEE 24th International Conference on High Performance Computing (HiPC). IEEE, 23–32.

[14]

Xinyu Que, Fabio Checconi, Fabrizio Petrini, and John A Gunnels. 2015. Scalable community detection with the louvain algorithm. In Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International. IEEE, 28–37.

Digital Library

[15]

Alexander W Rives and Timothy Galitski. 2003. Modular organization of cellular networks. Proceedings of the National Academy of Sciences 100, 3 (2003).

[16]

Vincent A Traag. 2015. Faster unfolding of communities: Speeding up the Louvain algorithm. Physical Review E 92, 3 (2015), 032801.

[17]

Barry Wellman. 2008. The development of social network analysis: A study in the sociology of science. Contemporary Sociology 37, 3 (2008), 221.

[18]

Jianping Zeng and Hongfeng Yu. 2018. A Scalable Distributed Louvain Algorithm for Large-Scale Graph Community Detection. In 2018 IEEE International Conference on Cluster Computing (CLUSTER). IEEE, 268–278.

[19]

Ziqiao Zhang, Peng Pu, Dingding Han, and Ming Tang. 2018. Self-adaptive Louvain algorithm: Fast and stable community detection algorithm based on the principle of small probability event. Physica A: Statistical Mechanics and its Applications 506 (2018), 975–986.

Cited By

Blondel VGuillaume JLambiotte R(2024)Fast unfolding of communities in large networks: 15 years laterJournal of Statistical Mechanics: Theory and Experiment10.1088/1742-5468/ad61392024:10(10R001)Online publication date: 28-Oct-2024
https://doi.org/10.1088/1742-5468/ad6139
Adiletta MTithi JFarsarakis EGerogiannis GAdolf RBenke RKashyap SHsia SLakhotia KPetrini FWei GBrooks D(2023) Characterizing the Scalability of Graph Convolutional Networks on Intel ® PIUMA 2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS57527.2023.00025(168-177)Online publication date: Apr-2023
https://doi.org/10.1109/ISPASS57527.2023.00025
Liu XLumsdaine AHalappanavar MBarker KGebremedhin A(2022)Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental AnalysisACM Journal of Experimental Algorithmics10.1145/356459327(1-31)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1145/3564593
Show More Cited By

Recommendations

k-truss network community detection
ASONAM '20: Proceedings of the 12th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

We review the k-truss algorithm for community detection in networks. The k-truss is an efficient clustering algorithm that holds advantageous properties for many network applications. In this paper, we compare the k-truss performance against other, more ...
Isolate Sets Based Parallel Louvain Method for Community Detection
Abstract
Community detection is a vital task in many fields, such as social networks and financial analysis, to name a few. The Louvain method, the main workhorse of community detection, is a popular heuristic method. To apply it to large-scale graph ...
A Case Study Comparing Twitter Communities Detected by the Louvain and Leiden Algorithms During the 2022 War in Ukraine
WWW '24: Companion Proceedings of the ACM Web Conference 2024

This paper presents a case study regarding a comparative examination of the Louvain and Leiden community detection algorithms. The case study was conducted on a real-world communication network consisting of 3,222,623 nodes and 27,423,553 edges. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICPP '20: Proceedings of the 49th International Conference on Parallel Processing

August 2020

844 pages

ISBN:9781450388160

DOI:10.1145/3404397

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 August 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Defense Sciences Office, DARPA

Conference

ICPP '20

ICPP '20: 49th International Conference on Parallel Processing

August 17 - 20, 2020

AB, Edmonton, Canada

Acceptance Rates

Overall Acceptance Rate 91 of 313 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
277
Total Downloads

Downloads (Last 12 months)124
Downloads (Last 6 weeks)21

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Blondel VGuillaume JLambiotte R(2024)Fast unfolding of communities in large networks: 15 years laterJournal of Statistical Mechanics: Theory and Experiment10.1088/1742-5468/ad61392024:10(10R001)Online publication date: 28-Oct-2024
https://doi.org/10.1088/1742-5468/ad6139
Adiletta MTithi JFarsarakis EGerogiannis GAdolf RBenke RKashyap SHsia SLakhotia KPetrini FWei GBrooks D(2023) Characterizing the Scalability of Graph Convolutional Networks on Intel ® PIUMA 2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS57527.2023.00025(168-177)Online publication date: Apr-2023
https://doi.org/10.1109/ISPASS57527.2023.00025
Liu XLumsdaine AHalappanavar MBarker KGebremedhin A(2022)Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental AnalysisACM Journal of Experimental Algorithmics10.1145/356459327(1-31)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1145/3564593
Gawande NGhosh SHalappanavar MTumeo AKalyanaraman A(2022)Towards scaling community detection on distributed-memory heterogeneous systemsParallel Computing10.1016/j.parco.2022.102898111:COnline publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.parco.2022.102898
Sattar NArifuzzaman S(2022)Scalable distributed Louvain algorithm for community detection in large graphsThe Journal of Supercomputing10.1007/s11227-021-04224-278:7(10275-10309)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s11227-021-04224-2
Akyildiz TAlabsi Aljundi AKaya K(2020)Understanding Coarsening for Embedding Large-Scale Graphs2020 IEEE International Conference on Big Data (Big Data)10.1109/BigData50022.2020.9377898(2937-2946)Online publication date: 10-Dec-2020
https://doi.org/10.1109/BigData50022.2020.9377898

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents