更改
无编辑摘要
该词条由【普天星相】翻译编辑，由【Flynn】审校，【张江】总审校，翻译自Wikipedia词条 [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model]
在[https://en.wikipedia.org/wiki/Graph_theory 图论]的数学理论部分中，'''ER随机图模型（Erdős–Rényi model）'''可指代两个密切相关的[https://en.wikipedia.org/wiki/Random_graph 随机图]生成模型中的任意一个。ER随机图模型的名字源于最早提出上述模型之一的数学家[https://en.wikipedia.org/wiki/Paul_Erd%C5%91s Paul Erdős]（保尔•厄多斯）和[https://en.wikipedia.org/wiki/Alfr%C3%A9d_R%C3%A9nyi Alfréd Rényi]（阿尔弗烈德•瑞利），他们在1959年首次提出了其中一个模型，<ref name="er59"/><ref name="b01"/>而几乎在同时期，[https://en.wikipedia.org/wiki/Edgar_Gilbert Edgar Gilbert]（埃德加•吉尔伯特）独立提出了另外一个模型。<ref name="g59"/>在Erdős和Rényi的模型中，节点集一定、连边数也一定的所有图是等概率的；在Gilbert的模型中，每个连边存在与否有着固定的概率，与其他连边无关。在[https://en.wikipedia.org/wiki/Probabilistic_method 概率方法]中，这两种模型可用来证明满足各种性质的图的存在，也可为几乎所有图的性质提供严格的定义。
==定义==
ER随机图模型有两个密切相关的版本。
*在模型''G''(''n'', ''M'')中，从''n''个节点、''M''个连边构成的所有图的集合里随机选择一个图。例如，在''G''(3, 2)模型中，3个节点和2个连边能构成三种可能的图，每种图的概率为1/3。
*在模型''G''(''n'', ''p'')中，随机连接节点构成一个图。图中每个连边彼此独立，连接的概率为''p''。等价地，拥有''n''个节点、''M''个连边的所有图具有相同的概率
<math>p^M (1-p)^{{n \choose 2}-M}</math>。
此模型中的参数''p''可以看成是加权函数；随着''p''从0增加到1，模型更倾向于包含拥有更多连边的图，而包含拥有较少连边的图的概率则降低。特别地，与''p''=0.5相对应的情况是，在拥有''n''个节点的<math>2^\binom{n}{2}</math>个图中，每个图被选择的概率相等。<br />
我们通常研究节点数''n''趋于无穷时随机图的表现。尽管在这种情况下，''p''和''M''可以固定，但是，它们也可以是关于''n''的函数。例如，命题“''G''(''n'', 2ln(''n'')/''n'')中几乎每个图都是连通的”的意思是，当''n''趋于无穷时，拥有''n''个节点、连边概率为2ln(''n'')/''n''的图连通的概率趋于1。
==两种模型的比较==
''G''(''n'', ''p'')中可能的连边数为<math>\binom{n}{2}p</math>，由[https://en.wikipedia.org/wiki/Law_of_large_numbers 大数定律]，''G''(''n'', ''p'')中的每个图几乎必有大概这么多连边（假设可能的连边数趋于无穷）。因此，粗略的结果是如果pn<sup>2</sup> → ∞，那么当<math>M=\tbinom{n}{2} p</math>随着n的增加而增加时，''G''(''n'', ''p'')将与''G''(''n'', ''M'')有相似的表现。许多图的性质都是这样。如果P是满足对子图序[https://en.wikipedia.org/wiki/Monotonic_function 单调]的任意一种图的性质（即若A是B的子图且A满足P，则B也满足P），那么命题“''G''(''n'', ''p'')中几乎所有图满足P”等价于“<math> G(n, \tbinom{n}{2} p) </math>中几乎所有图满足P”（其中pn<sup>2</sup> → ∞）。例如，当P是[https://en.wikipedia.org/wiki/Connectedness 连通性]时，或P是包含[https://en.wikipedia.org/wiki/Hamiltonian_path 哈密顿圈]的性质时，上述关系就成立。然而，它对非单调性质（如具有偶数连边的性质）未必成立。
如今在实际应用中，''G''(''n'', ''p'')模型更加常用，部分原因是通过连边的独立性进行分析较为容易。
[[File:1280px-Erdos generated network-p0.01.jpg|200px|thumb|right|二项分布ER模型生成的一个图（p=0.01）]]
==G(n, p)的性质==
沿用上述符号，G(n, p)中的一个图平均有<math>\binom{n}{2}p</math>条连边。任意特定节点的度服从[https://en.wikipedia.org/wiki/Binomial_distribution 二项分布]：<ref>{{cite journal |last= Newman |first= Mark. E. J. |authorlink= |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= |pages=026118
|id=
|url=
|accessdate=
|quote=
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1103/PhysRevE.64.026118 10.1103/PhysRevE.64.026118]
.[https://en.wikipedia.org/wiki/ArXiv arxiv]:[https://arxiv.org/abs/cond-mat/0007235 cond-mat/0007235]
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/2001PhRvE..64b6118N 2001PhRvE..64b6118N]}}, Eq. (1)</ref>
<math>P(\deg(v) = k) = {n-1\choose k}p^k(1-p)^{n-1-k},</math>
其中n为图中节点的总数。由于
<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>
故当n很大且np=常数时，服从[https://en.wikipedia.org/wiki/Poisson_distribution 泊松分布]。
在1960年的一篇论文中，Erdős和Rényi<ref name="Erdos1960">{{cite journal |last=Erdős |first=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 |issue=|pages=17–61|id= |url=http://www.renyi.hu/~p_erdos/1960-10.pdf |accessdate= |quote= |doi=}} 这里的概率p指的是<math>N(n) = \tbinom{n}{2} p</math></ref>非常精确地描述了p在不同取值下G(n, p)的表现。其结论有：
*若np<1，则G(n, p)中的一个图几乎一定没有连通分量的大小大于O(log(n))。
*若np=1，则G(n, p)中的一个图几乎必有最大的连通分量，其阶为n <sup>2/3</sup>。
*若np→c>1，其中c为常数，则G(n, p)中的一个图几乎必有唯一的包含节点有限部分的[[巨连通集团]]。没有连通分量会有超过O(log(n))个节点。
*若<math>p<\tfrac{(1-\varepsilon)\ln n} n</math>，则G(n, p)中的一个图几乎必有孤立节点，因而它是不连通的。
*若 <math>p{>}\tfrac{(1+\varepsilon)\ln n} n</math>，则G(n, p)中的一个图几乎一定是连通的。
因此<math> \tfrac{\ln n} n</math>是G(n, p)连通性的重要临界值。
当n趋于无穷大时，还有许多图的性质几乎处处成立。例如，存在k(n)（近似等于2log <sub>2</sub> (n)）使得G(n, 0.5)中最大团的大小几乎必为k(n)或k(n)+1。<ref>{{cite journal
| last = Matula | first = David W.
| date = February 1972
| journal = Notices of the American Mathematical Society
| pages = A-382
| title = The employee party problem
| volume = 19}}</ref>
因此，尽管确定图中最大团的大小是[https://en.wikipedia.org/wiki/NP-complete NP完全的]，但“典型”图中最大团的大小（根据此模型）是非常好理解的。
ER图的连边对偶图是几乎有着相同度分布的图，但具有度相关性，且集聚系数更高。<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
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1103/PhysRevE.67.046107 10.1103/PhysRevE.67.046107]
.[https://en.wikipedia.org/wiki/ArXiv arxiv]:[https://arxiv.org/abs/cond-mat/0212469 cond-mat/0212469]
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/2003PhRvE..67d6107R 2003PhRvE..67d6107R] }}</ref>
==与渗流的关系==
在[http://wiki.swarma.net/index.php/%E6%B8%97%E6%B5%81%E6%A8%A1%E5%9E%8B 渗流理论]中，人们研究有限或无限的图，并随机删除连边（或连接）。因此，ER模型的过程实际就是[https://en.wikipedia.org/wiki/Complete_graph 完全图]上未加权连接的渗流。（所谓渗流，就是在加权的情况下以不同的权重移除节点和（或）连边）。渗流理论有很深的[https://en.wikipedia.org/wiki/Physics 物理学]根源，大部分研究都是在欧几里得空间中的[https://en.wikipedia.org/wiki/Lattice_(group) 格子]上进行的。np=1时，由巨连通分量向小连通分量的转变与这些图类似，但对格子来说，确定临界点很难。物理学家通常将对完全图的研究称为[https://en.wikipedia.org/wiki/Mean_field_theory 平均场理论]，因此ER模型的过程就是渗流的平均场情况。
人们在随机图的渗流上也做了许多重要研究。从物理学家的角度看，这仍是一个平均场模型，所以它常被看成一个通信网络，研究结果常用图的鲁棒性来表示。设一个随机图有n>>1个节点，平均度为<k>。从网络中随机删除1-p’个节点，仅保留一部分p’。存在渗流临界值<math>p'_c=\tfrac{1}{\langle k\rangle}</math>，使得低于该值时，网络变得支离破碎，而高于<math>p'_c</math>时，会有n阶巨连通分量存在。巨连通分量的相对大小P<sub>∞</sub>由下式给出<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= |pages=290–297 |id= |url=http://www.renyi.hu/~p_erdos/1959-11.pdf |accessdate= |quote= }}
</ref><ref name="b01">{{Cite book | last = Bollobás | first = B. | title = Random Graphs | publisher = Cambridge University Press| edition = 2nd | year = 2001|id= |url= |accessdate= |quote=
.[https://en.wikipedia.org/wiki/International_Standard_Book_Number ISBN] [https://en.wikipedia.org/wiki/Special:BookSources/0-521-79722-5 0-521-79722-5]}}
</ref><ref>
{{cite journal |last= Bollobás |first= B. |authorlink= |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|id= |url= |accessdate= |quote=
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1017/S0305004100053056 10.1017/S0305004100053056]
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/1976MPCPS..80..419B 1976MPCPS..80..419B]}}
</ref>
<math> P_\infty= p'[1-\exp(-\langle k \rangle P_\infty)]. \, </math>
==说明==
G(n, p)模型的两个主要假设（连边独立，每条连边可能性相同）可能不适合为某些现实生活中的现象建模。尤其是ER图的度分布没有厚尾，而[https://en.wikipedia.org/wiki/Scale-free_network#Examples 许多实际网络的分布是厚尾的]。此外，与许多社交网络不同，ER图集聚系数较低。其他较好的替代模型可见[[BA网络模型]]（Barabási–Albert model）和[http://wiki.swarma.net/index.php/WS%E5%B0%8F%E4%B8%96%E7%95%8C%E6%A8%A1%E5%9E%8B WS小世界网络模型]（Watts and Strogatz model）。这两个替代模型不是渗流过程，它们分别是生长模型和断边重连模型。Buldyrev（布尔德列夫）等人最近又设计了一种用于交互的[[ER随机图模型]]。<ref>{{cite journal |last1=Buldyrev |first1=S. V. |last2=Parshani |first2=R. |last3=Paul |first3=G. |last4=Stanley |first4=H. E. |last5=Havlin |first5=S. |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|id= |url= |accessdate= |quote=
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1038/nature08932 10.1038/nature08932]
.[https://en.wikipedia.org/wiki/PubMed_Identifier PMID]:[https://www.ncbi.nlm.nih.gov/pubmed/20393559 20393559]
.[https://en.wikipedia.org/wiki/ArXiv arxiv]:[https://arxiv.org/abs/0907.1182 0907.1182]
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/2010Natur.464.1025B 2010Natur.464.1025B] }}</ref>
==历史==
1959年，Edgar Gilbert在研究之前提到的连通性临界值的论文中，首次引入了G(n, p)模型。<ref name="g59">{{cite journal |last= [https://en.wikipedia.org/wiki/Edgar_Gilbert E.N. Gilbert]|year=1959 |title=Random Graphs |journal=Annals of Mathematical Statistics |volume= 30|issue= 4|pages=1141–1144 |id= |url= |accessdate= |quote=
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1214/aoms/1177706098 10.1214/aoms/1177706098] }}</ref>G(n, M)模型则是Erdős和Rényi在他们1959年的论文中提出来的。与Gilbert一样，他们首先研究的是G(n, M)的连通性，1960年，他们做了更详细的分析。
==另请参阅==
*[https://en.wikipedia.org/wiki/Rado_graph 拉多图]（Rado graph），将G(n, p)模型扩展到[https://en.wikipedia.org/wiki/Countability 可数无穷]个顶点的图。与有限的情况不同，这种趋于无穷过程的结果（概率为1）是相同的图，直到同构。
*[https://en.wikipedia.org/wiki/Dual-phase_evolution 双相演化]（Dual-phase evolution）描述了与ER模型相关的性质推动系统中秩序出现的方式。
*[[指数随机图]]（Exponential random graph models）描述的是给定网络统计数据和各种相关参数的“n”节点图的一般概率分布。
*[[随机分块模型]]（Stochastic block model），是ER模型的推广，是具有潜在社团结构的图。
*[[WS小世界模型]]
*[[BA网络模型]]
==参考文献==
<references />
==进一步阅读==
* {{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 = <!--None-->}}
* {{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]]}}
本词条内容翻译自 en.wikipedia.org，遵守 CC3.0协议。
[[Category:旧版词条]]
在[https://en.wikipedia.org/wiki/Graph_theory 图论]的数学理论部分中，'''ER随机图模型（Erdős–Rényi model）'''可指代两个密切相关的[https://en.wikipedia.org/wiki/Random_graph 随机图]生成模型中的任意一个。ER随机图模型的名字源于最早提出上述模型之一的数学家[https://en.wikipedia.org/wiki/Paul_Erd%C5%91s Paul Erdős]（保尔•厄多斯）和[https://en.wikipedia.org/wiki/Alfr%C3%A9d_R%C3%A9nyi Alfréd Rényi]（阿尔弗烈德•瑞利），他们在1959年首次提出了其中一个模型，<ref name="er59"/><ref name="b01"/>而几乎在同时期，[https://en.wikipedia.org/wiki/Edgar_Gilbert Edgar Gilbert]（埃德加•吉尔伯特）独立提出了另外一个模型。<ref name="g59"/>在Erdős和Rényi的模型中，节点集一定、连边数也一定的所有图是等概率的；在Gilbert的模型中，每个连边存在与否有着固定的概率，与其他连边无关。在[https://en.wikipedia.org/wiki/Probabilistic_method 概率方法]中，这两种模型可用来证明满足各种性质的图的存在，也可为几乎所有图的性质提供严格的定义。
==定义==
ER随机图模型有两个密切相关的版本。
*在模型''G''(''n'', ''M'')中，从''n''个节点、''M''个连边构成的所有图的集合里随机选择一个图。例如，在''G''(3, 2)模型中，3个节点和2个连边能构成三种可能的图，每种图的概率为1/3。
*在模型''G''(''n'', ''p'')中，随机连接节点构成一个图。图中每个连边彼此独立，连接的概率为''p''。等价地，拥有''n''个节点、''M''个连边的所有图具有相同的概率
<math>p^M (1-p)^{{n \choose 2}-M}</math>。
此模型中的参数''p''可以看成是加权函数；随着''p''从0增加到1，模型更倾向于包含拥有更多连边的图，而包含拥有较少连边的图的概率则降低。特别地，与''p''=0.5相对应的情况是，在拥有''n''个节点的<math>2^\binom{n}{2}</math>个图中，每个图被选择的概率相等。<br />
我们通常研究节点数''n''趋于无穷时随机图的表现。尽管在这种情况下，''p''和''M''可以固定，但是，它们也可以是关于''n''的函数。例如，命题“''G''(''n'', 2ln(''n'')/''n'')中几乎每个图都是连通的”的意思是，当''n''趋于无穷时，拥有''n''个节点、连边概率为2ln(''n'')/''n''的图连通的概率趋于1。
==两种模型的比较==
''G''(''n'', ''p'')中可能的连边数为<math>\binom{n}{2}p</math>，由[https://en.wikipedia.org/wiki/Law_of_large_numbers 大数定律]，''G''(''n'', ''p'')中的每个图几乎必有大概这么多连边（假设可能的连边数趋于无穷）。因此，粗略的结果是如果pn<sup>2</sup> → ∞，那么当<math>M=\tbinom{n}{2} p</math>随着n的增加而增加时，''G''(''n'', ''p'')将与''G''(''n'', ''M'')有相似的表现。许多图的性质都是这样。如果P是满足对子图序[https://en.wikipedia.org/wiki/Monotonic_function 单调]的任意一种图的性质（即若A是B的子图且A满足P，则B也满足P），那么命题“''G''(''n'', ''p'')中几乎所有图满足P”等价于“<math> G(n, \tbinom{n}{2} p) </math>中几乎所有图满足P”（其中pn<sup>2</sup> → ∞）。例如，当P是[https://en.wikipedia.org/wiki/Connectedness 连通性]时，或P是包含[https://en.wikipedia.org/wiki/Hamiltonian_path 哈密顿圈]的性质时，上述关系就成立。然而，它对非单调性质（如具有偶数连边的性质）未必成立。
如今在实际应用中，''G''(''n'', ''p'')模型更加常用，部分原因是通过连边的独立性进行分析较为容易。
[[File:1280px-Erdos generated network-p0.01.jpg|200px|thumb|right|二项分布ER模型生成的一个图（p=0.01）]]
==G(n, p)的性质==
沿用上述符号，G(n, p)中的一个图平均有<math>\binom{n}{2}p</math>条连边。任意特定节点的度服从[https://en.wikipedia.org/wiki/Binomial_distribution 二项分布]：<ref>{{cite journal |last= Newman |first= Mark. E. J. |authorlink= |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= |pages=026118
|id=
|url=
|accessdate=
|quote=
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1103/PhysRevE.64.026118 10.1103/PhysRevE.64.026118]
.[https://en.wikipedia.org/wiki/ArXiv arxiv]:[https://arxiv.org/abs/cond-mat/0007235 cond-mat/0007235]
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/2001PhRvE..64b6118N 2001PhRvE..64b6118N]}}, Eq. (1)</ref>
<math>P(\deg(v) = k) = {n-1\choose k}p^k(1-p)^{n-1-k},</math>
其中n为图中节点的总数。由于
<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>
故当n很大且np=常数时，服从[https://en.wikipedia.org/wiki/Poisson_distribution 泊松分布]。
在1960年的一篇论文中，Erdős和Rényi<ref name="Erdos1960">{{cite journal |last=Erdős |first=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 |issue=|pages=17–61|id= |url=http://www.renyi.hu/~p_erdos/1960-10.pdf |accessdate= |quote= |doi=}} 这里的概率p指的是<math>N(n) = \tbinom{n}{2} p</math></ref>非常精确地描述了p在不同取值下G(n, p)的表现。其结论有：
*若np<1，则G(n, p)中的一个图几乎一定没有连通分量的大小大于O(log(n))。
*若np=1，则G(n, p)中的一个图几乎必有最大的连通分量，其阶为n <sup>2/3</sup>。
*若np→c>1，其中c为常数，则G(n, p)中的一个图几乎必有唯一的包含节点有限部分的[[巨连通集团]]。没有连通分量会有超过O(log(n))个节点。
*若<math>p<\tfrac{(1-\varepsilon)\ln n} n</math>，则G(n, p)中的一个图几乎必有孤立节点，因而它是不连通的。
*若 <math>p{>}\tfrac{(1+\varepsilon)\ln n} n</math>，则G(n, p)中的一个图几乎一定是连通的。
因此<math> \tfrac{\ln n} n</math>是G(n, p)连通性的重要临界值。
当n趋于无穷大时，还有许多图的性质几乎处处成立。例如，存在k(n)（近似等于2log <sub>2</sub> (n)）使得G(n, 0.5)中最大团的大小几乎必为k(n)或k(n)+1。<ref>{{cite journal
| last = Matula | first = David W.
| date = February 1972
| journal = Notices of the American Mathematical Society
| pages = A-382
| title = The employee party problem
| volume = 19}}</ref>
因此，尽管确定图中最大团的大小是[https://en.wikipedia.org/wiki/NP-complete NP完全的]，但“典型”图中最大团的大小（根据此模型）是非常好理解的。
ER图的连边对偶图是几乎有着相同度分布的图，但具有度相关性，且集聚系数更高。<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
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1103/PhysRevE.67.046107 10.1103/PhysRevE.67.046107]
.[https://en.wikipedia.org/wiki/ArXiv arxiv]:[https://arxiv.org/abs/cond-mat/0212469 cond-mat/0212469]
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/2003PhRvE..67d6107R 2003PhRvE..67d6107R] }}</ref>
==与渗流的关系==
在[http://wiki.swarma.net/index.php/%E6%B8%97%E6%B5%81%E6%A8%A1%E5%9E%8B 渗流理论]中，人们研究有限或无限的图，并随机删除连边（或连接）。因此，ER模型的过程实际就是[https://en.wikipedia.org/wiki/Complete_graph 完全图]上未加权连接的渗流。（所谓渗流，就是在加权的情况下以不同的权重移除节点和（或）连边）。渗流理论有很深的[https://en.wikipedia.org/wiki/Physics 物理学]根源，大部分研究都是在欧几里得空间中的[https://en.wikipedia.org/wiki/Lattice_(group) 格子]上进行的。np=1时，由巨连通分量向小连通分量的转变与这些图类似，但对格子来说，确定临界点很难。物理学家通常将对完全图的研究称为[https://en.wikipedia.org/wiki/Mean_field_theory 平均场理论]，因此ER模型的过程就是渗流的平均场情况。
人们在随机图的渗流上也做了许多重要研究。从物理学家的角度看，这仍是一个平均场模型，所以它常被看成一个通信网络，研究结果常用图的鲁棒性来表示。设一个随机图有n>>1个节点，平均度为<k>。从网络中随机删除1-p’个节点，仅保留一部分p’。存在渗流临界值<math>p'_c=\tfrac{1}{\langle k\rangle}</math>，使得低于该值时，网络变得支离破碎，而高于<math>p'_c</math>时，会有n阶巨连通分量存在。巨连通分量的相对大小P<sub>∞</sub>由下式给出<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= |pages=290–297 |id= |url=http://www.renyi.hu/~p_erdos/1959-11.pdf |accessdate= |quote= }}
</ref><ref name="b01">{{Cite book | last = Bollobás | first = B. | title = Random Graphs | publisher = Cambridge University Press| edition = 2nd | year = 2001|id= |url= |accessdate= |quote=
.[https://en.wikipedia.org/wiki/International_Standard_Book_Number ISBN] [https://en.wikipedia.org/wiki/Special:BookSources/0-521-79722-5 0-521-79722-5]}}
</ref><ref>
{{cite journal |last= Bollobás |first= B. |authorlink= |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|id= |url= |accessdate= |quote=
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1017/S0305004100053056 10.1017/S0305004100053056]
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/1976MPCPS..80..419B 1976MPCPS..80..419B]}}
</ref>
<math> P_\infty= p'[1-\exp(-\langle k \rangle P_\infty)]. \, </math>
==说明==
G(n, p)模型的两个主要假设（连边独立，每条连边可能性相同）可能不适合为某些现实生活中的现象建模。尤其是ER图的度分布没有厚尾，而[https://en.wikipedia.org/wiki/Scale-free_network#Examples 许多实际网络的分布是厚尾的]。此外，与许多社交网络不同，ER图集聚系数较低。其他较好的替代模型可见[[BA网络模型]]（Barabási–Albert model）和[http://wiki.swarma.net/index.php/WS%E5%B0%8F%E4%B8%96%E7%95%8C%E6%A8%A1%E5%9E%8B WS小世界网络模型]（Watts and Strogatz model）。这两个替代模型不是渗流过程，它们分别是生长模型和断边重连模型。Buldyrev（布尔德列夫）等人最近又设计了一种用于交互的[[ER随机图模型]]。<ref>{{cite journal |last1=Buldyrev |first1=S. V. |last2=Parshani |first2=R. |last3=Paul |first3=G. |last4=Stanley |first4=H. E. |last5=Havlin |first5=S. |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|id= |url= |accessdate= |quote=
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1038/nature08932 10.1038/nature08932]
.[https://en.wikipedia.org/wiki/PubMed_Identifier PMID]:[https://www.ncbi.nlm.nih.gov/pubmed/20393559 20393559]
.[https://en.wikipedia.org/wiki/ArXiv arxiv]:[https://arxiv.org/abs/0907.1182 0907.1182]
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/2010Natur.464.1025B 2010Natur.464.1025B] }}</ref>
==历史==
1959年，Edgar Gilbert在研究之前提到的连通性临界值的论文中，首次引入了G(n, p)模型。<ref name="g59">{{cite journal |last= [https://en.wikipedia.org/wiki/Edgar_Gilbert E.N. Gilbert]|year=1959 |title=Random Graphs |journal=Annals of Mathematical Statistics |volume= 30|issue= 4|pages=1141–1144 |id= |url= |accessdate= |quote=
.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1214/aoms/1177706098 10.1214/aoms/1177706098] }}</ref>G(n, M)模型则是Erdős和Rényi在他们1959年的论文中提出来的。与Gilbert一样，他们首先研究的是G(n, M)的连通性，1960年，他们做了更详细的分析。
==另请参阅==
*[https://en.wikipedia.org/wiki/Rado_graph 拉多图]（Rado graph），将G(n, p)模型扩展到[https://en.wikipedia.org/wiki/Countability 可数无穷]个顶点的图。与有限的情况不同，这种趋于无穷过程的结果（概率为1）是相同的图，直到同构。
*[https://en.wikipedia.org/wiki/Dual-phase_evolution 双相演化]（Dual-phase evolution）描述了与ER模型相关的性质推动系统中秩序出现的方式。
*[[指数随机图]]（Exponential random graph models）描述的是给定网络统计数据和各种相关参数的“n”节点图的一般概率分布。
*[[随机分块模型]]（Stochastic block model），是ER模型的推广，是具有潜在社团结构的图。
*[[WS小世界模型]]
*[[BA网络模型]]
==参考文献==
<references />
==进一步阅读==
* {{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 = <!--None-->}}
* {{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]]}}
本词条内容翻译自 en.wikipedia.org，遵守 CC3.0协议。
[[Category:旧版词条]]