🔖 On random graphs by Paul ErdĹ‘s and AlfrĂ©d RĂ©nyi (1959)

Bookmarked On Random Graphs. I by Paul Erdős and Alfréd Rényi (Publicationes Mathematicae. 6: 290–297.)

Original source of Erdős–Rényi model.

In the mathematical field of graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs. They are named after mathematicians Paul Erdős and Alfréd Rényi, who first introduced one of the models in 1959,[1][2] while Edgar Gilbert introduced the other model contemporaneously and independently of Erdős and Rényi.[3] In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely; in the model introduced by Gilbert, each edge has a fixed probability of being present or absent, independently of the other edges. 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.

hat tip: Linked: The New Science Of Networks by Albert-László Barabási

Leave a Reply

Your email address will not be published. Required fields are marked *