Title: Generating Connected Random Graphs,
Abstract: Sampling random graphs is essential in many applications, and often
algorithms use Markov chain Monte Carlo methods to sample uniformly from the
space of graphs. However, often there is a need to sample graphs with some
property that we are unable, or it is too inefficient, to sample using standard
approaches. In this paper, we are interested in sampling graphs from a
conditional ensemble of the underlying graph model. We present an algorithm to
generate samples from an ensemble of connected random graphs using a
Metropolis-Hastings framework. The algorithm extends to a general framework for
sampling from a known distribution of graphs, conditioned on a desired
property. We demonstrate the method to generate connected spatially embedded
random graphs, specifically the well known Waxman network, and illustrate the
convergence and practicalities of the algorithm.