Random graphs (Erdős–Rényi model)
Grafos aleatorios (modelo de Erdős-Rényi)
- Date
- 1959 · confidence high
- Place
- Budapest, Hungary
- Credited to
- Paul Erdős and Alfréd Rényi
- Field
- Knowledge & symbols
What was discovered
A model in which a network is formed by adding edges at random between nodes and one studies the probability at which structures appear, such as a giant component. It founded the theory of random graphs.
Gilbert proposed a very similar model in 1959, and today both are called Erdős–Rényi. The first paper appeared in Publicationes Mathematicae Debrecen; the follow-up (1960) was at the Hungarian Academy of Sciences.
What it led to
- complex network theory
- the probabilistic method in combinatorics
- models of epidemics and internet connectivity