- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Fast consensus clustering in complex networks

Aditya Tandon1, Aiiad Albeshri2, Vijey Thayananthan2, Wadee Alhalabi2, and Santo Fortunato3,1

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

PDF

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

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

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.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (22)

  1. M. A. Porter, J.-P. Onnela, and P. J. Mucha, Communities in networks, Not. Amer. Math. Soc. 56, 1082 (2009).
  2. S. Fortunato, Community detection in graphs, Phys. Rep. 486, 75 (2010).
  3. S. Fortunato and D. Hric, Community detection in networks: A user guide, Phys. Rep. 659, 1 (2016).
  4. A. Lancichinetti and S. Fortunato, Consensus clustering in complex networks, Sci. Rep. 2, 336 (2012).
  5. P. Ronhovde and Z. Nussinov, Multiresolution community detection for megascale networks by information-based replica correlations, Phys. Rev. E 80, 016109 (2009).
  6. O. Sporns, Structure and function of complex brain networks, Dialogues in Clinical Neuroscience 15, 247 (2013).
  7. D. S. Bassett, M. A. Porter, N. F. Wymbs, S. T. Grafton, J. M. Carlson, and P. J. Mucha, Robust detection of dynamic community structure in networks, Chaos 23, 013142 (2013).
  8. A. Tagarelli, A. Amelio, and F. Gullo, Ensemble-based community detection in multilayer networks, Data Min. knowl. Discov. 31, 1506 (2017).
  9. L. GS Jeub, O. Sporns, and S. Fortunato, Multiresolution consensus clustering in networks, Sci. Rep. 8, 3259 (2018).
  10. Valérie Poulin and François Théberge, Ensemble clustering for graphs, International Workshop on Complex Networks and their Applications (Springer, Berlin, 2018), p. 231.
  11. A. A. Hagberg, D. A. Schult, and P. J. Swart, Exploring network structure, dynamics, and function using networkx, in Proceedings of the 7th Python in Science Conference, edited by Gaël Varoquaux, Travis Vaught, and Jarrod Millman (Pasadena, CA, USA, 2008), pp. 11–15.
  12. G. Csardi and T. Nepusz, The igraph software package for complex network research, InterJournal, Complex Systems, 1695 (2006).
  13. http://github.com/adityat/fastconsensus.
  14. A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms, Phys. Rev. E 78, 046110 (2008).
  15. A. Lancichinetti and S. Fortunato, Community detection algorithms: A comparative analysis, Phys. Rev. E 80, 056117 (2009).
  16. A. Lancichinetti, S. Fortunato, and J. Kertesz, Detecting the overlapping and hierarchical community structure in complex networks, New J. Phys. 11, 033015 (2009).
  17. A. Clauset, M. E. J. Newman, and C. Moore, Finding community structure in very large networks, Phys. Rev. E 70, 066111 (2004).
  18. M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004).
  19. V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, Fast unfolding of communities in large networks, J. Stat. Mech. (2008) P10008.
  20. S. Fortunato and M. Barthélemy, Resolution limit in community detection, Proc. Natl. Acad. Sci. USA 104, 36 (2007).
  21. U. N. Raghavan, R. Albert, and S. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E 76, 036106 (2007).
  22. M. Rosvall and C. T. Bergstrom, Maps of random walks on complex networks reveal community structure, Proc. Natl. Acad. Sci. USA 105, 1118 (2008).

Outline

Information

Phys. Rev. E 99, 042301– Published 1 April, 2019
  • Received 5 February 2019
Crossmark - Check for updates button

©2019 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation