The exponential random graph model is used in sociology to model networks of relationships. They seeks to incorporate into random graphs the notion of reciprocity, that is, a large number of triangles and other small subgraphs. Sampling from these distributions is typically done using MCMC methods. We present results on when these algorithms are efficient as well as other implications for the models.
Joint work with Shankar Bhamidi and Guy Bresler.
Allan Sly is a fourth year graduate student in the Statistics department at U.C. Berkeley. He is from Australia where he got a silver medal at the math olympaid and a master degrees. He is expected to graduate this summer.