Generating graphs randomly
From MaRDI portal
Publication:5051744
zbMath1504.05279arXiv2201.04888MaRDI QIDQ5051744
Publication date: 18 November 2022
Abstract: Graphs are used in many disciplines to model the relationships that exist between objects in a complex discrete system. Researchers may wish to compare a network of interest to a "typical" graph from a family (or ensemble) of graphs which are similar in some way. One way to do this is to take a sample of several random graphs from the family, to gather information about what is "typical". Hence there is a need for algorithms which can generate graphs uniformly (or approximately uniformly) at random from the given family. Since a large sample may be required, the algorithm should also be computationally efficient. Rigorous analysis of such algorithms is often challenging, involving both combinatorial and probabilistic arguments. We will focus mainly on the set of all simple graphs with a particular degree sequence, and describe several different algorithms for sampling graphs from this family uniformly, or almost uniformly.
Full work available at URL: https://arxiv.org/abs/2201.04888
Random graphs (graph-theoretic aspects) (05C80) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
This page was built for publication: Generating graphs randomly
