Phys. Rev. E 99, 042301 (2019) - Fast consensus clustering in complex networks

Learn about our response to COVID-19, including freely available research and expanded remote access support.

Go Mobile »
Access by University of Bath Library

Fast consensus clustering in complex networks

Aditya Tandon, Aiiad Albeshri, Vijey Thayananthan, Wadee Alhalabi, and Santo Fortunato

Phys. Rev. E 99, 042301 – Published 1 April 2019

Abstract

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.

Received 5 February 2019

DOI:https://doi.org/10.1103/PhysRevE.99.042301

©2019 American Physical Society

Physics Subject Headings (PhySH)

Patterns in complex systems

Interdisciplinary Physics

Authors & Affiliations

Aditya Tandon¹, Aiiad Albeshri², Vijey Thayananthan², Wadee Alhalabi², and Santo Fortunato^3,1

¹School of Informatics, Computing and Engineering, Indiana University, Bloomington, Indiana 47408, USA
²Department of Computer Science, Faculty of Computing and Information Technology, King Abdulaziz University, Jeddah 21589, Kingdom of Saudi Arabia
³Indiana University Network Science Institute (IUNI), Bloomington, Indiana 47408, USA

Article Text

Click to Expand

References

Click to Expand

Issue

Vol. 99, Iss. 4 — April 2019

Reuse & Permissions

Physical Review A•B•C•D - 50 Years

To celebrate 50 years of enduring discoveries, APS is offering 50% off APCs for any manuscript submitted in 2020, published in any of its hybrid journals: PRL, PRA, PRB, PRC, PRD, PRE, PRApplied, PRFluids, and PRMaterials. Learn More »

Ways to Access APS Journal Articles Off-Campus

Many researchers now find themselves working away from their institutions and, thus, may have trouble accessing the Physical Review journals. To address this, we have been improving access via several different mechanisms. See Off-Campus Access to Physical Review for further instructions.

APS and the Physical Review Editorial Office Continue to Support Researchers

COVID-19 has impacted many institutions and organizations around the world, disrupting the progress of research. Through this difficult time APS and the Physical Review editorial office are fully equipped and actively working to support researchers by continuing to carry out all editorial and peer-review functions and publish research in the journals as well as minimizing disruption to journal access.

We appreciate your continued effort and commitment to helping advance science, and allowing us to publish the best physics journals in the world. And we hope you, and your loved ones, are staying safe and healthy.

Images

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$ $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$ $n = 10 000$ , mixing parameter $μ = 0.75$ $μ = 0.75$ , degree exponent $τ_{1} = 2$ $τ_{1} = 2$ , community size exponent $τ_{2} = 3$ $τ_{2} = 3$ , average degree $k_{avg} = 20$ $k_{avg} = 20$ , maximum degree $k_{max} = 50$ $k_{\max} = 50$ , minimum community size $c_{min} = 10$ $c_{\min} = 10$ , maximum community size $c_{max} = 100$ $c_{\max} = 100$ .
Reuse & Permissions
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 $μ$ $μ$ -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$ $n = 10 000$ , degree exponent $τ_{1} = 2$ $τ_{1} = 2$ , community size exponent $τ_{2} = 3$ $τ_{2} = 3$ , average degree $k_{avg} = 20$ $k_{avg} = 20$ , maximum degree $k_{max} = 50$ $k_{\max} = 50$ , minimum community size $c_{min} = 10$ $c_{\min} = 10$ , maximum community size $c_{max} = 100$ $c_{\max} = 100$ .
Reuse & Permissions
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 $τ_{1} = 2$ $τ_{1} = 2$ , community size exponent $τ_{2} = 3$ $τ_{2} = 3$ , average degree $k_{avg} = 20$ $k_{avg} = 20$ , maximum degree $k_{max} = 50$ $k_{\max} = 50$ , minimum community size $c_{min} = 10$ $c_{\min} = 10$ , maximum community size $c_{max} = 50$ $c_{\max} = 50$ for $n = 1000$ $n = 1000$ nodes and $c_{max} = 100$ $c_{\max} = 100$ for $n = 10000$ $n = 10 000$ nodes. For each $μ$ $μ$ -value we generated 20 benchmark configurations, for the LPM and $μ = 0.6$ $μ = 0.6$ (1000 nodes) and $μ = 0.75$ $μ = 0.75$ (10 000 nodes) we used 100 configurations to reduce the error.
Reuse & Permissions
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 $τ_{1} = 2$ $τ_{1} = 2$ , community size exponent $τ_{2} = 3$ $τ_{2} = 3$ , average degree $k_{avg} = 20$ $k_{avg} = 20$ , maximum degree $k_{max} = 50$ $k_{\max} = 50$ , minimum community size $c_{min} = 10$ $c_{\min} = 10$ , maximum community size $c_{max} = 1000$ $c_{\max} = 1000$ .
Reuse & Permissions
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 $τ_{1} = 2$ $τ_{1} = 2$ , community size exponent $τ_{2} = 3$ $τ_{2} = 3$ , average degree $k_{avg} = 20$ $k_{avg} = 20$ , maximum degree $k_{max} = 50$ $k_{\max} = 50$ , minimum community size $c_{min} = 10$ $c_{\min} = 10$ , maximum community size $c_{max} = n / 10$ $c_{\max} = n / 10$ ( $n$ $n$ being the number of nodes of the graph). The mixing parameter $μ$ $μ$ is set to the value 0.3. The error bars indicate the standard deviation of the mean.
Reuse & Permissions

1 of 5

Sign up to receive regular email alerts from Physical Review E

This site uses cookies. To find out more, read our Privacy Policy. I Agree