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.
Sampling in exponential random graphs is typically carried out by using Markov chain Monte Carlo methods like the Glauber dynamics or the Metropolis-Hastings procedure. High and low temperature regimes are characterized, and for each regime the order of the mixing time of the sampling procedure is specified in terms of the number of vertices in the graph. The results are used to determine whether or not specific exponential random graph models possess a desired reciprocity property.
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 large deviation principle for the Erdős-Rényi random graph
- The Selection of Prior Distributions by Formal Rules
- The Structure and Function of Complex Networks
Cited in
(47)- Weighted exponential random graph models: scope and large network limits
- Exponential random graphs behave like mixtures of stochastic block models
- Efficient MCMC for Gibbs random fields using pre-computation
- Ensemble equivalence for dense graphs
- Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
- On mixing in pairwise Markov random fields with application to social networks
- The Kronecker-clique model for higher-order clustering coefficients
- Statistics of the two star ERGM
- Convergence details about \(k\)-DPP Monte-Carlo sampling for large graphs
- Dimension reduction in vertex-weighted exponential random graphs
- Logarithmic Sobolev inequalities for finite spin systems and applications
- Concentration and consistency results for canonical and curved exponential-family models of random graphs
- Replica symmetry in upper tails of mean-field hypergraphs
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
- Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs
- Degeneracy in sparse ERGMs with functions of degrees as sufficient statistics
- Consistent structure estimation of exponential-family random graph models with block structure
- Mixing time of vertex-weighted exponential random graphs
- A note on parallel sampling in Markov graphs
- Mixing time bounds for graphlet random walks
- Estimating and understanding exponential random graph models
- Critical phenomena in exponential random graphs
- An introduction to large deviations for random graphs
- On replica symmetry of large deviations in random graphs
- Perspectives on exponential random graphs
- A novel simulation method for binary discrete exponential families, with application to social networks
- Consistency under sampling of exponential random graph models
- On the mixing time of geographical threshold graphs
- Configuring random graph models with fixed degree sequences
- A perfect sampling method for exponential family random graph models
- A semiparametric Bayesian approach to epidemics, with application to the spread of the coronavirus MERS in South Korea in 2015
- A note on perfect simulation for exponential random graph models
- The Mixing Time of the Newman-Watts Small-World Model
- Graphical construction of spatial Gibbs random graphs
- Applications of Stein's method for concentration inequalities
- Mixing time of PageRank surfers on sparse random digraphs
- On the time to identify the nodes in a random graph
- Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs
- VARIETIES OF INTERGOVERNMENTAL ORGANIZATION MEMBERSHIPS AND STRUCTURAL EFFECTS IN THE WORLD TRADE NETWORK
- Sub-critical exponential random graphs: concentration of measure and some applications
- Typical structure of sparse exponential random graph models
- Second-order approximation of exponential random graph models
- Statistics for the triangle density in ERGM and its mean-field approximation
- Sparse random graphs with many triangles
- Attracting random walks
- Mixing and concentration by Ricci curvature
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)
