Faster unfolding of communities: Speeding up the Louvain algorithm

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 $O\left(m\right)$ to $O(nlog\langle k\rangle )$ 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.

Figure 1

Clique. The original Louvain algorithm considers all communities, which leads to $E\left(t\right)=O\left(n_c^2\right)$ operations for putting all $n_c$ nodes of a clique in a single community. The improvement considers only random neighbors, which takes only $E\left(t\right)=O(n_{c}log{n}_c)$ operations to identify the whole clique as a community. In (a) we show the number of operations in a simulation, with the markers indicating the simulated number of operations, and the solid lines the analytically derived estimates. In (b)–(e) we show the actual time used when optimizing the indicated quality functions for a clique for the different objective functions. The solid lines in (b)–(e) denote best fits to $n_c^2$ and $n_{c}log{n}_c$ in log space.

Figure 2

Network size. We here show the ratio of the time and of the quality (i.e., $\mathcal{H}$) of the uncovered partitions by the original Louvain algorithm and the random neighbor Louvain. The random neighbor Louvain algorithm is 2–3 times faster than the original Louvain algorithm and at some points even faster for clear communities in (a) when using $\mu =0.1$. However, for less clear communities at $\mu =0.8$ as displayed in (b), the optimization of significance and surprise is not faster by using the random neighbor Louvain. The random neighbor Louvain uncovers almost the same quality as the original version for a large part, as shown in (c) and (d). However, especially for surprise, the quality is adversely affected by the random neighbor Louvain for $\mu =0.1$, shown in (c). The results are based on benchmark graph with communities of size $n_c=1000$ and an average degree of $\langle k\rangle =15$.

Figure 3

Effect of community size. Results in (a) show that the speedup ratio increases with the community size for $\mu =0.1$. Surprise and significance find smaller substructures within large communities as seen in (c). This is also when the improvement starts to deteriorate. The results for large communities in (a) and (c) are very similar to the situation when $\mu =0.8$ in (b) and (d), which resembles a random graph more closely. The speedup ratio in (b) corresponds to this: the speedup is rather large for modularity, while it is much lower for surprise and significance. In (e) and (f) we show that heterogeneity in the community sizes nearly do not impact the speedup ratio. In that case we generate LFR benchmark graphs with smallest community size $n_c=10$ and the maximum community size varies from 2 to 10 times as large. We use $n={10}^5$ and $\langle k\rangle =10$ for both benchmarks.

Figure 4

Empirical network results. The random neighbor Louvain usually speeds up the optimization of the objective function for most empirical networks. For the hyperlink network from Google it does not work for any method, while the adolescent health data set poses problems for optimizing CM modularity. The quality remains relatively similar compared to the original, especially for modularity as shown in (b). For significance and surprise the differences are more pronounced.

Figure 5

Performance weighted neighbor sampling. Instead of sampling a neighbor randomly, it is also possible to sample neighbors proportional to the weight. We here test the performance of the unweighted neighbor sampling in (a),(b) and the weighted neighbor sampling in (c),(d). We generate weighted LFR benchmark networks, where the strength of the nodes follows the degree $s_i=k_i^{\beta }$ with $\beta =1.5$ with $\langle k\rangle =10$ and $n={10}^5$. The results for the unweighted neighbor sampling in (a) and (b) are very similar to the results for the weighted neighbor sampling in (c) and (d). Taking into account the weight hence does not improve the random neighbor sampling much.