Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-27T22:08:38.377Z Has data issue: false hasContentIssue false
  • English
  • Français

An improved MCMC algorithm for generating random graphs from constrained distributions

Published online by Cambridge University Press:  11 February 2016

TREVOR TAO
TREVOR TAO*
Affiliation:
Defence Science and Technology Organisation, Edinburgh, South Australia 5111, Australia (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the problem of generating uniformly random graphs from a constrained distribution. A graph is valid if it obeys certain constraints such as a given number of nodes, edges, k-stars or degree sequence, and each graph must occur with equal probability. A typical application is to confirm the correctness of a model by repeated sampling and comparing statistical properties against empirical data. Markov Chain Monte Carlo (MCMC) algorithms are often used, but have certain difficulties such as the inability to search the space of all possible valid graphs. We propose an improved algorithm which overcomes these difficulties. Although each individual iteration of the MCMC algorithm takes longer, we obtain better coverage of the search space in the same amount of time. This leads to better estimates of various quantities such as the expected number of transitive triads given the constraints. The algorithm should be of general interest with many possible applications, including the world wide web, biological, and social networks.

Keywords

MCMCadjacency matrixgraph theoryconstrained distributionsocial networktriad census
Type
Research Article
Information
Network Science , Volume 4 , Issue 1 , March 2016 , pp. 117 - 139
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Blitzstein, J., & Diaconis, P. (2010). A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Mathematics, 6 (4), 489–522.Google Scholar
Chung, F., & Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6 (2), 125–145.Google Scholar
Erdös, P., & Rényi, A. (1959). On random graphs. Publicationes Mathematicae, 6, 290–297.CrossRefGoogle Scholar
Erdös, P. L., Miklós, I., & Soukup, L. (2013). Towards random uniform sampling of bipartite graphs with given degree sequence. Electronic Journal of Combinatorics, 20 (1).Google Scholar
Holland, P., & Leinhardt, S. (1981). An exponential family of probability distributions for directed graphs. Journal of the American Statistical Association, 76 (373), 33–50.Google Scholar
Lusher, D., Koskinen, J., & Robins, G. (eds). (2012). Exponential random graph models for social networks, theory, methods, and applications. New York, NY, USA: Cambridge University Press.Google Scholar
McDonald, J., Smith, P., & Forster, J. (2007). Markov chain Monte Carlo exact inference for social networks. Social Networks, 29 (1), 127–136.Google Scholar
McKinney, J. C. (1948). An educational application of a two-dimensional sociometric test. Sociometry, 11 (4), 358–367.Google Scholar
Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review, 45 (2), 167–256.CrossRefGoogle Scholar
Rabiner, L. R., & Juang, B. H. (1986). An introduction to hidden Markov models. IEEE ASSP Magazine, 3 (1), 4–16.Google Scholar
Rao, A., Jana, R., & Bandyopadhyay, S. (1996). A Markov chain Monte Carlo method for generating random 0-1 matrices with given marginals. Sankhya, Series A, 58 (2), 225–242.Google Scholar
Roberts, J. (2000). Simple methods for simulating sociomatrices with given marginal totals. Social Networks, 22 (3), 273–283.Google Scholar
Rubinstein, R. Y., Ridder, A., & Vaisman, R. (2013). Introduction to Monte Carlo methods (pp. 1–5). Hoboken, NJ, USA: John Wiley and Sons, Inc.Google Scholar
Snijders, T. (2011). Statistical models for social networks. Annual Review of Sociology, 37, 131–53.Google Scholar
Wasserman, S., & Faust, K. (1994). Social network analysis: methods and applications. Cambridge, UK: Cambridge University Press.CrossRefGoogle Scholar
Wasserman, S. S. (1977). Random directed graph distributions and the triad census in social networks. Journal of Mathematical Sociology, 5 (1), 61–86.Google Scholar