{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T15:49:24Z","timestamp":1780328964118,"version":"3.54.1"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T00:00:00Z","timestamp":1553126400000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Decisions Cooperative Research Centre"},{"name":"ARC Center of Excellence for Mathematical and Statistical Frontiers"},{"name":"Australian Government Research Training Program"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 article, 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\u2013Hastings 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.<\/jats:p>","DOI":"10.1093\/comnet\/cnz011","type":"journal-article","created":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T04:26:06Z","timestamp":1552364766000},"page":"896-912","source":"Crossref","is-referenced-by-count":8,"title":["Generating connected random graphs"],"prefix":"10.1093","volume":"7","author":[{"given":"Caitlin","family":"Gray","sequence":"first","affiliation":[{"name":"ARC Centre of Excellence for Mathematical and Statistical Frontiers, School of Mathematical Sciences, University of Adelaide, North Terrace, South Australia 5005, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lewis","family":"Mitchell","sequence":"additional","affiliation":[{"name":"ARC Centre of Excellence for Mathematical and Statistical Frontiers, School of Mathematical Sciences, University of Adelaide, North Terrace, South Australia 5005, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew","family":"Roughan","sequence":"additional","affiliation":[{"name":"ARC Centre of Excellence for Mathematical and Statistical Frontiers, School of Mathematical Sciences, University of Adelaide, North Terrace, South Australia 5005, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2019,3,20]]},"reference":[{"key":"2019121010372419600_B1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1146\/annurev.ecolsys.38.091206.095818","article-title":"Plant-animal mutualistic networks: the architecture of biodiversity","volume":"38","author":"Bascompte,","year":"2007","journal-title":"Annu. Rev. Ecol. Evol. Syst."},{"key":"2019121010372419600_B2","doi-asserted-by":"crossref","first-page":"045104","DOI":"10.1103\/PhysRevE.69.045104","article-title":"Model for cascading failures in complex networks","volume":"69","author":"Crucitti,","year":"2004","journal-title":"Phys. Rev. E"},{"key":"2019121010372419600_B3","doi-asserted-by":"publisher","first-page":"1435","DOI":"10.1145\/3184558.3191590","article-title":"Super-blockers and the effect of network structure on information cascades","author":"Gray,","year":"2018","journal-title":"Companion Proceedings of the Web Conference 2018"},{"key":"2019121010372419600_B4","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1103\/RevModPhys.87.925","article-title":"Epidemic processes in complex networks","volume":"87","author":"Pastor-Satorras,","year":"2015","journal-title":"Rev. Mod. Phys."},{"key":"2019121010372419600_B5","doi-asserted-by":"crossref","first-page":"026125","DOI":"10.1103\/PhysRevE.80.026125","article-title":"Information cascades on degree-correlated random networks","volume":"80","author":"Payne,","year":"2009","journal-title":"Phys. Rev. E"},{"key":"2019121010372419600_B6","doi-asserted-by":"crossref","first-page":"1617","DOI":"10.1109\/49.12889","article-title":"Routing of multipoint connections","volume":"6","author":"Waxman,","year":"1988","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"2019121010372419600_B7","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1093\/comnet\/cny008","article-title":"The connectivity of graphs of graphs with self-loops and a given degree sequence","volume":"6","author":"Nishimura,","year":"2018","journal-title":"J. Complex Netw."},{"key":"2019121010372419600_B8","first-page":"838","article-title":"Uniform sampling of bipartite graphs with degrees in prescribed intervals","volume":"6","author":"Rechner,","year":"2017","journal-title":"J. Complex Netw."},{"key":"2019121010372419600_B9","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/11533719_45","article-title":"Efficient and simple generation of random simple connected graphs with prescribed degree sequence","volume-title":"Computing and Combinatorics","author":"Viger,","year":"2005"},{"key":"2019121010372419600_B10","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1137\/1.9781611972795.83","article-title":"Graph generation with prescribed feature constraints","volume-title":"Proceedings of the 2009 SIAM International Conference on Data Mining","author":"Ying,","year":"2009"},{"key":"2019121010372419600_B11","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs, I","volume":"6","author":"Erd\u00f6s,","year":"1959","journal-title":"Publ. Math. (Debrecen)"},{"key":"2019121010372419600_B12","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","article-title":"Random graphs","volume":"30","author":"Gilbert,","year":"1959","journal-title":"Ann. Math. Stat."},{"key":"2019121010372419600_B13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2010.11.002","article-title":"Spatial networks","volume":"499","author":"Barth\u00e9lemy,","year":"2011","journal-title":"Phys. Rep."},{"key":"2019121010372419600_B14","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.tcs.2018.08.014","article-title":"Geometric inhomogeneous random graphs","volume":"760","author":"Bringmann,","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"2019121010372419600_B15","doi-asserted-by":"crossref","first-page":"036125","DOI":"10.1103\/PhysRevE.73.036125","article-title":"Centrality measures in spatial networks of urban streets","volume":"73","author":"Crucitti,","year":"2006","journal-title":"Phys. Rev. E"},{"key":"2019121010372419600_B16","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1093\/comnet\/cny004","article-title":"Analytic models for SIR disease spread on random spatial networks","volume":"6","author":"Lang,","year":"2018","journal-title":"J. Complex Netw."},{"key":"2019121010372419600_B17","article-title":"Estimating the parameters of the Waxman random graph","author":"Roughan,","year":"2015"},{"key":"2019121010372419600_B18","first-page":"17","article-title":"Random distance within a rectangle and between two rectangles","volume":"43","author":"Ghosh,","year":"1951","journal-title":"Bull. Calcutta Math. Soc."},{"key":"2019121010372419600_B19","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","article-title":"Monte Carlo sampling methods using Markov chains and their applications","volume":"57","author":"Hastings,","year":"1970","journal-title":"Biometrika"},{"key":"2019121010372419600_B20","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1080\/01621459.1949.10483310","article-title":"The Monte Carlo method","volume":"44","author":"Metropolis,","year":"1949","journal-title":"J. Am. Stat. Assoc."},{"key":"2019121010372419600_B21","volume-title":"Monte Carlo Statistical Methods (Springer Texts in Statistics)","author":"Robert,","year":"2005"},{"key":"2019121010372419600_B22","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1137\/16M1087175","article-title":"Configuring random graph models with fixed degree sequences","volume":"60","author":"Fosdick,","year":"2018","journal-title":"SIAM Rev."},{"key":"2019121010372419600_B23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511894701","volume-title":"Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications","author":"Lusher,","year":"2012"},{"key":"2019121010372419600_B24","doi-asserted-by":"crossref","first-page":"056708","DOI":"10.1103\/PhysRevE.72.056708","article-title":"Generating uniformly distributed random networks","volume":"72","author":"Artzy-Randrup","year":"2015","journal-title":"Phys. Rev. E"},{"key":"2019121010372419600_B25","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1017\/S0963548306007978","article-title":"Sampling regular graphs and a peer-to-peer network","volume":"16","author":"Cooper,","year":"2007","journal-title":"Comb. Probab. Comput."},{"issue":"1.7","key":"2019121010372419600_B26","first-page":"1.1","article-title":"Generating constrained random graphs using multiple edge switches","volume":"16","author":"Tabourier,","year":"2011","journal-title":"J. Exp. Algorithmics"},{"key":"2019121010372419600_B27","article-title":"The Markov chain simulation method for generating connected power law random graphs","volume-title":"Proceedings of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX)","author":"Gkantsidis,","year":"2003"},{"key":"2019121010372419600_B28","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/265910.265914","article-title":"Sparsification\u2014a technique for speeding up dynamic graph algorithms","volume":"44","author":"Eppstein,","year":"1997","journal-title":"J. ACM"},{"key":"2019121010372419600_B29","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/rsa.20168","article-title":"The phase transition in inhomogeneous random graphs","volume":"31","author":"Bollob\u00e1s,","year":"2007","journal-title":"Random Struct. Algorithms"},{"key":"2019121010372419600_B30","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.dam.2018.06.019","article-title":"The flip Markov chain for connected regular graphs","volume":"254","author":"Cooper,","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"2019121010372419600_B31","doi-asserted-by":"crossref","DOI":"10.1109\/FOCS.2006.5","article-title":"A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science.","author":"Feder,","year":"2006"},{"key":"2019121010372419600_B32","first-page":"11","article-title":"Exploring network structure, dynamics, and function using NetworkX","volume-title":"Proceedings of the 7th Python in Science Conferences (SciPy 2008)","author":"Hagberg,","year":"2008"},{"key":"2019121010372419600_B33","volume-title":"R: A Language and Environment for Statistical Computing","year":"2017"},{"key":"2019121010372419600_B34","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/ss\/1177011143","article-title":"[Practical Markov chain Monte Carlo]: Comment: one long run with diagnostics: implementation strategies for Markov chain Monte Carlo","volume":"7","author":"Raftery,","year":"1992","journal-title":"Stat. Sci."},{"key":"2019121010372419600_B35","doi-asserted-by":"crossref","DOI":"10.1002\/9781118014967","volume-title":"Handbook of Monte Carlo Methods","author":"Kroese,","year":"2011"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/7\/6\/896\/31484134\/cnz011.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/7\/6\/896\/31484134\/cnz011.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T11:50:51Z","timestamp":1694692251000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/7\/6\/896\/5415736"}},"subtitle":[],"editor":[{"given":"James","family":"Gleeson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2019,3,20]]},"references-count":35,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2019,3,20]]},"published-print":{"date-parts":[[2019,12,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnz011","relation":{},"ISSN":["2051-1329"],"issn-type":[{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,12]]},"published":{"date-parts":[[2019,3,20]]}}}