Generating graphs randomly
From MaRDI portal
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.
Recommendations
Cited in
(19)- Generating Random Networks and Graphs
- scientific article; zbMATH DE number 5912545 (Why is no real title available?)
- scientific article; zbMATH DE number 459046 (Why is no real title available?)
- Uniform sampling of directed and undirected graphs conditional on vertex connectivity
- Random graphic model generation algorithm based on Prüfer code
- scientific article; zbMATH DE number 4142091 (Why is no real title available?)
- Cataloging graphs by generating them uniformly at random
- scientific article; zbMATH DE number 3924802 (Why is no real title available?)
- Efficient and simple generation of random simple connected graphs with prescribed degree sequence
- Interactive random graph generation with evolutionary algorithms
- On a possible generation modality of random graphs
- Coin-flipping, Ball-dropping, and Grass-hopping for generating random graphs from matrices of edge probabilities
- Random graph generation using multiple switches of edges
- Uniform generation of temporal graphs with given degrees
- Triangle switches: irreducibility and mixing
- Disease transmission on random graphs using edge-based percolation
- Extremal estimates of the Wiener index for weakly connected directed graphs
- Sequential stub matching for asymptotically uniform generation of directed graphs with a given degree sequence
- A program generating homogeneous random graphs with given weights
This page was built for publication: Generating graphs randomly
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5051744)
