Statistical inference of assortative community structures

2020/06/29 by Lizhi Zhang, Li‐Zhi Zhang, Tiago P. Peixoto · 1 citation
Computer Science · Mathematics · Neuroscience · Physics and Astronomy · Psychology · #Artificial intelligence #Assortativity #Cluster analysis #Complex Network Analysis Techniques #Complex network #Computer science #Econometrics #Functional Brain Connectivity Studies #Inference #Machine learning #Mathematics #Mental Health Research Topics #Statistical inference #Statistics #Stochastic block model #Theoretical computer science #cond-mat.dis-nn #cs.SI #physics.soc-ph #stat.ML

paper · pdf · doi:10.1103/physrevresearch.2.043271

published as Phys. Rev. Research 2, 043271 (2020) · 15 pages, 6 figures. Code is available at https://graph-tool.skewed.de and a HOWTO documentation at https://graph-tool.skewed.de/static/doc/demos/inference/inference.html

arxiv created 2020/06/29 · openalex publication_date 2020/11/23 · openalex created_date 2020/12/07 · arxiv updated 2020/12/24 · openalex updated_date 2026/08/05

Abstract

We develop a principled methodology to infer assortative communities in networks based on a nonparametric Bayesian formulation of the planted partition model. We show that this approach succeeds in finding statistically significant assortative modules in networks, unlike alternatives such as modularity maximization, which systematically overfits both in artificial as well as in empirical examples. In addition, we show that our method is not subject to an appreciable resolution limit, and can uncover an arbitrarily large number of communities, as long as there is statistical evidence for them. Our formulation is amenable to model selection procedures, which allow us to compare it to more general approaches based on the stochastic block model, and in this way reveal whether assortativity is in fact the dominating large-scale mixing pattern. We perform this comparison with several empirical networks and identify numerous cases where the network's assortativity is exaggerated by traditional community detection methods, and we show how a more faithful degree of assortativity can be identified.

Citations

• Generalized Communities in Networks
• Community structure in social and biological networks
• Analysis of the structure of complex networks at different resolution levels
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Equation of State Calculations by Fast Computing Machines
• Performance of modularity maximization in practical contexts
• The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations
• Stochastic blockmodels and community structure in networks
• Subnetwork hierarchies of biochemical pathways
• Community detection in graphs
• Monte Carlo sampling methods using Markov chains and their applications

Cited by

• Robust Markov stability for community detection at a scale learned based on the structure