<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html> <head> <link href="https://bactra.org/plain-style.css" rel="stylesheet" type="text/css"> <title>Graph Sampling Algorithms (Yet Another Inadequate Placeholder)</title>        </head> <body>   <P> <P></P><!-- Access to MathJax through the version I'm hosting on bactra.org !--><!-- but only IF mathmode is activated via meta_mathmode !-->  <script> window.MathJax = {  tex: {    inlineMath: [['$','$'], ['\\(','\\)']],    processEscapes: true,    autoload: {      color: [],      colorv2: ['color']    },    packages: {'[+]': ['noerrors']}  },  options: {    ignoreHtmlClass: 'tex2jax_ignore',    processHtmlClass: 'tex2jax_process'  },  loader: {    load: ['[tex]/noerrors']  }};</script>      <cite><a href="http://bactra.org/notebooks">Notebooks</a></cite> <div class="text"><div class="left"><h2>Graph Sampling Algorithms (Yet Another Inadequate Placeholder)</h2> <i><a href="faq.html#5.4">Last update</a>: 21 Apr 2025 21:17</i><br><i><a href="faq.html#5.4">First version</a>: September (?) 2013</i> <hr> <P>  <P>How do we efficiently generate graphs with specified properties? <P>This is (I think!) distinct from questions of how to get graph data bysomehow sampling, in the statistical sense, a real network, the biases inducedby different sampling procedures, etc.; for those, seeunder <a href="network-data-analysis.html">network data analysis</a>.  <ul>See also:	<li><a href="network-data-analysis.html">analysis of network data</a>	<li><a href="complex-networks.html">complex networks</a>	<li><a href="ergms.html">exponential-family random graph models</a>	<li><a href="graph-theory.html">graph theory</a> (in general)	<li><a href="graphical-models.html">graphical models</a>	<li><a href="monte-carlo.html">Monte Carlo</a>	</ul> <ul>Recommended:	<li>M. E. J. Newman, Steven H. Strogatz and Duncan J. Watts,"Random graphs with arbitrary degree distributions and their applications",<cite>Physical Review E</cite> <strong>64</strong> (2001): 026118,<a href="http://arxiv.org/abs/cond-mat/0007235">cond-mat/0007235</a>	</ul> <ul>To read:	<li>Vladimir Batagelj and Ulrik Brandes, "Efficient generation of largerandom networks", <ahref="https://doi.org/10.1103/PhysRevE.71.036113"><cite>Physical ReviewE</citE><strong>71</strong> (2005): 036113</a>	<li>Joseph Blitzstein and Persi Diaconis, "A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees",<a href="https://doi.org/10.1080/15427951.2010.557277"><cite>Internet Mathematics</cite> <strong>6</strong> (2011): 489--522</a> [Joe has a<a href="http://www.people.fas.harvard.edu/~blitz/BlitzsteinDiaconisGraphAlgorithm.pdf">free PDF preprint</a>, but it's from 2006...]	<li>Michele Catanzaro, Marian Boguna and Romualdo Pastor-Satorras,"Generation of uncorrelated random scale-free networks", <ahref="http://arxiv.org/abs/cond-mat/0408110">cond-mat/0408110</a>	<li>Ton Coolen, Alessia Annibale, Ekaterina Roberts, <a href="https://doi.org/10.1093/oso/9780198709893.001.0001"><cite>Generating Random Networks and Graphs</cite></a>	<li>Alex Fout, Bailey K. Fosdick and Matthew P. Hitt, "Non-Uniform Sampling of Fixed Margin Binary Matrices", <a href="https://doi.org/10.1145/3412815.3416887">pp. 95--105 in <cite>Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference</cite> [FODS '20]</a>	<li>Catherine Greenhill, "Generating graphs randomly", <a href="http://arxiv.org/abs/2201.04888">arxiv:2201.04888</a>	<li>Yangbo He, Jinzhu Jia, Bin Yu, "Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs", <a href="https://doi.org/10.1214/13-AOS1125"><cite>Annals of Statistics</cite> <strong>41</strong> (2013): 1742--1779</a>, <a href="http://arxiv.org/abs/1209.5860">arxiv:1209.5860</a>	<li>Brian Karrer and M. E. J. Newman, "Random graphs containingarbitrary distributions ofsubgraphs", <a href="https://doi.org/10.1103/PhysRevE.82.066118"><cite>PhysicalReview E</cite> <strong>82</strong> (2010): 066118</a>, <a href="http://arxiv.org/abs/1005.1659">arxiv:1005.1659</a>	<li>Jack Kuipers, Giusi Moffa, "Uniform random generation of large acyclic digraphs", <a href="https://doi.org/10.1007/s11222-013-9428-y"><cite>Statistics and Computing</cite> <strong>25</strong> (2015): 227--242</a>, <a href="http://arxiv.org/abs/1202.6590">arxiv:1202.6590</a>	<li>Andre Krzywicki, "Defining statistical ensembles of randomgraphs," <a href="http://arxiv.org/abs/cond-mat/0110574">cond-mat/0110574</a>	<li>Gesine Reinert, Wenkai Xu, "SteinGen: Generating Fidelitous and Diverse Graph Samples", <a href="http://arxiv.org/abs/2403.18578">arxiv:2403.18578</a>	<li>E. S. Roberts and A. C. C. Coolen, "Unbiased degree-preservingrandomization of directed binarynetworks", <a href="https://doi.org/10.1103/PhysRevE.85.046103"><cite>PhysicalReview E</cite> <strong>85</strong> (2012): 046103</a>	<li>E. S. Roberts, A. C. C. Coolen, T. Schlitt, "Tailored graph ensembles as proxies or null models for real networks II: results on directed graphs", <a href="http://arxiv.org/abs/1101.6022">arxiv:1101.6022</a>	<li>Lionel Tabourier, Camille Roth, Jean-Philippe Cointet, "Generating constrained random graphs using multiple edge switches", <a href="http://arxiv.org/abs/1012.3023">arxiv:1012.3023</a>	<li>Dmitri Volchenkov and Ph. Blanchard, "An Algorithm Generating ScaleFree Graphs,"<a href="http://arxiv.org/abs/cond-mat/0204126">cond-mat/0204126</a>	<li>Sebastian Weber, Markus Porto, "Generation of arbitrarily two-pointcorrelated randomnetworks", <a href="http://arxiv.org/abs/0708.4161">arxiv:0708.4161</a>	<li>Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng, Mahashweta Das, Hanghang Tong, "Discrete-state Continuous-time Diffusion for Graph Generation", <a href="http://arxiv.org/abs/2405.11416">arxiv:2405.11416</a>	</ul>  </p> </div></div> <hr> <div class="footer"><P><a href="http://bactra.org/notebooks/graph-sampling.html">permanent link for thisnote</a> &nbsp; <a href="http://bactra.org/notebooks/graph-sampling.rss">RSS feed for thisnote</a></P></div><div class="foot"> <center> <cite><a href="http://bactra.org/notebooks">Notebooks</a></cite>: &nbsp; <a href="http://www.blosxom.com/">Powered by Blosxom</a> </center> </div> </body></html>