Large deviations of connected components in the stochastic block model
arXiv:2003.03415 · doi:10.1103/PhysRevE.102.052108
Abstract
We study the stochastic block model which is often used to model community structures and study community-detection algorithms. We consider the case of two blocks in regard to its largest connected component and largest biconnected component, respectively. We are especially interested in the distributions of their sizes including the tails down to probabilities smaller than . For this purpose we use sophisticated Markov chain Monte Carlo simulations to sample graphs from the stochastic block model ensemble. We use this data to study the large-deviation rate function and conjecture that the large-deviation principle holds. Further we compare the distribution to the well known Erdős-Rényi ensemble, where we notice subtle differences at and above the percolation threshold.
arXiv comment12 pages, 8 figures
References in corpus (27)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- Emergence of scaling in random networks
- Error and attack tolerance of complex networks
- An efficient, multiple range random walk algorithm to calculate the density of states
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Stochastic blockmodels and community structure in networks
- The large deviation approach to statistical mechanics
- Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Fast Algorithm to Calculate Density of States
- Nonparametric Bayesian inference of the microcanonical stochastic block model
- Wang-Landau Algorithm: a Theoretical Analysis of the Saturation of the Error
- Entropy of stochastic blockmodel ensembles
- Large-deviation properties of largest component for random graphs
- Bicomponents and the robustness of networks to failure
- Large-deviation properties of the largest biconnected component for random graphs
- Distribution of diameters for Erdös-Rényi random graphs
- Large-deviation properties of resilience of power grids
- Complete high-precision entropic sampling
- Large-deviations/thermodynamic approach to percolation on the complete graph
- Large Deviations of Convex Hulls of Self-Avoiding Random Walks
- Fragmentation properties of two-dimensional Proximity Graphs considering random failures and targeted attacks