View source for Erdős–Rényi model

{{short description|Two closely related models for generating random graphs}}
[[File:Critical 1000-vertex Erdős–Rényi–Gilbert graph.svg|thumb|upright=1.35|An Erdős–Rényi–Gilbert graph with 1000 vertices at the critical edge probability <math>p=1/(n-1)</math>, showing a large component and many small ones]]
{{Network Science}} 
In the mathematical field of [[Graph theory|graph theory]], the '''Erdős–Rényi model''' refers to one of two closely related models for generating [[Random graph|random graph]]s or the [[Evolution of a random network|evolution of a random network]]. These models are named after Hungarian mathematicians [[Biography:Paul Erdős|Paul Erdős]] and [[Biography:Alfréd Rényi|Alfréd Rényi]], who introduced one of the models in 1959.<ref name="er59"/><ref name="b01"/> [[Biography:Edgar Gilbert|Edgar Gilbert]] introduced the other model contemporaneously with and independently of Erdős and Rényi.<ref name="g59"/> 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''',<ref>{{cite journal
 | last = Fienberg | first = Stephen E.
 | doi = 10.1080/10618600.2012.738106
 | issue = 4
 | journal = Journal of Computational and Graphical Statistics
 | mr = 3005799
 | pages = 825–839
 | title = A brief history of statistical models for network analysis and open challenges
 | volume = 21
 | year = 2012| s2cid = 52232135
 }}</ref> 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|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|almost all]] graphs.

== Definition ==
There are two closely related variants of the Erdős–Rényi random graph model.

[[File:Erdos generated network-p0.01.jpg|thumb|A graph generated by the binomial model of Erdős and Rényi (''p''&nbsp;=&nbsp;0.01)]]
*In the <math>G(n,M)</math> model, a graph is chosen uniformly at random from the collection of all graphs which have <math>n</math> nodes and <math>M</math> 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 <math>G(3,2)</math> 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 <math>\tfrac{1}{3}</math>.
*In the <math>G(n,p)</math> model, a graph is constructed by connecting labeled nodes randomly. Each edge is included in the graph with probability <math>p</math>, independently from every other edge. Equivalently, the probability for generating each graph that has <math>n</math> nodes and <math>M</math> edges is <math display=block>p^M (1-p)^{ {n \choose 2}-M}.</math> The parameter <math>p</math> in this model can be thought of as a weighting function; as <math>p</math> increases from <math> 0 </math> to <math>1</math>, 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 <math>p=\tfrac{1}{2}</math> corresponds to the case where all <math>2^\binom{n}{2}</math> graphs on <math>n</math> vertices are chosen with equal probability.

The behavior of random graphs are often studied in the case where <math>n</math>, the number of vertices, tends to infinity.  Although <math>p</math> and <math>M</math> can be fixed in this case, they can also be functions depending on <math>n</math>.  For example, the statement that almost every graph in <math>G(n,2\ln(n)/n)</math> is connected means that, as <math>n</math> tends to infinity, the probability that a graph on <math>n</math> vertices with edge probability <math>2\ln(n)/n</math> is connected tends to <math>1</math>.

==Comparison between the two models==
The expected number of edges in ''G''(''n'', ''p'') is <math>\tbinom{n}{2}p</math>, and by the [[Law of large numbers|law of large numbers]] any graph in ''G''(''n'', ''p'') will almost surely have approximately this many edges (provided the expected number of edges tends to infinity).  Therefore, a rough heuristic is that if ''pn''<sup>2</sup> → ∞, then ''G''(''n'',''p'') should behave similarly to ''G''(''n'', ''M'') with <math>M=\tbinom{n}{2} p</math> as ''n'' increases.

For many graph properties, this is the case.  If ''P'' is any graph property which is [[Monotonic function|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), then the statements "''P'' holds for almost all graphs in ''G''(''n'',&nbsp;''p'')" and "''P'' holds for almost all graphs in <math> G(n, \tbinom{n}{2} p) </math>" are equivalent (provided ''pn''<sup>2</sup> → ∞). For example, this holds if ''P'' is the property of being [[Connectedness|connected]], or if ''P'' is the property of containing a [[Hamiltonian path|Hamiltonian cycle]].  However, this will not necessarily hold for non-monotone properties (e.g. the property of having an even number of edges).

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 <math>\tbinom{n}{2} p</math> edges. The distribution of the [[Degree (graph theory)|degree]] of any particular vertex is [[Binomial distribution|binomial]]:<ref>{{cite journal |last1= Newman |first1= Mark. E. J. |last2=Strogatz |first2=S. H. |last3=Watts |first3=D. J. |year= 2001 |title= Random graphs with arbitrary degree distributions and their applications|journal= Physical Review E|volume=64 |issue= 2 |pages=026118 |doi=10.1103/PhysRevE.64.026118|arxiv=cond-mat/0007235|bibcode=2001PhRvE..64b6118N |pmid= 11497662|s2cid= 360112 }}, Eq. (1)</ref>

: <math>P(\deg(v) = k) = {n-1\choose k}p^k(1-p)^{n-1-k},</math>

where ''n'' is the total number of vertices in the graph. Since

:<math>P(\deg(v) = k) \to \frac{(np)^k \mathrm{e}^{-np}}{k!} \quad \text{ as } n \to \infty \text{ and } np = \text{constant},</math>

this distribution is [[Poisson distribution|Poisson]] for large ''n'' and ''np'' = const.

In a 1960 paper, Erdős and Rényi<ref name="Erdos1960">{{cite journal |last1=Erdős |first1=P. |last2=Rényi |first2=A. |year=1960 |title=On the evolution of random graphs |journal=Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences] |volume=5 |pages=17–61 |url=http://www.renyi.hu/~p_erdos/1960-10.pdf |access-date=2011-11-18 |archive-date=2021-02-01 |archive-url=https://web.archive.org/web/20210201163041/https://www.renyi.hu/~p_erdos/1960-10.pdf |url-status=live }} The probability ''p'' used here refers there to <math>N(n) = \tbinom{n}{2} p</math></ref> described the behavior of ''G''(''n'',&nbsp;''p'') very precisely for various values of ''p''.  Their results included that:

*If ''np'' < 1, then a graph in ''G''(''n'',&nbsp;''p'') will almost surely have no connected components of size larger than O(log(''n'')).
*If ''np'' = 1, then a graph in ''G''(''n'',&nbsp;''p'') will almost surely have a largest component whose size is of order ''n''<sup>2/3</sup>.
*If ''np'' → ''c''&nbsp;>&nbsp;1, where ''c'' is a constant, then a graph in ''G''(''n'',&nbsp;''p'') will almost surely have a unique [[Giant component|giant component]] containing a positive fraction of the vertices.  No other component will contain more than O(log(''n'')) vertices.
*If <math>p<\tfrac{(1-\varepsilon)\ln n} n</math>, then a graph in ''G''(''n'', ''p'') will almost surely contain isolated vertices, and thus be disconnected.
*If <math>p>\tfrac{(1+\varepsilon) \ln n} n</math>, then a graph in ''G''(''n'', ''p'') will almost surely be connected.

Thus <math> \tfrac{\ln n} n</math> 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<sub>2</sub>(''n'')) such that the largest [[Clique (graph theory)|clique]] in ''G''(''n'',&nbsp;0.5) has almost surely either size ''k''(''n'') or ''k''(''n'')&nbsp;+&nbsp;1.<ref>{{cite journal
 | date = February 1972
 | journal = Notices of the American Mathematical Society
 | pages = A-382
 | title = The employee party problem
 | volume = 19}}</ref>

Thus, even though finding the size of the largest clique in a graph is NP-complete, 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|clustering coefficient]].<ref>{{cite journal |last1=Ramezanpour |first1=A. |last2=Karimipour |first2=V. |last3=Mashaghi |first3=A. |date=April 2003 |title=Generating correlated networks from uncorrelated ones |journal=Physical Review E |volume=67 |issue=4 |pages=046107 |doi=10.1103/PhysRevE.67.046107|arxiv=cond-mat/0212469 |bibcode=2003PhRvE..67d6107R |pmid=12786436 |s2cid=33054818 }}</ref>

==Relation to percolation==
In [[Percolation theory|percolation theory]] 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|complete graph]]. (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|physics]], much of the research done was on the [[Lattice (group)|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 [[Physics:Mean field theory|mean field theory]]. 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''&nbsp;≫&nbsp;1 nodes with an average degree&nbsp;<math>\langle k \rangle</math>. Remove randomly a fraction <math>1 - p'</math> of nodes and leave only a fraction <math>p'</math> from the network. There exists a critical percolation threshold <math>p'_c=\tfrac{1}{\langle k\rangle}</math> below which the network becomes fragmented while above <math>p'_c</math> a giant connected component of order ''n'' exists. The relative size of the giant component, ''P''<sub>∞</sub>, is given by<ref name="Erdos1960" /><ref name="er59">{{cite journal |last1=Erdős |first1=P. |last2=Rényi |first2=A. |year=1959 |title=On Random Graphs. I |journal=Publicationes Mathematicae |volume=6 |issue=3–4 |pages=290–297 |doi=10.5486/PMD.1959.6.3-4.12 |s2cid=253789267 |url=http://www.renyi.hu/~p_erdos/1959-11.pdf |access-date=2011-02-23 |archive-date=2020-08-07 |archive-url=https://web.archive.org/web/20200807021117/https://www.renyi.hu/~p_erdos/1959-11.pdf |url-status=live }}</ref><ref name="b01">{{Cite book | last = Bollobás | first = B. | title = Random Graphs | publisher = Cambridge University Press| edition = 2nd | year = 2001 | isbn = 0-521-79722-5}}
</ref><ref>
{{cite journal |last1= Bollobás |first1= B. |last2=Erdős |first2=P. |year= 1976 |title= Cliques in Random Graphs|journal=Mathematical Proceedings of the Cambridge Philosophical Society|volume=80 |issue=3 |pages= 419–427|doi= 10.1017/S0305004100053056 |bibcode=1976MPCPS..80..419B|s2cid= 16619643 }}
</ref>

:<math> P_\infty= p'[1-\exp(-\langle k \rangle P_\infty)]. \, </math>

==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.<ref>{{cite journal |last1=Saberi |first1=Abbas Ali |title=Recent advances in percolation theory and its applications |journal=Physics Reports |date=March 2015 |volume=578 |page=12 |doi=10.1016/j.physrep.2015.03.003 |arxiv=1504.02898 |bibcode=2015PhR...578....1S |s2cid=119209128 |url=https://www.sciencedirect.com/science/article/abs/pii/S0370157315002008 |access-date=30 January 2022}}</ref> Some modeling alternatives include [[Barabási–Albert model]] and Watts and Strogatz model. 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 family random graph models|exponential random graph models]].

== History ==
The ''G''(''n'',&nbsp;''p'') model was first introduced by [[Biography:Edgar Gilbert|Edgar Gilbert]] in a 1959 paper studying the connectivity threshold mentioned above.<ref name="g59">{{cite journal |last= Gilbert |first= E.N.|year=1959 |title=Random Graphs |journal=Annals of Mathematical Statistics |volume= 30|issue= 4|pages=1141–1144 |doi=10.1214/aoms/1177706098 |doi-access=free}}</ref>  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'',&nbsp;''M''), with the more detailed analysis following in 1960.

== Continuum limit representation of critical ''G''(''n'', ''p'') ==
[[File:Brownian motion quadratic drift.svg|thumb|390x390px|The Brownian motion with quadratic negative drift is decomposed into Brownian excursions of decreasing sizes.]]
A continuum limit of the graph was obtained when <math>p</math> is of order <math>1/n</math>.<ref name=":0">{{Cite journal |last1=Addario-Berry |first1=L. |last2=Broutin |first2=N. |last3=Goldschmidt |first3=C. |date=2012-04-01 |title=The continuum limit of critical random graphs |journal=Probability Theory and Related Fields |language=en |volume=152 |issue=3 |pages=367–406 |doi=10.1007/s00440-010-0325-4 |s2cid=253980763 |issn=1432-2064|doi-access=free }}</ref> Specifically, consider the sequence of graphs <math>G_n:=G(n,1/n+\lambda n^{-\frac{4}{3}})</math> for <math>\lambda\in \R</math>. The limit object can be constructed as follows:

* First, generate a diffusion <math>W^\lambda(t):=W(t)+\lambda t - \frac{t^2}{2}</math> where <math>W</math> is a standard Brownian motion.
* From this process, we define the reflected process <math>R^\lambda(t):= W^\lambda(t) - \inf\limits_{s\in[0,t]}W^\lambda(s)</math>. This process can be seen as containing many successive [[Brownian excursion|excursion]] (not quite a Brownian excursion, see <ref>{{Cite journal |last=Aldous |first=David |date=1997-04-01 |title=Brownian excursions, critical random graphs and the multiplicative coalescent |journal=The Annals of Probability |volume=25 |issue=2 |doi=10.1214/aop/1024404421 |s2cid=16578106 |issn=0091-1798 |doi-access=free }}</ref>). Because the drift of <math>W^\lambda</math> is dominated by <math>-\frac{t^2}{2}</math>, these excursions become shorter and shorter as <math>t\to +\infty</math>. In particular, they can be sorted in order of decreasing lengths: we can partition <math>\R</math> into intervals <math>(C_i)_{i\in \N}</math> of decreasing lengths such that <math>R^\lambda</math> restricted to <math>C_i</math> is a Brownian excursion for any <math>i\in \N</math>.
* Now, consider an excursion <math>(e(s))_{s\in [0,1]}</math>. Construct a random graph as follows:[[File:Brownian excursion with leaf and internal node identified..svg|thumb|392x392px|A Brownian excursion <math>(e(t))_{t\in [0,1]}</math>. Here, the process <math>\Xi</math> has a single point, marked with a red dot. The red line corresponds to a single internal node of the associated tree <math>T_e</math>, the green line corresponds to a leaf of <math>T_e</math>. If one adds an edge between the two nodes, one obtains a graph with a single cycle]]
** Construct a [[Real tree|real tree]] <math>T_e</math> (see [[Brownian tree]]).
** Consider a [[Poisson point process]] <math>\Xi</math> on <math>[0,1]\times \R_+</math> with unit intensity. To each point <math>(x,s)\in \Xi</math> such that <math>x\leq e(s)</math>, corresponds an underlying internal node and a leaf of the tree <math>T_e</math>. Identifying the two vertices, the tree <math>T_e</math> becomes a graph <math>\Gamma_e</math>

Applying this procedure, one obtains a sequence of random infinite graphs of decreasing sizes: <math>(\Gamma_i)_{i\in \N}</math>. The theorem<ref name=":0" /> states that this graph corresponds in a certain sense to the limit object of <math>G_n</math> as <math>n\to+\infty</math>.

==See also==
*{{annotated link|Rado graph}}, the graph formed by extending the ''G''(''n'',&nbsp;''p'') model to graphs with a countably infinite number of vertices. Unlike in the finite case, the result of this infinite process is (with [[Almost surely|probability&nbsp;1]]) the same graph, up to isomorphism.
*{{annotated link|Dual-phase evolution}} describes ways in which properties associated with the Erdős–Rényi model contribute to the emergence of order in systems.
*{{annotated link|Exponential random graph models}} describe a general probability distribution of graphs on "n" nodes given a set of network statistics and various parameters associated with them.
* {{annotated link|Stochastic block model}}, a generalization of the Erdős–Rényi model for graphs with latent community structure
* {{annotated link|Watts–Strogatz model}}
* {{annotated link|Barabási–Albert model}}

==References==
{{reflist|30em}}

==Literature==
* {{Cite book | last = West | first = Douglas B. | title = Introduction to Graph Theory | publisher = Prentice Hall | edition = 2nd | year = 2001 | isbn = 0-13-014400-2 }}
* {{cite book |title=Networks: An Introduction |last= Newman |first=M. E. J. |year= 2010|publisher=  Oxford}}

== External links ==
* [https://www.youtube.com/watch?reload=9&v=XwVZ5VttrW0 Video: Erdos-Renyi Random Graph]

{{DEFAULTSORT:Erdos-Renyi model}}
[[Category:Random graphs]]

{{Sourceattribution|Erdős–Rényi model}}