Are we there yet? when to stop a markov chain while generating random graphs

Abstract. Markov chains are a convenient means of generating real-izations 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 in-dependent draws from the distribution of graphs; the realizations are correlated. Consequently, one runs a Markov chain for N iterations be-fore 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) be-tween 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 ∝ |E|, where |E | is the number of edges in the graph. The two methods are compared by sampling on real, sparse graphs with 103−104 vertices