Statistical inference of assortative community structures

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 a 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.

arXiv comment15 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

References in corpus (32)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Lethality and centrality in protein networks
• Hierarchical organization of modularity in metabolic networks
• Functional cartography of complex metabolic networks
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• The performance of modularity maximization in practical contexts
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Limits of modularity maximization in community detection
• Sustaining the Internet with Hyperbolic Mapping
• Analysis of the structure of complex networks at different resolution levels
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Subnetwork hierarchies of biochemical pathways
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• Identification of core-periphery structure in networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Role models for complex networks
• Generalized communities in networks
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Merge-split Markov chain Monte Carlo for community detection
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Local multiresolution order in community detection

Cited by in corpus (9)

• Social physics
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Multidimensional political polarization in online social networks
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Community detection for directed networks revisited using bimodularity
• Quantifying metadata relevance to network block structure using description length
• Unraveling Media Perspectives: A Comprehensive Methodology Combining Large Language Models, Topic Modeling, Sentiment Analysis, and Ontology Learning to Analyse Media Bias
• Anatomy of Elite and Mass Polarization in Social Networks