Faster unfolding of communities: speeding up the Louvain algorithm

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 $\mathcal{O}(m)$ to $\mathcal{O}(n\log ⟨k⟩)$ 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 (14)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Structure and tie strengths in mobile communication networks
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Line Graphs, Link Partitions and Overlapping Communities
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Narrow scope for resolution-limit-free community detection
• 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