Generating connected random graphs

Simple item page
dc.contributor.authorGray, C.
dc.contributor.authorMitchell, L.
dc.contributor.authorRoughan, M.
dc.contributor.editorGleeson, J.
dc.date.issued2019
dc.descriptionAdvance Access Publication on 20 March 2019
dc.description.abstractSampling 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.
dc.description.statementofresponsibilityCaitlin Gray, Lewis Mitchell and Matthew Roughan
dc.identifier.citationJournal of Complex Networks, 2019; 7(6):896-912
dc.identifier.doi10.1093/comnet/cnz011
dc.identifier.issn2051-1310
dc.identifier.issn2051-1329
dc.identifier.orcidGray, C. [0000-0003-1928-7008]
dc.identifier.orcidMitchell, L. [0000-0001-8191-1997]
dc.identifier.orcidRoughan, M. [0000-0002-7882-7329]
dc.identifier.urihttp://hdl.handle.net/2440/124786
dc.language.isoen
dc.publisherOxford University Press (OUP)
dc.rights© The authors 2019. Published by Oxford University Press. All rights reserved.
dc.source.urihttps://doi.org/10.1093/comnet/cnz011
dc.subjectrandom graphs; MCMC; network sampling; connected networks
dc.titleGenerating connected random graphs
dc.typeJournal article
pubs.publication-statusPublished

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
hdl_124786.pdf
Size:
569.85 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download

Collections

Mathematical Sciences publications