TY - GEN

T1 - Mixing time of exponential random graphs

AU - Bhamidi, Shankar

AU - Bresler, Guy

AU - Sly, Allan

PY - 2008

Y1 - 2008

N2 - A variety of random graph models have 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 the 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-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 θ;(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 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 Erdos-Rényi random graph.

AB - A variety of random graph models have 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 the 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-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 θ;(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 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 Erdos-Rényi random graph.

KW - Exponential random graphs

KW - Mixing times

KW - Path coupling

KW - Pseudo-random graphs

UR - http://www.scopus.com/inward/record.url?scp=57949105276&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57949105276&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2008.75

DO - 10.1109/FOCS.2008.75

M3 - Conference contribution

AN - SCOPUS:57949105276

SN - 9780769534367

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 803

EP - 812

BT - Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008

T2 - 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008

Y2 - 25 October 2008 through 28 October 2008

ER -