Are we there yet? When to stop a Markov chain while generating random graphs

Jaideep Ray, Ali Pinar, C. Seshadhri

Introduction

Generating random graphs that preserve the complex structural properties of real-world networks—such as power grids or social circles—is a cornerstone of network science. However, a fundamental challenge remains: how many iterations must a Markov Chain Monte Carlo (MCMC) sampler run before the resulting graph is truly "random" and independent of its initial state? Researchers at Sandia National Laboratories have addressed this "Stopping Problem" by introducing practical methods to determine convergence.

The MCMC Rewiring Process

To generate an ensemble of graphs sharing a specific degree distribution, researchers typically use an edge-swapping MCMC algorithm. Starting with an observed graph, the algorithm iteratively "rewires" it to explore the space of possible configurations.

The three-step edge-swapping process used in MCMC graph rewiring.

As shown in the figure above, the process involves picking two edges and swapping their endpoints while maintaining desired degree constraints. Because each step only changes a tiny fraction of the graph, successive samples are highly correlated. To obtain independent samples, the chain must run for $N$ iterations between saves. Run it too short, and the results are biased by the starting point; run it too long, and computation is wasted.

Proposed Methods for Stopping

The authors propose two distinct strategies to identify the required number of iterations:

  1. Method A (Analytical): This approach models the evolution of individual edges as two-state Markov chains. By analyzing transition probabilities based on the graph's joint degree distribution, the authors derive a formula where $N$ is proportional to $|E| \ln(1/\epsilon)$, where $\epsilon$ represents the allowed residual correlation.
  2. Method B (Data-Driven): This statistical approach involves running a single long chain and "thinning" it by a factor $k$. The Bayesian Information Criterion (BIC) is then used to compare models of independence versus correlation to find the optimal stopping point.

Empirical Results and the $|E|$ Scaling Law

The methods were tested on four diverse networks: C. Elegans (neural), Power (electrical grid), Netscience (co-authorship), and Epinions (social).

Summary of graph properties and the calculated thinning factors for the four test networks.

A key finding is that the required mixing time scales linearly with the number of edges $|E|$. As seen in the table, for most networks, running the chain for $10|E|$ to $30|E|$ iterations is sufficient to achieve decorrelation. While Method B tends to be more conservative (suggesting higher thinning factors), both methods produce ensembles that are statistically indistinguishable regarding global metrics like diameter and clustering coefficients.

Conclusion

This research provides a practical framework for researchers to avoid the pitfalls of under-sampling (leading to biased results) or over-sampling (wasting computation). The $|E|$ scaling law offers a robust rule of thumb for graph generation. Future work will focus on identifying specific "hard-to-decorrelate" edges and extending these methods to samplers that preserve more complex graph properties.

Summary updated

Abstract

Markov chains are a convenient means of generating realizations of networks, since they require little more than a procedure for rewiring edges. If a rewiring procedure exists for generating new graphs with specified statistical properties, then a Markov chain sampler can generate an ensemble of graphs with prescribed characteristics. However, successive graphs in a Markov chain cannot be used when one desires independent draws from the distribution of graphs; the realizations are correlated. Consequently, one runs a Markov chain for N iterations before accepting the realization as an independent sample. In this work, we devise two methods for calculating N. They are both based on the binary "time-series" denoting the occurrence/non-occurrence of edge (u, v) between vertices u and v in the Markov chain of graphs generated by the sampler. They differ in their underlying assumptions. We test them on the generation of graphs with a prescribed joint degree distribution. We find the N proportional |E|, where |E| is the number of edges in the graph. The two methods are compared by sampling on real, sparse graphs with 10^3 - 10^4 vertices.
BibTeX
@inproceedings{ray2012are,
  author = {Jaideep Ray and Ali Pinar and C. Seshadhri},
  title = {{Are we there yet? When to stop a Markov chain while generating random graphs}},
  booktitle = {WAW},
  year = {2012},
  doi = {10.1007/978-3-642-30541-2\_12},
}
Figure