Mixing time of exponential random graphs
From MaRDI portal
Abstract: Exponential random graphs are used extensively in the sociology literature. This model seeks to incorporate in random graphs the notion of reciprocity, that is, the larger than expected number of triangles and other small subgraphs. Sampling from these distributions is crucial for parameter estimation hypothesis testing, and more generally for understanding basic features of the network model itself. In practice sampling is typically carried out using Markov chain Monte Carlo, in particular either the Glauber dynamics or the Metropolis-Hasting procedure. In this paper we characterize the high and low temperature regimes of the exponential random graph model. We establish that in the high temperature regime the mixing time of the Glauber dynamics is , where is the number of vertices in the graph; in contrast, we show that in the low temperature regime the mixing is exponentially slow for any local Markov chain. Our results, moreover, give a rigorous basis for criticisms made of such models. In the high temperature regime, where sampling with MCMC is possible, we show that any finite collection of edges are asymptotically independent; thus, the model does not possess the desired reciprocity property, and is not appreciably different from the ErdH{o}s-R'enyi random graph.
Recommendations
- Mixing time of vertex-weighted exponential random graphs
- A note on perfect simulation for exponential random graph models
- A perfect sampling method for exponential family random graph models
- Perspectives on exponential random graphs
- Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs
Cites work
- Information Theory and Statistical Mechanics
- Logit models and logistic regressions for social networks. I: An introduction to Markov graphs and \(p^*\)
- Markov Graphs
- On Counting Independent Sets in Sparse Graphs
- Pseudo-random graphs
- Quasi-random graphs
- Random graph dynamics
- Randomly coloring graphs with lower bounds on girth and maximum degree
- Statistical mechanics of complex networks
- The Selection of Prior Distributions by Formal Rules
- The Structure and Function of Complex Networks
- The large deviation principle for the Erdős-Rényi random graph
Cited in
(44)- Exponential random graphs behave like mixtures of stochastic block models
- Degeneracy in sparse ERGMs with functions of degrees as sufficient statistics
- Dimension reduction in vertex-weighted exponential random graphs
- Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
- Replica symmetry in upper tails of mean-field hypergraphs
- Estimating and understanding exponential random graph models
- Applications of Stein's method for concentration inequalities
- Ensemble equivalence for dense graphs
- An introduction to large deviations for random graphs
- A note on parallel sampling in Markov graphs
- On the time to identify the nodes in a random graph
- On mixing in pairwise Markov random fields with application to social networks
- Configuring random graph models with fixed degree sequences
- Attracting random walks
- Graphical construction of spatial Gibbs random graphs
- Mixing and concentration by Ricci curvature
- VARIETIES OF INTERGOVERNMENTAL ORGANIZATION MEMBERSHIPS AND STRUCTURAL EFFECTS IN THE WORLD TRADE NETWORK
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- On the mixing time of geographical threshold graphs
- The Kronecker-clique model for higher-order clustering coefficients
- Consistency under sampling of exponential random graph models
- The Mixing Time of the Newman-Watts Small-World Model
- Mixing time of PageRank surfers on sparse random digraphs
- Convergence details about \(k\)-DPP Monte-Carlo sampling for large graphs
- Consistent structure estimation of exponential-family random graph models with block structure
- Concentration and consistency results for canonical and curved exponential-family models of random graphs
- Logarithmic Sobolev inequalities for finite spin systems and applications
- Statistics of the two star ERGM
- Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
- Perspectives on exponential random graphs
- On replica symmetry of large deviations in random graphs
- A novel simulation method for binary discrete exponential families, with application to social networks
- Typical structure of sparse exponential random graph models
- A perfect sampling method for exponential family random graph models
- Mixing time of vertex-weighted exponential random graphs
- A semiparametric Bayesian approach to epidemics, with application to the spread of the coronavirus MERS in South Korea in 2015
- Efficient MCMC for Gibbs random fields using pre-computation
- Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs
- Critical phenomena in exponential random graphs
- Mixing time bounds for graphlet random walks
- Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs
- Weighted exponential random graph models: scope and large network limits
- Sub-critical exponential random graphs: concentration of measure and some applications
- A note on perfect simulation for exponential random graph models
This page was built for publication: Mixing time of exponential random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657693)
