Portal:Marine life/Selected Article/April, 2007

2008-05-05T20:12:59Z

41.248.162.32:

{{Network Science}}
In [[graph theory]], the '''Erdős–Rényi model''' is either of two closely related models for generating [[random graph]]s, including one that sets an edge between each pair of nodes with equal probability, [[statistical independence|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.

== Definition ==
There are two closely related variants of the Erdős–Rényi (ER) 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'' = 0.01)]]
*In the ''G''(''n'', ''M'') model, a graph is chosen uniformly at random from the collection of all graphs which have ''n'' nodes and ''M'' edges. For example, in the ''G''(3, 2) model, each of the three possible graphs on three vertices and two edges are included with probability 1/3.
*In the ''G''(''n'', ''p'') model, a graph is constructed by connecting nodes randomly. Each edge is included in the graph with probability ''p'' independent from every other edge. Equivalently, all graphs with ''n'' nodes and ''M'' edges have equal probability of

::<math>p^M (1-p)^{{n \choose 2}-M}.</math>

:The parameter ''p'' in this model can be thought of as a weighting function; as ''p'' increases from 0 to 1, 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 ''p'' = 0.5 corresponds to the case where all <math>2^\binom{n}{2}</math> graphs on ''n'' vertices are chosen with equal probability.

The behavior of random graphs are often studied in the case where ''n'', the number of vertices, tends to infinity. Although ''p'' and ''M'' can be fixed in this case, they can also be functions depending on ''n''. For example, the statement

:Almost every graph in ''G''(''n'', 2ln(''n'')/''n'') is connected.

means

:As ''n'' tends to infinity, the probability that a graph on ''n'' vertices with edge probability 2ln(''n'')/''n'' is connected, tends to 1.

==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]] 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''2 → ∞, 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 ''A'' satisfies ''P'', then ''B'' will satisfy ''P'' as well), then the statements "''P'' holds for almost all graphs in ''G''(''n'', ''p'')" and "''P'' holds for almost all graphs in <math> G(n, \tbinom{n}{2} p) </math>" are equivalent (provided ''pn''2 → ∞). 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 of any particular vertex is [[binomial distribution|binomial]]:<ref>{{cite journal |last= Newman |first= Mark. E. J. |authorlink= |coauthors=S. H. Strogatz and D. J. Watts |year= 2001 |month= |title= Random graphs with arbitrary degree distributions and their applications|journal= Physical Review E|volume=64 |issue= 026118|pages=|id= |url= |accessdate= |quote= |doi=10.1103/PhysRevE.64.026118}}, Eq. (1)</ref>

: <math>P(\operatorname{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(\operatorname{deg}(v) = k) \to \frac{(np)^k \mathrm{e}^{-np}}{k!} \quad \mbox{ as } n \to \infty \mbox{ and } np = \mathrm{const},</math>

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

In a 1960 paper, Erdős and Rényi<ref>{{cite journal |last= Erdős |first= Paul |authorlink= |coauthors=A. Rényi |year=1960 |month= |title=On the evolution of random graphs|journal=Publications of the Mathematical Institute of the Hungarian Academy of Sciences|volume=5 |issue=|pages=17–61|id= |url=http://www.renyi.hu/~p_erdos/1960-10.pdf |accessdate= |quote= |doi=}} The probability ''p'' used here refers there to <math>N(n) = {n \choose 2} p</math></ref> 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]] containing a positive fraction of the vertices. No other component will contain more than O(log(''n'')) vertices.

*If <math>p<\tfrac{(1-\epsilon)\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+\epsilon) \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 [[threshold function|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 2log2(''n'')) such that the largest [[Clique (graph theory)|clique]] 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]], the size of the largest clique in a "typical" graph (according to this model) is very well understood.

==Relation to percolation==
In [[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]]. (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]], 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 [[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'' ≫ 1 nodes with an average degree <''k''>. Remove randomly a fraction 1 − ''p′'' of nodes and leave only a fraction ''p′'' 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''∞, is given by<ref>{{Cite book | last = Bollobás | first = B. | title = Random Graphs | publisher = Cambridge University Press| edition = 2nd | year = 2001 | isbn = 0-521-79722-5 | postscript = }}
</ref><ref>
{{cite journal |last= Bollobás |first= B. |authorlink= |coauthors=Erdős, P. |year= 1976 |month= |title= Cliques in Random Graphs|journal= Math. Proc. Cambridge Phil. Soc.|volume=80 |issue=3 |pages= 419–427|id= |url= |accessdate= |quote= |doi= 10.1017/S0305004100053056 }}
</ref><ref>
{{cite journal |last= Erdős |first= P.|authorlink= |coauthors=Rényi, A. |year=1959 |month= |title=On Random Graphs. I |journal=Publicationes Mathematicae |volume= 6|issue= |pages=290–297 |id= |url=http://www.renyi.hu/~p_erdos/1959-11.pdf |accessdate= |quote= }}
</ref><ref>{{cite journal |last= Erdős |first= P.|authorlink= |coauthors=Rényi, A. |year=1960 |month= |title=The Evolution of Random Graphs |journal=Magyar Tud. Akad. Mat. Kutató Int. Közl. |volume= 5|issue= |pages=17–61 |id= |url= |accessdate= |quote= }}</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 real-life phenomena. In particular, an Erdős–Rényi graph does not have heavy tails, as is the case in many real networks. Moreover, it has low clustering, unlike many social networks. For popular modeling alternatives, see [[Barabási–Albert model]] and [[Watts and Strogatz model]]. One should note that these alternative models are not percolation processes, but instead represent a growth and rewiring model, respectively. A model for interacting ER networks was developed recently by Buldyrev ''et al.''.<ref>{{cite journal |author=S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin|year=2010 |title=Catastrophic cascade of failures in interdependent networks |journal=Nature |volume= 464 |issue= 7291|pages=1025–8 |url= http://havlin.biu.ac.il/Publications.php?keyword=Catastrophic+cascade+of+failures+in+interdependent+networks&year=*&match=all| doi = 10.1038/nature08932}}</ref>

== History ==
The ''G''(''n'', ''p'') model was first introduced by [[Edgar Gilbert]] in a 1959 paper which studied the connectivity threshold mentioned above.<ref>{{cite journal |last= Gilbert |first= E.N.|authorlink=Edgar Gilbert |coauthors= |year=1959 |month= |title=Random Graphs |journal=Annals of Mathematical Statistics |volume= 30|issue= 4|pages=1141–1144 |id= |url= |accessdate= |quote=|doi=10.1214/aoms/1177706098 }}</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'', ''M''), with the more detailed analysis following in 1960.

== Interacting Erdős–Rényi random graphs model (communities of ER networks) ==
A simple generalization of the (ER) random graph model applies as follows
.<ref>{{cite journal |author=M. Ostilli, J. F. F. Mendes|year=2009 |title=Small-world of communities: communication and correlation of the meta-network |journal=Journal of Statistical Mechanics
|volume =L08004|pages=1 |url=http://iopscience.iop.org/1742-5468/2009/08/L08004/| doi = 10.1088/1742-5468/2009/08/L08004}}</ref>
Let the set of nodes ''n'' be partitioned into ''q'' communities, composed of
<math>n^{(1)},...,n^{(q)}</math> nodes each, with <math>\sum_l n^{(l)}=n </math>,
and let be given the following ''q x q'' matrix of probabilities
<math>p^{(l,m)}</math>
of connection between any node of the community ''l''
with any other node of the community ''m'' (possibly with ''l=m'')

::<math>p^{(l,m)}=\frac{c^{(l,m)}}{n}</math>,

where <math>c^{(l,m)}</math> is in turn a non negative ''q x q'' matrix which satisfies the detailed balance

:: <math>n^{(l)} c^{(l,m)}=c^{(l,m)}n^{(m)}</math>.

By using this construction one realizes a generalization of the ER random graph where <math>c^{(l,m)}</math> represents the matrix of average connectivities
between the community ''l'' and the community ''m'', the self-cases ''l=m'' being the ones where we recover the single ER network (''q=1'').
It is possible to prove
that such a community of ER networks is percolating when the matrix <math>c^{(l,m)}</math> satisfies
<ref>{{cite journal |author=M. Ostilli, J. F. F. Mendes|year=2009 |title=Communication and correlation among communities |journal=Physical Review E |volume= 80 |issue=1 |pages=011142 |url=
http://link.aps.org/doi/10.1103/PhysRevE.80.011142| doi = 10.1103/PhysRevE.80.011142 }}</ref>

::<math>\max \{\mathrm{Eigenvalues~of~} \bold{c} \}>1 </math>,

which in particular implies that the percolation "threshold" is actually now a surface given by the following Eq.

::<math> \det (\bold{1-c})=0 </math>.

Unlike the case ''q=1'' (where we recover the percolation threshold ''c=1'', see above)
this Eq. can have many solutions and in general the number of solutions can grow faster than ''n''.

==See also==
*[[Rado graph]], the graph formed by extending the ''G''(''n'', ''p'') model to graphs with a [[countability|countably infinite]] number of vertices. Unlike in the finite case, the result of this infinite process is (with [[almost surely|probability 1]]) the same graph, up to isomorphism.
*[[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.
* [[Watts and Strogatz model]]
* [[Barabási–Albert model]]

==References==
{{reflist}}

==Further reading==
* {{Cite book | last = West | first = Douglas B. | title = Introduction to Graph Theory | publisher = Prentice Hall | edition = 2nd | year = 2001 | isbn = 0-13-014400-2 | postscript = }}
* {{cite book |title=Networks: An Introduction |last= Newman |first=M. E. J. |year= 2010|publisher= Oxford}}
* {{cite book |title= Complex Networks: Structure, Robustness and Function|year= 2010 |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php |publisher= Cambridge University Press |author= Reuven Cohen and [[Shlomo Havlin]]}}

{{DEFAULTSORT:Erdos-Renyi model}}
[[Category:Random graphs]]
[[Category:Paul Erdős|Renyi model]]

formulasearchengine - User contributions [en]

Portal:Marine life/Selected Article/April, 2007