Generating graphs randomly

• Published in 2022
• Added on 2022-02-16

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.

Links

• http://arxiv.org/abs/2201.04888v1
• http://arxiv.org/pdf/2201.04888v1

Other information

BibTeX entry

@article{Generatinggraphsrandomly,
	key = {Generatinggraphsrandomly},
	type = {article},
	title = {Generating graphs randomly},
	author = {Catherine Greenhill},
	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.},
	comment = {},
	date_added = {2022-02-16},
	date_published = {2022-10-09},
	urls = {http://arxiv.org/abs/2201.04888v1,http://arxiv.org/pdf/2201.04888v1},
	collections = {basically-computer-science},
	url = {http://arxiv.org/abs/2201.04888v1 http://arxiv.org/pdf/2201.04888v1},
	year = 2022,
	urldate = {2022-02-16},
	archivePrefix = {arXiv},
	eprint = {2201.04888},
	primaryClass = {math.CO}
}