A stopping criterion for Markov chains when generating independent random graphs

Jaideep Ray, Ali Pinar, C. Seshadhri

Abstract

Markov chains are convenient means of generating realizations of networks with a given (joint or otherwise) degree distribution, since they simply require a procedure for rewiring edges. The major challenge is to find the right number of steps to run such a chain, so that we generate truly independent samples. Theoretical bounds for mixing times of these Markov chains are too large to be practically useful. Practitioners have no useful guide for choosing the length, and tend to pick numbers fairly arbitrarily. We give a principled mathematical argument showing that it suffices for the length to be proportional to the number of desired number of edges. We also prescribe a method for choosing this proportionality constant. We run a series of experiments showing that the distributions of common graph properties converge in this time, providing empirical evidence for our claims.

Introduction

Generating independent random graphs that preserve specific structural properties, such as degree distribution, is a fundamental task in network science. The standard approach utilizes Markov Chain Monte Carlo (MCMC) methods, where an initial graph is iteratively "scrambled" through edge-swapping operations. However, a critical question remains: how many steps are necessary to ensure the resulting graph is independent of its starting state?

Existing theoretical upper bounds for "mixing times" are often astronomically high—on the order of $O(|E|^6)$—making them practically useless for real-world networks. Consequently, researchers often resort to arbitrary stopping points. This paper addresses this gap by providing a principled mathematical argument that the required number of steps $N$ is actually proportional to the number of edges $|E|$, typically ranging from $5|E|$ to $30|E|$.

Methodology

The authors bridge the gap between theory and practice by modeling the behavior of individual edges as 2-state Markov chains. They analyze transition probabilities under two common constraints: preserving the Degree Distribution (DD) and the more restrictive Joint Degree Distribution (JDD).

The edge-swapping process for preserving degree distribution (DD).

By examining the eigenvalues of these edge-level chains, the authors prove that the time required for an edge to "forget" its initial state is proportional to the total number of edges. To validate this, they used four diverse real-world networks: C. Elegans (neural network), Netscience (co-authorship), Power (electrical grid), and soc-Epinions1 (large social network). They also introduced a data-driven method using the Bayesian Information Criterion (BIC) to verify the independence of sampled graphs.

Key Insights and Results

A primary finding is the "Double Rule": preserving the JDD is approximately twice as computationally demanding as preserving the simple DD. Specifically, the model predicts $N \approx (m/2) \ln(1/\epsilon)$ for DD and $N \approx m \ln(1/\epsilon)$ for JDD.

The study also distinguishes between global and local mixing. While global properties like clustering coefficients and diameters converge rapidly, a small fraction of "pathological" edges in large graphs may take significantly longer to decorrelate. However, for most research applications, these few edges do not prevent the overall graph statistics from stabilizing.

Convergence of graph property distributions as the chain length increases (decreasing epsilon).

Empirical results demonstrate that running the chain for $5|E|$ steps (for DD) or $10|E|$ steps (for JDD) is generally sufficient. As shown in the convergence plots, the distributions of global metrics for these lengths become statistically indistinguishable from much longer runs. This was further validated using the Gelman-Rubin diagnostic, confirming that the chains effectively explore the entire state space.

Conclusion and Future Work

This work provides a robust "rule of thumb" for practitioners, moving away from arbitrary stopping criteria. While $10|E|$ is sufficient for general structural analysis, the authors caution that higher thresholds may be necessary for privacy-sensitive applications where individual "pathological" edges must be fully randomized. Future work may involve refining the heuristic approximations used for the $\alpha$ parameter in different graph topologies. To support the community, the authors have released the graphMC software implementation of their independence tests.

Summary updated

Abstract

Markov chains are convenient means of generating realizations of networks with a given (joint or otherwise) degree distribution, since they simply require a procedure for rewiring edges. The major challenge is to find the right number of steps to run such a chain, so that we generate truly independent samples. Theoretical bounds for mixing times of these Markov chains are too large to be practically useful. Practitioners have no useful guide for choosing the length, and tend to pick numbers fairly arbitrarily. We give a principled mathematical argument showing that it suffices for the length to be proportional to the number of desired number of edges. We also prescribe a method for choosing this proportionality constant. We run a series of experiments showing that the distributions of common graph properties converge in this time, providing empirical evidence for our claims.
BibTeX
@inproceedings{ray2012stopping,
  author = {Jaideep Ray and Ali Pinar and C. Seshadhri},
  title = {{A stopping criterion for Markov chains when generating independent random graphs}},
  booktitle = {WAW},
  year = {2012},
  doi = {10.1007/978-3-642-30541-2\_12},
}
Figure