Graph Sampling Algorithms
13 Mar 2022 14:10
How do we efficiently generate graphs with specified properties? (Yet another inadequate placeholder.) — This is (I think!) distinct from questions of how to get a data graph by somehow sampling, in the statistical sense, a real network, the baises 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
- 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
