An improved MCMC algorithm for generating random graphs from constrained distributions
Bibliographic Data
| ID | 6161513 |
|---|---|
| Authors | Trevor Chi-Yuen Tao (Defence Science and Technology Group, corresponding author), TREVOR TAO |
| Year | 2016 |
| Volume | 4 |
| Issue | 1 |
| Pages | 117-139 |
| Publication date | 2016-02-11 |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Network Science (JOURNAL) |
| Journal identifiers | ISSN: 2050-1250 • E-ISSN: 2050-1242 |
| Publisher | Cambridge University Press (PUBLISHER • US) |
| DOI | 10.1017/nws.2015.35 |
| OpenAlex | W2283601946 |
| Language | EN |
| Citations received | 1 |
| References cited | 13 |
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
Algorithm · Combinatorics · Correctness · Graph · Markov chain Monte Carlo · Mathematical optimization · Monte Carlo method · Random graph · Statistics · Transitive relation · Complex Network Analysis Techniques · Computer Science · Markov Chains and Monte Carlo Methods · Mathematics · Stochastic processes and statistical mechanics · Theoretical Computer Science
Social Network Analysis
Exponential Random Graph Models for Social Networks
On random graphs. I.
An Exponential Family of Probability Distributions for Directed Graphs
The Structure and Function of Complex Networks
Markov chain Monte Carlo exact inference for social networks
Simple methods for simulating sociomatrices with given marginal totals
An Educational Application of a Two-Dimensional Sociometric Test
Random directed graph distributions and the triad census in social networks
Statistical Models for Social Networks
| Citations per year | 0.14 |
|---|---|
| Citation span | 2019 - 2019 (1) |
| Highly cited | No |