Erdős–Rényi Random Graph Model

An Erdős–Rényi Random Graph Model is a Random Graph Model that assigns equal probability to all graphs with the same number of edges.

• Example(s):
  • …
• Counter-Example(s):
  • Random Dot-Product Graph,
  • Web-based Random Graph.
• See: Erdős–Rényi Graph, Random Graph, Statistical Independence.

---

---

References

2013

• (Wikipedia, 2013) ⇒ http://en.wikipedia.org/wiki/Erdős–Rényi_model Retrieved:2013-12-7.
  • In graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges. They are named for Paul Erdős and Alfréd Rényi, who first introduced one of the two models in 1959; the other model was introduced independently and contemporaneously by Edgar Gilbert. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

1960

• (Erdős & Rényi, 1960) ⇒ Paul Erdős, and A. Rényi (1960). “On the Evolution of Random Graphs". Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5.

---