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