Graph Sampling Algorithms (Yet Another Inadequate Placeholder)
Last update: 14 Dec 2024 10:46First version: September (?) 2013
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", Statistics and Computing 25 (2015): 227--242, arxiv:1202.6590
- Andre Krzywicki, "Defining statistical ensembles of random graphs," cond-mat/0110574
- Gesine Reinert, Wenkai Xu, "SteinGen: Generating Fidelitous and Diverse Graph Samples", arxiv:2403.18578
- 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