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. 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.
    2. 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.
    3. 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.
    4. 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.
    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. 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.
    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. 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.
    2. 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.
    3. Jordán, Ferenc, 2022. "The network perspective: Vertical connections linking organizational levels," Ecological Modelling, Elsevier, vol. 473(C).
    4. 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.
    5. 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).
    6. Wu, Jianshe & Lu, Rui & Jiao, Licheng & Liu, Fang & Yu, Xin & Wang, Da & Sun, Bo, 2013. "Phase transition model for community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(6), pages 1287-1301.
    7. Martin Rosvall & Carl T Bergstrom, 2011. "Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems," PLOS ONE, Public Library of Science, vol. 6(4), pages 1-10, April.
    8. Wang, Wensheng & Karimi, Faezeh & Khalilpour, Kaveh & Green, David & Varvarigos, Manos, 2023. "Robustness analysis of electricity networks against failure or attack: The case of the Australian National Electricity Market (NEM)," International Journal of Critical Infrastructure Protection, Elsevier, vol. 41(C).
    9. 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.
    10. 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.
    11. Ma, Xiaoke & Gao, Lin & Yong, Xuerong & Fu, Lidong, 2010. "Semi-supervised clustering algorithm for community structure detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(1), pages 187-197.
    12. Chungmok Lee & Minh Pham & Myong K. Jeong & Dohyun Kim & Dennis K. J. Lin & Wanpracha Art Chavalitwongse, 2015. "A Network Structural Approach to the Link Prediction Problem," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 249-267, May.
    13. 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).
    14. Liu, Ji & Deng, Guishi, 2009. "Link prediction in a user–object network based on time-weighted resource allocation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(17), pages 3643-3650.
    15. 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.
    16. Weihua Zhan & Jihong Guan & Zhongzhi Zhang, 2017. "A New Method for Extracting the Hierarchical Organization of Networks," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 16(05), pages 1359-1385, September.
    17. Kininmonth, Stuart & van Oppen, Madeleine J.H. & Possingham, Hugh P., 2010. "Determining the community structure of the coral Seriatopora hystrix from hydrodynamic and genetic networks," Ecological Modelling, Elsevier, vol. 221(24), pages 2870-2880.
    18. 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.
    19. Li, Wenyuan & Lin, Yongjing & Liu, Ying, 2007. "The structure of weighted small-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 376(C), pages 708-718.
    20. 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.

    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.