Fast consensus clustering in complex networks

Algorithms for community detection are usually stochastic, leading to different partitions for different choices of random seeds. Consensus clustering has proven to be an effective technique to derive more stable and accurate partitions than the ones obtained by the direct application of the algorithm. However, the procedure requires the calculation of the consensus matrix, which can be quite dense if (some of) the clusters of the input partitions are large. Consequently, the complexity can get dangerously close to quadratic, which makes the technique inapplicable on large graphs. Here, we present a fast variant of consensus clustering, which calculates the consensus matrix only on the links of the original graph and on a comparable number of additional node pairs, suitably chosen. This brings the complexity down to linear, while the performance remains comparable as the full technique. Therefore, our fast consensus clustering procedure can be applied on networks with millions of nodes and links.

Figure 1

Importance of triadic closure in the construction of a sparse consensus matrix. The accuracy of the resulting partition rapidly increases as we compute additional elements of the consensus matrix, by randomly closing triads formed by the (weighted) links of the initial matrix, after thresholding. Closing a modest number of triads suffices to outperform the direct application of the clustering method (here the Louvain algorithm), whose accuracy is indicated by the horizontal yellow line. The accuracy quickly climbs up to that of LF consensus (magenta line) and reaches about 0.87 for about $m$ closed triads, remaining remarkably stable thereafter. The thickness of the blue line indicates the standard error of the mean. For the LFR benchmark graph used in this test we chose the following parameters: number of nodes $n=10000$, mixing parameter $\mu =0.75$, degree exponent ${\tau }_1=2$, community size exponent ${\tau }_2=3$, average degree $k_{\mathrm{avg}}=20$, maximum degree $k_{\max }=50$, minimum community size $c_{\min }=10$, maximum community size $c_{\max }=100$.

Figure 2

Stability of consensus clustering partitions. Average value of the NMI for all pairs of partitions returned by our technique, compared with the corresponding average score for the input partitions. The thickness of the lines indicate the standard error of the average. The test uses the Louvain algorithm on LFR benchmarks. When communities are easy to find (low to intermediate $\mu$-values), partitions are essentially identical in both cases and the pairwise NMI is equal to one. Interestingly, for our consensus clustering procedure the resulting partitions are very similar even when communities are harder to find, whereas the input partitions become less and less similar to each other. The parameters used to generate the LFR benchmark graphs are: number of nodes $n=10000$, degree exponent ${\tau }_1=2$, community size exponent ${\tau }_2=3$, average degree $k_{\mathrm{avg}}=20$, maximum degree $k_{\max }=50$, minimum community size $c_{\min }=10$, maximum community size $c_{\max }=100$.

Figure 3

Performance of fast consensus clustering on LFR benchmark graphs with 1000 (left) and 10 000 (right) nodes. The algorithms are fast greedy modularity maximization by Clauset, Newman, and Moore [CNM, (a) and (b)], Louvain [(c) and (d)], and the label propagation method [LPM, (e) and (f)]. The three curves in each plot correspond to the performance of the community detection method (brown), LF consensus (magenta), and fast consensus (blue). The thickness of the lines indicates the standard error of the mean. The parameters used to generate the LPM benchmark graphs are: degree exponent ${\tau }_1=2$, community size exponent ${\tau }_2=3$, average degree $k_{\mathrm{avg}}=20$, maximum degree $k_{\max }=50$, minimum community size $c_{\min }=10$, maximum community size $c_{\max }=50$ for $n=1000$ nodes and $c_{\max }=100$ for $n=10000$ nodes. For each $\mu$-value we generated 20 benchmark configurations, for the LPM and $\mu =0.6$ (1000 nodes) and $\mu =0.75$ (10 000 nodes) we used 100 configurations to reduce the error.

Figure 4

Fast consensus clustering on large networks. Comparative analysis of the performance of the Louvain algorithm, with and without consensus clustering, on LFR benchmark graphs with 100 000 nodes. The thickness of the lines indicates the standard error of the mean. The other parameters to construct the graphs are: degree exponent ${\tau }_1=2$, community size exponent ${\tau }_2=3$, average degree $k_{\mathrm{avg}}=20$, maximum degree $k_{\max }=50$, minimum community size $c_{\min }=10$, maximum community size $c_{\max }=1000$.

Figure 5

Time complexity of LF consensus and our fast consensus clustering procedure. The clustering algorithm is Louvain, the tests were done on LFR benchmark graphs with the following parameters: degree exponent ${\tau }_1=2$, community size exponent ${\tau }_2=3$, average degree $k_{\mathrm{avg}}=20$, maximum degree $k_{\max }=50$, minimum community size $c_{\min }=10$, maximum community size $c_{\max }=n/10$ ($n$ being the number of nodes of the graph). The mixing parameter $\mu$ is set to the value 0.3. The error bars indicate the standard deviation of the mean.