Mixing time of exponential random graphs

Shankar Bhamidi, Guy Bresler, Allan Sly

Research output: Contribution to journalArticlepeer-review

53 Scopus citations

Abstract

A variety of random graph models has been developed in recent years to study a range of problems on networks, driven by the wide availability of data from many social, telecommunication, biochemical and other networks. A key model, extensively used in sociology literature, is the exponential random graph model. 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-Hastings 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 Θ(n2 log n), 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 Markov chain Monte Carlo is possible, we show that any finite collection of edges is asymptotically independent; thus, the model does not possess the desired reciprocity property and is not appreciably different from the Erd?os-Rényi random graph.

Original languageEnglish (US)
Pages (from-to)2146-2170
Number of pages25
JournalAnnals of Applied Probability
Volume21
Issue number6
DOIs
StatePublished - Dec 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Exponential random graphs
  • Mixing times
  • Path coupling

Fingerprint

Dive into the research topics of 'Mixing time of exponential random graphs'. Together they form a unique fingerprint.

Cite this