Mixing time of exponential random graphs

DOI10.1214/10-AAP740zbMATH Open1238.60011arXiv0812.2265WikidataQ105584278 ScholiaQ105584278MaRDI QIDQ657693FDOQ657693

Allan Sly, Guy Bresler, Shankar Bhamidi

Publication date: 10 January 2012

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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 $Theta(n^{2}logn)$, where $n$ 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.

Full work available at URL: https://arxiv.org/abs/0812.2265

zbMATH Keywords

exponential random graphspath couplingMixing times

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Statistical mechanics of complex networks
• The Structure and Function of Complex Networks
• Logit models and logistic regressions for social networks. I: An introduction to Markov graphs and \(p^*\)
• Markov Graphs
• The Selection of Prior Distributions by Formal Rules
• Information Theory and Statistical Mechanics
• Quasi-random graphs
• On Counting Independent Sets in Sparse Graphs
• The large deviation principle for the Erdős-Rényi random graph
• Randomly coloring graphs with lower bounds on girth and maximum degree

Cited In (39)

• The Kronecker-clique model for higher-order clustering coefficients
• Consistency under sampling of exponential random graph models
• A note on parallel sampling in Markov graphs
• On replica symmetry of large deviations in random graphs
• Sub-critical exponential random graphs: concentration of measure and some applications
• Perspectives on exponential random graphs
• On the mixing time of geographical threshold graphs
• Statistics of the two star ERGM
• Weighted exponential random graph models: scope and large network limits
• Degeneracy in sparse ERGMs with functions of degrees as sufficient statistics
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• The Mixing Time of the Newman-Watts Small-World Model
• Graphical construction of spatial Gibbs random graphs
• Typical structure of sparse exponential random graph models
• Ensemble equivalence for dense graphs
• A semiparametric Bayesian approach to epidemics, with application to the spread of the coronavirus MERS in South Korea in 2015
• Exponential random graphs behave like mixtures of stochastic block models
• A Novel Simulation Method for Binary Discrete Exponential Families, With Application to Social Networks
• Concentration and consistency results for canonical and curved exponential-family models of random graphs
• Dimension reduction in vertex-weighted exponential random graphs
• Consistent structure estimation of exponential-family random graph models with block structure
• Mixing time of vertex-weighted exponential random graphs
• Estimating and understanding exponential random graph models
• An introduction to large deviations for random graphs
• Mixing time of PageRank surfers on sparse random digraphs
• Replica symmetry in upper tails of mean-field hypergraphs
• VARIETIES OF INTERGOVERNMENTAL ORGANIZATION MEMBERSHIPS AND STRUCTURAL EFFECTS IN THE WORLD TRADE NETWORK
• Mixing and concentration by Ricci curvature
• A perfect sampling method for exponential family random graph models
• A note on perfect simulation for Exponential Random Graph Models
• Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
• Configuring Random Graph Models with Fixed Degree Sequences
• Applications of Stein's method for concentration inequalities
• Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
• Efficient MCMC for Gibbs random fields using pre-computation
• Critical phenomena in exponential random graphs
• Logarithmic Sobolev inequalities for finite spin systems and applications
• Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs
• Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs

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)