In the mathematical field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the Erdős–Rényi model refers to one of two closely related models for generating
random graph
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs l ...
s or the
evolution of a random network. These models are named after
Hungarian mathematicians
Paul Erdős
Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
Alfréd Rényi
Alfréd Rényi (20 March 1921 – 1 February 1970) was a Hungarian mathematician known for his work in probability theory, though he also made contributions in combinatorics, graph theory, and number theory.
Life
Rényi was born in Budapest to A ...
, who introduced one of the models in 1959.
Edgar Gilbert
Edgar Nelson Gilbert (July 25, 1923 – June 15, 2013) was an American mathematician and coding theorist, a longtime researcher at Bell Laboratories. His accomplishments include the Gilbert–Varshamov bound in coding theory, the Gilbert–Ell ...
introduced the other model contemporaneously with and independently of Erdős and Rényi.
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, also called the Erdős–Rényi–Gilbert model, 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
In mathematics, the probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly c ...
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
In mathematics, the term "almost all" means "all but a negligible quantity". More precisely, if X is a set (mathematics), set, "almost all elements of X" means "all elements of X but those in a negligible set, negligible subset of X". The meaning o ...
graphs.
Definition
There are two closely related variants of the Erdős–Rényi random graph model.

*In the
model, a graph is chosen uniformly at random from the collection of all graphs which have
nodes and
edges. The nodes are considered to be labeled, meaning that graphs obtained from each other by permuting the vertices are considered to be distinct. For example, in the
model, there are three two-edge graphs on three labeled vertices (one for each choice of the middle vertex in a two-edge path), and each of these three graphs is included with probability
.
*In the
model, a graph is constructed by connecting labeled nodes randomly. Each edge is included in the graph with probability
, independently from every other edge. Equivalently, the probability for generating each graph that has
nodes and
edges is
The parameter
in this model can be thought of as a weighting function; as
increases from
to
, the model becomes more and more likely to include graphs with more edges and less and less likely to include graphs with fewer edges. In particular, the case
corresponds to the case where all
graphs on
vertices are chosen with equal probability.
The behavior of random graphs are often studied in the case where
, the number of vertices, tends to infinity. Although
and
can be fixed in this case, they can also be functions depending on
. For example, the statement that almost every graph in
is connected means that, as
tends to infinity, the probability that a graph on
vertices with edge probability
is connected tends to
.
Comparison between the two models
The expected number of edges in ''G''(''n'', ''p'') is
, with a standard deviation asymptotic to
. Therefore, a rough heuristic is that if some property of ''G''(''n'', ''M'') with
does not significantly change in behavior if ''M'' is changed by up to ''s''(''n''), then ''G''(''n'', ''p'') should share that behavior.
This is formalized in a result of Łuczak. Suppose that ''P'' is a graph property such that for every sequence ''M'' = ''M''(''n'') with
, the probability that a graph sampled from ''G''(''n'', ''M'') has property ''P'' tends to ''a'' as ''n'' → ∞. Then the probability that ''G''(''n'', ''p'') has property ''P'' also tends to ''a''.
Implications in the other direction are less reliable, but a partial converse (also shown by Łuczak) is known when ''P'' is
monotone with respect to the subgraph ordering (meaning that if ''A'' is a subgraph of ''B'' and ''B'' satisfies ''P'', then ''A'' will satisfy ''P'' as well). Let
, and suppose that a monotone property ''P'' is true of both ''G''(''n'', ''p'' – ''ε'') and ''G''(''n'', ''p'' + ''ε'') with a probability tending to the same constant ''a'' as ''n'' → ∞. Then the probability that
has property ''P'' also tends to ''a''.
For example, both directions of equivalency hold if ''P'' is the property of being
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
, or if ''P'' is the property of containing a
Hamiltonian cycle
In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
. However, properties that are not monotone (e.g. the property of having an even number of edges) or that change too rapidly (e.g. the property of having at least
edges) may behave differently in the two models.
In practice, the ''G''(''n'', ''p'') model is the one more commonly used today, in part due to the ease of analysis allowed by the independence of the edges.
Properties of ''G''(''n'', ''p'')
With the notation above, a graph in ''G''(''n'', ''p'') has on average
edges. The distribution of the
degree of any particular vertex is
binomial
Binomial may refer to:
In mathematics
*Binomial (polynomial), a polynomial with two terms
*Binomial coefficient, numbers appearing in the expansions of powers of binomials
*Binomial QMF, a perfect-reconstruction orthogonal wavelet decomposition
* ...
:
:
where ''n'' is the total number of vertices in the graph. Since
:
this distribution is
Poisson for large ''n'' and ''np'' = const.
In a 1960 paper, Erdős and Rényi
[ The probability ''p'' used here refers there to ] described the behavior of ''G''(''n'', ''p'') very precisely for various values of ''p''. Their results included that:
*If ''np'' < 1, then a graph in ''G''(''n'', ''p'') will almost surely have no connected components of size larger than O(log(''n'')).
*If ''np'' = 1, then a graph in ''G''(''n'', ''p'') will almost surely have a largest component whose size is of order ''n''
2/3.
*If ''np'' → ''c'' > 1, where ''c'' is a constant, then a graph in ''G''(''n'', ''p'') will almost surely have a unique
giant component
In network theory, a giant component is a connected component of a given random graph that contains a significant fraction of the entire graph's vertices.
More precisely, in graphs drawn randomly from a probability distribution over arbitrarily ...
containing a positive fraction of the vertices. No other component will contain more than O(log(''n'')) vertices.
*If
, then a graph in ''G''(''n'', ''p'') will almost surely contain isolated vertices, and thus be disconnected.
*If
, then a graph in ''G''(''n'', ''p'') will almost surely be connected.
Thus
is a sharp threshold for the connectedness of ''G''(''n'', ''p'').
Further properties of the graph can be described almost precisely as ''n'' tends to infinity. For example, there is a ''k''(''n'') (approximately equal to 2log
2(''n'')) such that the largest
clique
A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...
in ''G''(''n'', 0.5) has almost surely either size ''k''(''n'') or ''k''(''n'') + 1.
Thus, even though finding the size of the largest clique in a graph is
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
, the size of the largest clique in a "typical" graph (according to this model) is very well understood.
Edge-dual graphs of Erdos-Renyi graphs are graphs with nearly the same degree distribution, but with degree correlations and a significantly higher
clustering coefficient
In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups ...
.
Relation to percolation
In
percolation theory
In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected ...
one examines a finite or infinite graph and removes edges (or links) randomly. Thus the Erdős–Rényi process is in fact unweighted link percolation on the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
. (One refers to percolation in which nodes and/or links are removed with heterogeneous weights as weighted percolation). As percolation theory has much of its roots in
physics
Physics is the scientific study of matter, its Elementary particle, fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge whi ...
, much of the research done was on the
lattices in Euclidean spaces. The transition at ''np'' = 1 from giant component to small component has analogs for these graphs, but for lattices the transition point is difficult to determine. Physicists often refer to study of the complete graph as a
mean field theory
In physics and probability theory, Mean-field theory (MFT) or Self-consistent field theory studies the behavior of high-dimensional random (stochastic) models by studying a simpler model that approximates the original by averaging over degrees of ...
. Thus the Erdős–Rényi process is the mean-field case of percolation.
Some significant work was also done on percolation on random graphs. From a physicist's point of view this would still be a mean-field model, so the justification of the research is often formulated in terms of the robustness of the graph, viewed as a communication network. Given a random graph of ''n'' ≫ 1 nodes with an average degree
. Remove randomly a fraction
of nodes and leave only a fraction
from the network. There exists a critical percolation threshold
below which the network becomes fragmented while above
a giant connected component of order ''n'' exists. The relative size of the giant component, ''P''
∞, is given by
[
]
:
Caveats
Both of the two major assumptions of the ''G''(''n'', ''p'') model (that edges are independent and that each edge is equally likely) may be inappropriate for modeling certain real-life phenomena. Erdős–Rényi graphs have low clustering, unlike many social networks. Some modeling alternatives include
Barabási–Albert model
The Barabási–Albert (BA) model is an algorithm for generating random scale-free network, scale-free complex network, networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the Worl ...
and
Watts and Strogatz model
Watts is plural for ''watt'', the unit of power.
Watts may also refer to:
People
* Watts (surname), a list of people with the surname Watts
Fictional characters
* Albie Watts, a fictional character in the British soap opera ''EastEnders''
* Ang ...
. These alternative models are not percolation processes, but instead represent a growth and rewiring model, respectively. Another alternative family of random graph models, capable of reproducing many real-life phenomena, are
exponential random graph models.
History
The ''G''(''n'', ''p'') model was first introduced by
Edgar Gilbert
Edgar Nelson Gilbert (July 25, 1923 – June 15, 2013) was an American mathematician and coding theorist, a longtime researcher at Bell Laboratories. His accomplishments include the Gilbert–Varshamov bound in coding theory, the Gilbert–Ell ...
in a 1959 paper studying the connectivity threshold mentioned above.
The ''G''(''n'', ''M'') model was introduced by Erdős and Rényi in their 1959 paper. As with Gilbert, their first investigations were as to the connectivity of ''G''(''n'', ''M''), with the more detailed analysis following in 1960.
Continuum limit representation of critical ''G''(''n'', ''p'')

A continuum limit of the graph was obtained when
is of order
.
Specifically, consider the sequence of graphs
for
. The limit object can be constructed as follows:
* First, generate a diffusion
where
is a
standard Brownian motion
In mathematics, the Wiener process (or Brownian motion, due to its historical connection with the physical process of the same name) is a real-valued continuous-time stochastic process discovered by Norbert Wiener. It is one of the best know ...
.
* From this process, we define the reflected process
. This process can be seen as containing many successive
excursion
An excursion is a trip, usually made for leisure, education, or Physical exercise, physical purposes. It is often an adjunct to a longer journey or visit to a place, sometimes for other (typically work-related) purposes.
Public transportatio ...
(not quite a Brownian excursion, see
). Because the drift of
is dominated by
, these excursions become shorter and shorter as
. In particular, they can be sorted in order of decreasing lengths: we can partition
into intervals
of decreasing lengths such that
restricted to
is a Brownian excursion for any
.
* Now, consider an excursion
. Construct a random graph as follows:

** Construct a
real tree (see
Brownian tree).
** Consider a
Poisson point process
In probability theory, statistics and related fields, a Poisson point process (also known as: Poisson random measure, Poisson random point field and Poisson point field) is a type of mathematical object that consists of points randomly located ...
on
with unit intensity. To each point
such that
, corresponds an underlying internal node and a leaf of the tree
. Identifying the two vertices, the tree
becomes a graph
Applying this procedure, one obtains a sequence of random infinite graphs of decreasing sizes:
. The theorem
states that this graph corresponds in a certain sense to the limit object of
as
.
See also
*, the graph formed by extending the ''G''(''n'', ''p'') model to graphs with a
countably infinite
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbe ...
number of vertices. Unlike in the finite case, the result of this infinite process is (with
probability 1) the same graph, up to isomorphism.
* describes ways in which properties associated with the Erdős–Rényi model contribute to the emergence of order in systems.
* describe a general probability distribution of graphs on "n" nodes given a set of network statistics and various parameters associated with them.
* , a generalization of the Erdős–Rényi model for graphs with latent community structure
*
*
References
Literature
*
*
External links
Video: Erdos-Renyi Random Graph
{{DEFAULTSORT:Erdos-Renyi model
Random graphs
Renyi model