IDEAS home Printed from https://ideas.repec.org/a/spr/compst/v37y2022i3d10.1007_s00180-021-01156-6.html
   My bibliography  Save this article

On community structure validation in real networks

Author

Listed:
  • Mirko Signorelli

    (Leiden University)

  • Luisa Cutillo

    (University of Leeds)

Abstract

Community structure is a commonly observed feature of real networks. The term refers to the presence in a network of groups of nodes (communities) that feature high internal connectivity, but are poorly connected between each other. Whereas the issue of community detection has been addressed in several works, the problem of validating a partition of nodes as a good community structure for a real network has received considerably less attention and remains an open issue. We propose a set of indices for community structure validation of network partitions that are based on an hypothesis testing procedure that assesses the distribution of links between and within communities. Using both simulations and real data, we illustrate how the proposed indices can be employed to compare the adequacy of different partitions of nodes as community structures in a given network, to assess whether two networks share the same or similar community structures, and to evaluate the performance of different network clustering algorithms.

Suggested Citation

  • Mirko Signorelli & Luisa Cutillo, 2022. "On community structure validation in real networks," Computational Statistics, Springer, vol. 37(3), pages 1165-1183, July.
    • Handle: RePEc:spr:compst:v:37:y:2022:i:3:d:10.1007_s00180-021-01156-6
    DOI: 10.1007/s00180-021-01156-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00180-021-01156-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00180-021-01156-6?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. M. E. J. Newman & Aaron Clauset, 2016. "Structure and inference in annotated networks," Nature Communications, Nature, vol. 7(1), pages 1-11, September.
    2. Briatte, François, 2016. "Network patterns of legislative collaboration in twenty parliaments," Network Science, Cambridge University Press, vol. 4(2), pages 266-271, June.
    3. Mirko Signorelli & Ernst C. Wit, 2018. "A penalized inference approach to stochastic block modelling of community structure in the Italian Parliament," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 67(2), pages 355-369, February.
    4. Carissimo, Annamaria & Cutillo, Luisa & Feis, Italia De, 2018. "Validation of community robustness," Computational Statistics & Data Analysis, Elsevier, vol. 120(C), pages 1-24.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wang, Shuliang & Dong, Qiqi, 2023. "A multi-source power grid's resilience enhancement strategy based on subnet division and power dispatch," International Journal of Critical Infrastructure Protection, Elsevier, vol. 41(C).

    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. Tian, Yahui & Gel, Yulia R., 2019. "Fusing data depth with complex networks: Community detection with prior information," Computational Statistics & Data Analysis, Elsevier, vol. 139(C), pages 99-116.
    2. Yunpeng Zhao & Qing Pan & Chengan Du, 2019. "Logistic regression augmented community detection for network data with application in identifying autism‐related gene pathways," Biometrics, The International Biometric Society, vol. 75(1), pages 222-234, March.
    3. Zhou, Bin & Yan, Xiao-Yong & Xu, Xiao-Ke & Xu, Xiao-Ting & Wang, Nianxin, 2018. "Evolutionary of online social networks driven by pareto wealth distribution and bidirectional preferential attachment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 507(C), pages 427-434.
    4. Thorben Funke & Till Becker, 2019. "Stochastic block models: A comparison of variants and inference methods," PLOS ONE, Public Library of Science, vol. 14(4), pages 1-40, April.
    5. Jun Liu & Jiangzhou Wang & Binghui Liu, 2020. "Community Detection of Multi-Layer Attributed Networks via Penalized Alternating Factorization," Mathematics, MDPI, vol. 8(2), pages 1-20, February.
    6. Zhou, Bin & Xu, Xiao-Ting & Liu, Jian-Guo & Xu, Xiao-Ke & Wang, Nianxin, 2019. "Information interaction model for the mobile communication networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 525(C), pages 1170-1176.
    7. Chang, Zhenhai & Yin, Xianjun & Jia, Caiyan & Wang, Xiaoyang, 2018. "Mixture models with entropy regularization for community detection in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 339-350.
    8. Fengqin Tang & Chunning Wang & Jinxia Su & Yuanyuan Wang, 2020. "Spectral clustering-based community detection using graph distance and node attributes," Computational Statistics, Springer, vol. 35(1), pages 69-94, March.
    9. Anna Badalyan & Nicolò Ruggeri & Caterina De Bacco, 2024. "Structure and inference in hypergraphs with node attributes," Nature Communications, Nature, vol. 15(1), pages 1-11, December.
    10. Martina Contisciani & Federico Battiston & Caterina De Bacco, 2022. "Inference of hyperedges and overlapping communities in hypergraphs," Nature Communications, Nature, vol. 13(1), pages 1-10, December.
    11. Alireza Ermagun & Nazanin Tajik, 2021. "Recovery patterns and physics of the network," PLOS ONE, Public Library of Science, vol. 16(1), pages 1-20, January.
    12. Junhui Cai & Dan Yang & Wu Zhu & Haipeng Shen & Linda Zhao, 2021. "Network regression and supervised centrality estimation," Papers 2111.12921, arXiv.org.
    13. Ma, Xiaoke & Li, Dongyuan & Tan, Shiyin & Huang, Zhihao, 2019. "Detecting evolving communities in dynamic networks using graph regularized evolutionary nonnegative matrix factorization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 530(C), pages 1-1.
    14. Hric, Darko & Kaski, Kimmo & Kivelä, Mikko, 2018. "Stochastic block model reveals maps of citation patterns and their evolution in time," Journal of Informetrics, Elsevier, vol. 12(3), pages 757-783.
    15. Lucy L. Gao & Daniela Witten & Jacob Bien, 2022. "Testing for association in multiview network data," Biometrics, The International Biometric Society, vol. 78(3), pages 1018-1030, September.
    16. Joseph Crawford & Tijana Milenković, 2018. "ClueNet: Clustering a temporal network based on topological similarity rather than denseness," PLOS ONE, Public Library of Science, vol. 13(5), pages 1-25, May.
    17. Xu, Xiao-Ting & Wang, Nianxin & Bian, Jun & Zhou, Bin, 2019. "Understanding the diversity on power-law-like degree distribution in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 525(C), pages 576-581.
    18. Boris Mirkin & Soroosh Shalileh, 2022. "Community Detection in Feature-Rich Networks Using Data Recovery Approach," Journal of Classification, Springer;The Classification Society, vol. 39(3), pages 432-462, November.
    19. D’Ambra, Pasqua & Vassilevski, Panayot S. & Cutillo, Luisa, 2023. "Extending bootstrap AMG for clustering of attributed graphs," Applied Mathematics and Computation, Elsevier, vol. 447(C).
    20. Sirio Legramanti & Tommaso Rigon & Daniele Durante, 2022. "Bayesian Testing for Exogenous Partition Structures in Stochastic Block Models," Sankhya A: The Indian Journal of Statistics, Springer;Indian Statistical Institute, vol. 84(1), pages 108-126, June.

    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:spr:compst:v:37:y:2022:i:3:d:10.1007_s00180-021-01156-6. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.