Generating connected random graphs
Files
(Accepted version)
Date
2019
Authors
Gray, C.
Mitchell, L.
Roughan, M.
Editors
Gleeson, J.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Journal of Complex Networks, 2019; 7(6):896-912
Statement of Responsibility
Caitlin Gray, Lewis Mitchell and Matthew Roughan
Conference Name
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.
School/Discipline
Dissertation Note
Provenance
Description
Advance Access Publication on 20 March 2019
Access Status
Rights
© The authors 2019. Published by Oxford University Press. All rights reserved.