Entropy of stochastic blockmodel ensembles

Abstract

Stochastic blockmodels are generative network models where the vertices are separated into discrete groups, and the probability of an edge existing between two vertices is determined solely by their group membership. In this paper, we derive expressions for the entropy of stochastic blockmodel ensembles. We consider several ensemble variants, including the traditional model as well as the newly introduced degree-corrected version [Karrer et al. Phys. Rev. E 83, 016107 (2011)], which imposes a degree sequence on the vertices, in addition to the block structure. The imposed degree sequence is implemented both as "soft" constraints, where only the expected degrees are imposed, and as "hard" constraints, where they are required to be the same on all samples of the ensemble. We also consider generalizations to multigraphs and directed graphs. We illustrate one of many applications of this measure by directly deriving a log-likelihood function from the entropy expression, and using it to infer latent block structure in observed data. Due to the general nature of the ensembles considered, the method works well for ensembles with intrinsic degree correlations (i.e. with entropic origin) as well as extrinsic degree correlations, which go beyond the block structure.

16 pages, 7 figures

References in corpus (15)

• Statistical physics of social dynamics
• Stochastic blockmodels and community structure in networks
• Finding statistically significant communities in networks
• Adaptive Coevolutionary Networks: A Review
• Missing and spurious interactions and the reconstruction of complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Mixture models and exploratory analysis in networks
• The entropy of network ensembles
• The entropy of randomized network ensembles
• The entropic origin of disassortativity in complex networks
• Role models for complex networks
• Phase transitions in social networks
• Emergence of robustness against noise: A structural phase transition in evolved models of gene regulatory networks
• The behavior of noise-resilient Boolean networks with diverse topologies
• Construction of equilibrium networks with an energy function

Cited by in corpus (66)

• Networks beyond pairwise interactions: structure and dynamics
• Social physics
• The ground truth about metadata and community detection in networks
• The Statistical Physics of Real-World Networks
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• 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
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• On community structure in complex networks: challenges and opportunities
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Bayesian stochastic blockmodeling
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Emergence of overlap in ensembles of spatial multiplexes and statistical mechanics of spatial interacting networks ensembles
• Evolution of robust network topologies: Emergence of central backbones
• Clustering implies geometry in networks
• Extracting Information from Multiplex Networks
• Streaming Graph Challenge: Stochastic Block Partition
• Compensating for population sampling in simulations of epidemic spread on temporal contact networks
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Network structure, metadata and the prediction of missing nodes and annotations
• Entropy distribution and condensation in random networks with a given degree distribution
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Hierarchical community structure in networks
• Exponential random graph models for networks with community structure
• The organization of the interbank network and how ECB unconventional measures affected the e-MID overnight market
• Ensemble nonequivalence in random graphs with modular structure
• Mixing patterns and individual differences in networks
• Group detection in complex networks: An algorithm and comparison of the state of the art
• The Infinite Degree Corrected Stochastic Block Model
• Classical Information Theory of Networks
• Deep Graphs - a general framework to represent and analyze heterogeneous complex systems across scales
• Brain tumour genetic network signatures of survival
• Network mutual information measures for graph similarity
• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• Growing networks of overlapping communities with internal structure
• The role of adjacency matrix degeneration in maximum entropy weighted network models
• Dynamic Hidden-Variable Network Models
• Atomic subgraphs and the statistical mechanics of networks
• Analytical Formulation of the Block-Constrained Configuration Model
• Grand canonical ensembles of sparse networks and Bayesian inference
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• Entropy of labeled versus unlabeled networks
• Finite size analysis of the detectability limit of the stochastic block model
• Regular Decomposition: an information and graph theoretic approach to stochastic block models
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Limits and trade-offs of topological network robustness
• Duality between predictability and reconstructability in complex systems
• Computational limits to the legibility of the imaged human brain
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Entropy of microcanonical finite-graph ensembles
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Importance of initial conditions in the polarization of complex networks
• Consistency between ordering and clustering methods for graphs
• Minimum entropy stochastic block models neglect edge distribution heterogeneity
• Large deviations of connected components in the stochastic block model
• Edge based stochastic block model statistical inference
• Sequential locality of graphs and its hypothesis testing
• Null models for multi-optimized large-scale network structures
• Partition and Code: learning how to compress graphs
• Quantifying metadata relevance to network block structure using description length
• Graph model selection by edge probability sequential inference
• Structural Entropy of the Stochastic Block Models
• Regular Partitions and Their Use in Structural Pattern Recognition