## Graph Sampling Algorithms (Yet Another Inadequate Placeholder)

*05 Sep 2024 10:04*

How do we efficiently generate graphs with specified properties?

This is (I think!) distinct from questions of how to get graph data by somehow sampling, in the statistical sense, a real network, the biases induced by different sampling procedures, etc.; for those, see under network data analysis.

See also: analysis of network data; complex networks; exponential-family random graph models; graph theory (in general); graphical models; Monte Carlo

- Recommended:
- M. E. J. Newman, Steven H. Strogatz and Duncan J. Watts,
"Random graphs with arbitrary degree distributions and their applications",
Physical Review E
**64**(2001): 026118, cond-mat/0007235

- To read:
- Vladimir Batagelj and Ulrik Brandes, "Efficient generation of large
random networks", Physical Review
E
**71**(2005): 036113 - Joseph Blitzstein and Persi Diaconis, "A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees",
Internet Mathematics
**6**(2011): 489--522 [Joe has a free PDF preprint, but it's from 2006...] - Michele Catanzaro, Marian Boguna and Romualdo Pastor-Satorras, "Generation of uncorrelated random scale-free networks", cond-mat/0408110
- Ton Coolen, Alessia Annibale, Ekaterina Roberts, Generating Random Networks and Graphs
- Alex Fout, Bailey K. Fosdick and Matthew P. Hitt, "Non-Uniform Sampling of Fixed Margin Binary Matrices", pp. 95--105 in Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference [FODS '20]
- Catherine Greenhill, "Generating graphs randomly", arxiv:2201.04888
- Yangbo He, Jinzhu Jia, Bin Yu, "Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs", Annals of Statistics
**41**(2013): 1742--1779, arxiv:1209.5860 - Brian Karrer and M. E. J. Newman, "Random graphs containing
arbitrary distributions of
subgraphs", Physical
Review E
**82**(2010): 066118, arxiv:1005.1659 - Jack Kuipers, Giusi Moffa, "Uniform random generation of large acyclic digraphs", arxiv:1202.6590
- Andre Krzywicki, "Defining statistical ensembles of random graphs," cond-mat/0110574
- E. S. Roberts and A. C. C. Coolen, "Unbiased degree-preserving
randomization of directed binary
networks", Physical
Review E
**85**(2012): 046103 - 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", arxiv:1101.6022
- Lionel Tabourier, Camille Roth, Jean-Philippe Cointet, "Generating constrained random graphs using multiple edge switches", arxiv:1012.3023
- Dmitri Volchenkov and Ph. Blanchard, "An Algorithm Generating Scale Free Graphs," cond-mat/0204126
- Sebastian Weber, Markus Porto, "Generation of arbitrarily two-point correlated random networks", arxiv:0708.4161
- 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", arxiv:2405.11416