IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0018961.html
   My bibliography  Save this article

Finding Statistically Significant Communities in Networks

Author

Listed:
  • Andrea Lancichinetti
  • Filippo Radicchi
  • José J Ramasco
  • Santo Fortunato

Abstract

Community structure is one of the main structural features of networks, revealing both their internal organization and the similarity of their elementary units. Despite the large variety of methods proposed to detect communities in graphs, there is a big need for multi-purpose techniques, able to handle different types of datasets and the subtleties of community structure. In this paper we present OSLOM (Order Statistics Local Optimization Method), the first method capable to detect clusters in networks accounting for edge directions, edge weights, overlapping communities, hierarchies and community dynamics. It is based on the local optimization of a fitness function expressing the statistical significance of clusters with respect to random fluctuations, which is estimated with tools of Extreme and Order Statistics. OSLOM can be used alone or as a refinement procedure of partitions/covers delivered by other techniques. We have also implemented sequential algorithms combining OSLOM with other fast techniques, so that the community structure of very large networks can be uncovered. Our method has a comparable performance as the best existing algorithms on artificial benchmark graphs. Several applications on real networks are shown as well. OSLOM is implemented in a freely available software (http://www.oslom.org), and we believe it will be a valuable tool in the analysis of networks.

Suggested Citation

  • Andrea Lancichinetti & Filippo Radicchi & José J Ramasco & Santo Fortunato, 2011. "Finding Statistically Significant Communities in Networks," PLOS ONE, Public Library of Science, vol. 6(4), pages 1-18, April.
    • Handle: RePEc:plo:pone00:0018961
    DOI: 10.1371/journal.pone.0018961
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0018961
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0018961&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0018961?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Gergely Palla & Imre Derényi & Illés Farkas & Tamás Vicsek, 2005. "Uncovering the overlapping community structure of complex networks in nature and society," Nature, Nature, vol. 435(7043), pages 814-818, June.
    2. Réka Albert & Hawoong Jeong & Albert-László Barabási, 2000. "Error and attack tolerance of complex networks," Nature, Nature, vol. 406(6794), pages 378-382, July.
    3. Aaron Clauset & Cristopher Moore & M. E. J. Newman, 2008. "Hierarchical structure and the prediction of missing links in networks," Nature, Nature, vol. 453(7191), pages 98-101, May.
    4. Ann E. Krause & Kenneth A. Frank & Doran M. Mason & Robert E. Ulanowicz & William W. Taylor, 2003. "Compartments revealed in food-web structure," Nature, Nature, vol. 426(6964), pages 282-285, November.
    5. István A Kovács & Robin Palotai & Máté S Szalay & Peter Csermely, 2010. "Community Landscapes: An Integrative Approach to Determine Overlapping Network Module Hierarchy, Identify Key Nodes and Predict Network Dynamics," PLOS ONE, Public Library of Science, vol. 5(9), pages 1-14, September.
    6. Zhang, Shihua & Wang, Rui-Sheng & Zhang, Xiang-Sun, 2007. "Identification of overlapping community structure in complex networks using fuzzy c-means clustering," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 374(1), pages 483-490.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Selen Onel & Abe Zeid & Sagar Kamarthi, 2011. "The structure and analysis of nanotechnology co-author and citation networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 89(1), pages 119-138, October.
    2. Jordán, Ferenc, 2022. "The network perspective: Vertical connections linking organizational levels," Ecological Modelling, Elsevier, vol. 473(C).
    3. Abdolhosseini-Qomi, Amir Mahdi & Yazdani, Naser & Asadpour, Masoud, 2020. "Overlapping communities and the prediction of missing links in multiplex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 554(C).
    4. Carlo Piccardi, 2011. "Finding and Testing Network Communities by Lumped Markov Chains," PLOS ONE, Public Library of Science, vol. 6(11), pages 1-13, November.
    5. Zhenping Li & Xiang-Sun Zhang & Rui-Sheng Wang & Hongwei Liu & Shihua Zhang, 2013. "Discovering Link Communities in Complex Networks by an Integer Programming Model and a Genetic Algorithm," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-10, December.
    6. Ying Song & Zhiwen Zheng & Yunmei Shi & Bo Wang, 2023. "GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance Networks," Mathematics, MDPI, vol. 11(15), pages 1-16, July.
    7. Zhang, Zhiwei & Wang, Zhenyu, 2015. "Mining overlapping and hierarchical communities in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 421(C), pages 25-33.
    8. Cerqueti, Roy & Ciciretti, Rocco & Dalò, Ambrogio & Nicolosi, Marco, 2022. "A new measure of the resilience for networks of funds with applications to socially responsible investments," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 593(C).
    9. Amulyashree Sridhar & Sharvani GS & AH Manjunatha Reddy & Biplab Bhattacharjee & Kalyan Nagaraj, 2019. "The Eminence of Co-Expressed Ties in Schizophrenia Network Communities," Data, MDPI, vol. 4(4), pages 1-23, November.
    10. Franke, R., 2016. "CHIMERA: Top-down model for hierarchical, overlapping and directed cluster structures in directed and weighted complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 461(C), pages 384-408.
    11. Wu, Jianshe & Wang, Xiaohua & Jiao, Licheng, 2012. "Synchronization on overlapping community network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(3), pages 508-514.
    12. Badie, Reza & Aleahmad, Abolfazl & Asadpour, Masoud & Rahgozar, Maseud, 2013. "An efficient agent-based algorithm for overlapping community detection using nodes’ closeness," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(20), pages 5231-5247.
    13. Fu, Xianghua & Liu, Liandong & Wang, Chao, 2013. "Detection of community overlap according to belief propagation and conflict," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(4), pages 941-952.
    14. Federico Botta & Charo I del Genio, 2017. "Analysis of the communities of an urban mobile phone network," PLOS ONE, Public Library of Science, vol. 12(3), pages 1-14, March.
    15. Xiaofeng Wang & Gongshen Liu & Jianhua Li & Jan P Nees, 2017. "Locating Structural Centers: A Density-Based Clustering Method for Community Detection," PLOS ONE, Public Library of Science, vol. 12(1), pages 1-23, January.
    16. Akshat Singhal & Song Cao & Christopher Churas & Dexter Pratt & Santo Fortunato & Fan Zheng & Trey Ideker, 2020. "Multiscale community detection in Cytoscape," PLOS Computational Biology, Public Library of Science, vol. 16(10), pages 1-10, October.
    17. Ali Kharrazi & Brian D. Fath & Harald Katzmair, 2016. "Advancing Empirical Approaches to the Concept of Resilience: A Critical Examination of Panarchy, Ecological Information, and Statistical Evidence," Sustainability, MDPI, vol. 8(9), pages 1-17, September.
    18. Chen, Duanbing & Shang, Mingsheng & Lv, Zehua & Fu, Yan, 2010. "Detecting overlapping communities of weighted networks via a local algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(19), pages 4177-4187.
    19. Yi-Shan Sung & Dashun Wang & Soundar Kumara, 0. "Uncovering the effect of dominant attributes on community topology: A case of facebook networks," Information Systems Frontiers, Springer, vol. 0, pages 1-12.
    20. Lan Huang & Guishen Wang & Yan Wang & Enrico Blanzieri & Chao Su, 2013. "Link Clustering with Extended Link Similarity and EQ Evaluation Division," PLOS ONE, Public Library of Science, vol. 8(6), pages 1-18, June.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0018961. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.