Faster unfolding of communities: speeding up the Louvain algorithm
arXiv:1503.01322 · doi:10.1103/PhysRevE.92.032801
Abstract
Many complex networks exhibit a modular structure of densely connected groups of nodes. Usually, such a modular structure is uncovered by the optimization of some quality function. Although flawed, modularity remains one of the most popular quality functions. The Louvain algorithm was originally developed for optimizing modularity, but has been applied to a variety of methods. As such, speeding up the Louvain algorithm, enables the analysis of larger graphs in a shorter time for various methods. We here suggest to consider moving nodes to a random neighbor community, instead of the best neighbor community. Although incredibly simple, it reduces the theoretical runtime complexity from to in networks with a clear community structure. In benchmark networks, it speeds up the algorithm roughly 2-3 times, while in some real networks it even reaches 10 times faster runtimes. This improvement is due to two factors: (1) a random neighbor is likely to be in a "good" community; and (2) random neighbors are likely to be hubs, helping the convergence. Finally, the performance gain only slightly diminishes the quality, especially for modularity, thus providing a good quality-performance ratio. However, these gains are less pronounced, or even disappear, for some other measures such as significance or surprise.
References in corpus (28)
- Emergence of scaling in random networks
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Finding community structure in networks using the eigenvectors of matrices
- Hierarchical organization of modularity in metabolic networks
- Functional cartography of complex metabolic networks
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Community detection algorithms: a comparative analysis
- Statistical Mechanics of Community Detection
- Structure and tie strengths in mobile communication networks
- Community detection in complex networks using Extremal Optimization
- Finding statistically significant communities in networks
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- Social Structure of Facebook Networks
- Mapping change in large networks
- Line Graphs, Link Partitions and Overlapping Communities
- Limits of modularity maximization in community detection
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Narrow scope for resolution-limit-free community detection
- Local resolution-limit-free Potts model for community detection
- Significant Scales in Community Structure
- Multi-scale community organization of the human structural connectome and its relationship with resting-state functional connectivity
- Detecting communities using asymptotical Surprise
- Surprise maximization reveals the community structure of complex networks
Cited by in corpus (9)
- From Louvain to Leiden: guaranteeing well-connected communities
- Mapping Technology Space by Normalizing Patent Networks
- GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting
- Label propagation for clustering
- Hierarchical Message-Passing Graph Neural Networks
- GVE-Louvain: Fast Louvain Algorithm for Community Detection in Shared Memory Setting
- Scalable Community Detection via Parallel Correlation Clustering
- A Dimensionality-Reduction Strategy to Compute Shortest Paths in Urban Water Networks
- Agglomerative Likelihood Clustering