Fast multi-scale detection of overlapping communities using local criteria | Computing Skip to main content
Springer Nature Link
Log in

Fast multi-scale detection of overlapping communities using local criteria

  • Published:
Computing Aims and scope Submit manuscript

Abstract

Many systems can be described using graphs, or networks. Detecting communities in these networks can provide information about the underlying structure and functioning of the original systems. Yet this detection is a complex task and a large amount of work was dedicated to it in the past decade. One important feature is that communities can be found at several scales, or levels of resolution, indicating several levels of organisation. Therefore a graph may have several community structures. Also networks tend to be large and hence require efficient processing. In this work, we present a new algorithm with linear complexity for the fast detection of communities across scales using a local criterion. We exploit the local aspect of the criterion to enable parallel computation and improve the execution speed further. The algorithm is tested against very large generated multi-scale networks and experiments demonstrate its efficiency and accuracy.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The code developed for this work is available for download from http://www.elemartelot.org.

References

  1. Arenas A, Fernandez A, Gomez S (2008) Analysis of the structure of complex networks at different resolution levels. N J Phys 10:053039. doi:10.1088/1367-2630/10/5/053039

    Article  MathSciNet  Google Scholar 

  2. Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):1742–5468

  3. Courtois PJ, Heymans F, Parnas DL (1971) Concurrent control with “readers” and “writers”. Commun ACM 14(10):667–668. doi:10.1145/362759.362813

    Article  Google Scholar 

  4. Fortunato S (2010) Community detection in graphs. Phys Rep 486(3–5):75–174. doi:10.1016/j.physrep.2009.11.002

  5. Fred ALN, Jain AK (2003) Robust data clustering. IEEE Comput Soc Conf Comput Vis Pattern Recognit 2:128–133. doi:10.1109/CVPR.2003.1211462

    Google Scholar 

  6. Huang J, Sun H, Liu Y, Song Q, Weninger T (2011) Towards online multiresolution community detection in large-scale networks. PLoS One 6(8):e23829. doi:10.1371/journal.pone.0023829

  7. Lancichinetti A, Fortunato S (2009) Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E 80(1):016118. doi:10.1103/PhysRevE.80.016118

    Article  Google Scholar 

  8. Lancichinetti A, Fortunato S, Kertész J (2009) Detecting the overlapping and hierarchical community structure in complex networks. N J Phys 11(3):033015

  9. Le Martelot E, Hankin C (2013) Fast multi-scale detection of relevant communities in large scale networks. Comput J. doi:10.1093/comjnl/bxt002

  10. Le Martelot E, Hankin C (2013) Multi-scale community detection using stability optimisation. Int J Web Based Communities (IJWBC) (Special issue on community structure in complex networks) 9(3):323–348. doi:10.1504/IJWBC.2013.054907

  11. Leskovec J, Lang KJ, Dasgupta A, Mahoney MW (2008) Statistical properties of community structure in large social and information networks. In: Proceeding of the 17th international conference on world wide web. WWW ’08. ACM, New York, NY, USA, pp 695–704. doi:10.1145/1367497.1367591

  12. Leskovec J, Lang KJ, Mahoney M (2010) Empirical comparison of algorithms for network community detection. In: Proceedings of the 19th international conference on world wide web. WWW ’10. ACM, New York, NY, USA, pp 631–640. doi:10.1145/1772690.1772755

  13. Newman MEJ (2010) Networks: an introduction, 1st edn. Oxford University Press, Oxford

    Book  Google Scholar 

  14. Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113

    Article  Google Scholar 

  15. Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106. doi:10.1103/PhysRevE.76.036106

    Article  Google Scholar 

  16. Reichardt J, Bornholdt S (2006) Statistical mechanics of community detection. Phys Rev E 74(1 Pt 2):016110

  17. Riedy EJ, Meyerhenke H, Ediger D, Bader DA (2012) Parallel community detection for massive graphs. In: Proceedings of 10th DIMACS implementation challenge—graph partitioning and graph clustering, Atlanta, Georgia

  18. Ronhovde P, Nussinov Z (2010) Local resolution-limit-free Potts model for community detection. Phys Rev E 81(4):046114. doi:10.1103/PhysRevE.81.046114

    Article  Google Scholar 

  19. Simon HA (1962) The architecture of complexity. Proc Am Philos Soc 106(6):467–482

    Google Scholar 

  20. Soman J, Narang A (2011) Fast community detection algorithm with GPUs and multicore architectures. In: Proceedings of parallel distributed processing symposium (IPDPS), 2011 IEEE International, pp 568–579. doi:10.1109/IPDPS.2011.61

Download references

Acknowledgments

This work was conducted as part of the Making Sense(Making sense project: http://www.making-sense.org) project financially supported by EPSRC (project number EP/H023135/1)

Author information

Authors and Affiliations

  1. Department of Computing, Imperial College London, London, SW7 2AZ, UK

    Erwan Le Martelot & Chris Hankin

Authors
  1. Erwan Le Martelot
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chris Hankin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Erwan Le Martelot.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Le Martelot, E., Hankin, C. Fast multi-scale detection of overlapping communities using local criteria. Computing 96, 1011–1027 (2014). https://doi.org/10.1007/s00607-014-0401-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00607-014-0401-1

Keywords

Mathematics Subject Classification

Search

Navigation