Model selection and hypothesis testing for large-scale network models with overlapping groups

Abstract

The effort to understand network systems in increasing detail has resulted in a diversity of methods designed to extract their large-scale structure from data. Unfortunately, many of these methods yield diverging descriptions of the same network, making both the comparison and understanding of their results a difficult challenge. A possible solution to this outstanding issue is to shift the focus away from ad hoc methods and move towards more principled approaches based on statistical inference of generative models. As a result, we face instead the more well-defined task of selecting between competing generative processes, which can be done under a unified probabilistic framework. Here, we consider the comparison between a variety of generative models including features such as degree correction, where nodes with arbitrary degrees can belong to the same group, and community overlap, where nodes are allowed to belong to more than one group. Because such model variants possess an increasing number of parameters, they become prone to overfitting. In this work, we present a method of model selection based on the minimum description length criterion and posterior odds ratios that is capable of fully accounting for the increased degrees of freedom of the larger models, and selects the best one according to the statistical evidence available in the data. In applying this method to many empirical unweighted networks from different fields, we observe that community overlap is very often not supported by statistical evidence and is selected as a better model only for a minority of them. On the other hand, we find that degree correction tends to be almost universally favored by the available data, implying that intrinsic node proprieties (as opposed to group properties) are often an essential ingredient of network formation.

20 pages,7 figures, 1 table

References in corpus (48)

• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Catastrophic cascade of failures in interdependent networks
• The diameter of the world wide web
• Functional cartography of complex metabolic networks
• Multilayer Networks
• Benchmark graphs for testing community detection algorithms
• Community detection algorithms: a comparative analysis
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Mixed membership stochastic blockmodels
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Kronecker Graphs: An Approach to Modeling Networks
• Spectral redemption: clustering sparse networks
• Spectral methods for network community detection and graph partitioning
• Memory in network flows and its effects on spreading dynamics and community detection
• Phase transition in the detection of modules in sparse networks
• An efficient and principled method for detecting communities in networks
• Robustness of community structure in networks
• Graph spectra and the detectability of community structure in networks
• The entropy of network ensembles
• Core-periphery organization of complex networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Learning Latent Block Structure in Weighted Networks
• Uncovering latent structure in valued graphs: A variational approach
• Efficiently inferring community structure in bipartite networks
• Community analysis in social networks
• Friendship networks and social status
• Entropy of stochastic blockmodel ensembles
• Community detection and graph partitioning
• Model Selection for Degree-corrected Block Models
• Multifractal Network Generator
• Trust transitivity in social networks
• Compression of Flow Can Reveal Overlapping-Module Organization in Networks

Cited by in corpus (32)

• Social physics
• A network approach to topic models
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Spectral entropies as information-theoretic tools for complex network comparison
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Modeling sequences and temporal networks with dynamic community structures
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Estimating the number of communities in a network
• Selective Exposure shapes the Facebook News Diet
• Bayesian stochastic blockmodeling
• Nonparametric weighted stochastic block models
• Accurate and scalable social recommendation using mixed-membership stochastic block models
• Delineating Parameter Unidentifiabilities in Complex Models
• Network structure, metadata and the prediction of missing nodes and annotations
• Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
• Community Detection in Degree-Corrected Block Models
• Symptom extraction from the narratives of personal experiences with COVID-19 on Reddit
• Growing networks of overlapping communities with internal structure
• Optimal prediction of decisions and model selection in social dilemmas using block models
• Multiresolution Consensus Clustering in Networks
• Atomic subgraphs and the statistical mechanics of networks
• Analytical Formulation of the Block-Constrained Configuration Model
• Algorithmic complexity of multiplex networks
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Finite size analysis of the detectability limit of the stochastic block model
• The Role of Network Analysis in Industrial and Applied Mathematics
• Probabilistic community detection with unknown number of communities
• A Unified Framework for Community Detection and Network Representation Learning
• Finding community structure using the ordered random graph model
• Fragility of spectral clustering for networks with an overlapping structure