Systematic assessment of the quality of fit of the stochastic block model for empirical networks

Abstract

We perform a systematic analysis of the quality of fit of the stochastic block model (SBM) for 275 empirical networks spanning a wide range of domains and orders of size magnitude. We employ posterior predictive model checking as a criterion to assess the quality of fit, which involves comparing networks generated by the inferred model with the empirical network, according to a set of network descriptors. We observe that the SBM is capable of providing an accurate description for the majority of networks considered, but falls short of saturating all modeling requirements. In particular, networks possessing a large diameter and slow-mixing random walks tend to be badly described by the SBM. However, contrary to what is often assumed, networks with a high abundance of triangles can be well described by the SBM in many cases. We demonstrate that simple network descriptors can be used to evaluate whether or not the SBM can provide a sufficiently accurate representation, potentially pointing to possible model extensions that can systematically improve the expressiveness of this class of models.

arXiv comment21 pages, 9 figures

References in corpus (42)

• Community structure in social and biological networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• The structure of scientific collaboration networks
• Mixing patterns in networks
• Stochastic blockmodels and community structure in networks
• The Dynamics of Viral Marketing
• Community Structure in Jazz
• High-resolution measurements of face-to-face contact patterns in a primary school
• What's in a crowd? Analysis of face-to-face behavioral networks
• Missing and spurious interactions and the reconstruction of complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Centrality Measures in Spatial Networks of Urban Streets
• Layer aggregation and reducibility of multilayer interconnected networks
• Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
• The Dynamics of Protest Recruitment through an Online Network
• Random Walks on Multiplex Networks
• Emergence of network features from multiplexity
• Percolation on sparse networks
• The Anatomy of a Scientific Rumor
• Dynamic stochastic blockmodels for time-evolving social networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Data on face-to-face contacts in an office building suggests a low-cost vaccination strategy based on community linkers
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Robust network community detection using balanced propagation
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Stacking Models for Nearly Optimal Link Prediction in Complex Networks
• Clique Graphs and Overlapping Communities
• Network histograms and universality of blockmodel approximation
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• A network approach to analyzing highly recombinant malaria parasite genes
• Currency and commodity metabolites: Their identification and relation to the modularity of metabolic networks
• Cover time for random walks on arbitrary complex networks
• Merge-split Markov chain Monte Carlo for community detection
• Disentangling homophily, community structure and triadic closure in networks
• City-wide Analysis of Electronic Health Records Reveals Gender and Age Biases in the Administration of Known Drug-Drug Interactions
• Latent Poisson models for networks with heterogeneous density