A Comparative Analysis of Community Detection Algorithms on Artificial Networks

Abstract

Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms’ computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm’s predicting power and the effective computing time.

Full text

Its licence does not allow us to show the full text. Read it at PubMed Central:

References 46

1. 1.

   Newman M. E. The structure and function of complex networks. SIAM Review 45, 167–256 (2003 ).

   Not in our library

2. 2.

   Boccaletti S., Latora V., Moreno Y., Chavez M. & Hwang D.-U. Complex networks: Structure and dynamics. Physics Reports 424, 175–308 (2006 ).

   Not in our library

3. 3.

   Girvan M. & Newman M. E. Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 7821–7826 (2002 ).

   Not in our library10.1073/pnas.122653799

4. 4.

   Fortunato S. Community detection in graphs. Physics Reports 486, 75–174 (2010 ).

   Not in our library

5. 5.

   Lancichinetti A., Fortunato S. & Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E 78, 046110 (2008 ).

   Not in our library10.1103/physreve.78.046110

6. 6.
   Characterizing the community structure of complex networks. · 2010

   Not checked
7. 7.

   Condon A. & Karp R. M. Algorithms for graph partitioning on the planted partition model. Random Structures and Algorithms 18, 116–140 (2001 ).

   Not in our library

8. 8.

   Danon L., Díaz-Guilera A., Duch J. & Arenas A. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment 2005, P09008 (2005 ).

   Not in our library

9. 9.

   Barabási A.-L. & Albert R. Emergence of scaling in random networks. Science 286, 509–512 (1999 ).

   Not in our library10.1126/science.286.5439.509

10. 10.

    Palla G., Derényi I., Farkas I. & Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005 ).

    Not in our library10.1038/nature03607

11. 11.

    Guimerà R., Danon L., Díaz-Guilera A., Giralt F. & Arenas A. Self-similar community structure in a network of human interactions. Physical Review E 68, 065103 (2003 ).

    Not in our library10.1103/physreve.68.065103

12. 12.

    Clauset A., Newman M. E. & Moore C. Finding community structure in very large networks. Physical Review E 70, 066111 (2004 ).

    Not in our library10.1103/physreve.70.066111

13. 13.

    Lancichinetti A. & Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E 80, 016118 (2009 ).

    Not in our library10.1103/physreve.80.016118

14. 14.

    Orman G. K. & Labatut V. A comparison of community detection algorithms on artificial networks. In Discovery Science 242–256 (Springer, 2009 ).

    Not in our library

15. 15.

    Lancichinetti A. & Fortunato S. Community detection algorithms: a comparative analysis. Physical Review E 80, 056117 (2009 ).

    Not in our library10.1103/physreve.80.056117

16. 16.

    Radicchi F., Castellano C., Cecconi F., Loreto V. & Parisi D. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences 101, 2658–2663 (2004 ).

    Not in our library10.1073/pnas.0400054101

17. 17.

    Peel L. Estimating network parameters for selecting community detection algorithms. In 13th Conference on Information Fusion 1–8 (IEEE, 2010 ).

    Not in our library

18. 18.

    Hric D., Darst R. K. & Fortunato S. Community detection in networks: Structural communities versus ground truth. Physical Review E 90, 062805 (2014 ).

    Not in our library10.1103/physreve.90.062805

19. 19.

    Yang J. & Leskovec J. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42, 181–213 (2015 ).

    Not in our library

20. 20.

    Csardi G. & Nepusz T. The igraph software package for complex network research. InterJournal, Complex Systems 1695, URL http://igraph.org (2006 ).

    Not in our library

21. 21.

    Vinh N. X., Epps J. & Bailey J. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. The Journal of Machine Learning Research 11, 2837–2854 (2010 ).

    Not in our library

22. 22.

    Romano S., Bailey J., Nguyen V. & Verspoor K. Standardized mutual information for clustering comparisons: one step further in adjustment for chance. In Proceedings of the 31st International Conference on Machine Learning (ICML-14), 1143–1151 (2014 ).

    Not in our library

23. 23.

    Zhang P. Evaluating accuracy of community detection using the relative normalized mutual information. Journal of Statistical Mechanics: Theory and Experiment 2015, P11006 (2015 ).

    Not in our library

24. 24.

    Papadopoulos S., Kompatsiaris Y., Vakali A. & Spyridonos P. Community detection in social media. Data Mining and Knowledge Discovery 24, 515–554 (2012 ).

    Not in our library

25. 25.

    Blondel V. D., Guillaume J.-L., Lambiotte R. & Lefebvre E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008, P10008 (2008 ).

    Not in our library

26. 26.

    Fortunato S. & Barthélemy M. Resolution limit in community detection. Proceedings of the National Academy of Sciences 104, 36–41 (2007 ).

    Not in our library10.1073/pnas.0605965104

27. 27.

    Newman M. & Clauset A. Structure and inference in annotated networks. arXiv preprint arXiv:1507.04001 (2015 ).

    Not in our library10.1038/ncomms11863

28. 28.

    Zachary W. W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research 452–473 (1977 ).

    Not in our library

29. 29.

    Danon L., Díaz-Guilera A. & Arenas A. The effect of size heterogeneity on community identification in complex networks. Journal of Statistical Mechanics: Theory and Experiment 2006, P11010 (2006 ).

    Not in our library

30. 30.

    Molloy M. & Reed B. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms 6, 161–180 (1995 ).

    Not in our library

31. 31.

    Bagrow J. P. Evaluating local community methods in networks. Journal of Statistical Mechanics: Theory and Experiment 2008, P05001 (2008 ).

    Not in our library

32. 32.

    Poncela J., Gómez-Gardeñes J., Floria L. M., Sánchez A. & Moreno Y. Complex cooperative networks from evolutionary preferential attachment. PLoS One 3, e2449 (2008 ).

    Not in our library10.1371/journal.pone.0002449

33. 33.

    Orman G. K. & Labatut V. The effect of network realism on community detection algorithms. In International Conference on Advances in Social Networks Analysis and Mining 301–305 (IEEE, 2010 ).

    Not in our library

34. 34.

    Freeman L. C. Centrality in social networks conceptual clarification. Social Networks 1, 215–239 (1979 ).

    Not in our library

35. 35.

    Rosvall M. & Bergstrom C. T. An information-theoretic framework for resolving community structure in complex networks. Proceedings of the National Academy of Sciences 104, 7327–7331 (2007 ).

    Not in our library10.1073/pnas.0611034104

36. 36.

    Rosvall M., Axelsson D. & Bergstrom C. T. The map equation. The European Physical Journal Special Topics 178, 13–23 (2010 ).

    Not in our library

37. 37.

    Mukherjee A., Choudhury M., Peruani F., Ganguly N. & Mitra B. Dynamics On and Of Complex Networks, Volume 2: Applications to Time-Varying Dynamical Systems (Springer Science & Business Media, 2013 ).

    Not in our library

38. 38.

    Raghavan U. N., Albert R. & Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E 76, 036106 (2007 ).

    Not in our library10.1103/physreve.76.036106

39. 39.

    Newman M. E. Finding community structure in networks using the eigenvectors of matrices. Physical Review E 74, 036104 (2006 ).

    Not in our library10.1103/physreve.74.036104

40. 40.

    Xie J. & Szymanski B. K. Community detection using a neighborhood strength driven label propagation algorithm. In Network Science Workshop 188–195 (IEEE, 2011 ).

    Not in our library

Cited by papers we hold 4

• Mapping the Network of Social Cognition Domains in Children With Autism Spectrum Disorder Through Graph Analysis · 2020
  Not checked
• Network Analysis of the Multidimensional Symptom Experience of Oncology · 2019
  No notice
• From Louvain to Leiden: guaranteeing well-connected communities · 2019
  No notice
• Exploratory graph analysis: A new approach for estimating the number of dimensions in psychological research · 2017
  No notice

Reads

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.