查看“︁ER随机图”︁的源代码

{{Not|ER模型}}

在[[图论]]中，'''ER[[随机图]]（Erdős–Rényi random graph）'''是一种网络，以概率p连接N个节点中的每一对节点。ER随机图以[[埃尔德什·帕尔]]和{{tsl|en|Alfréd Rényi|阿尔弗雷德·雷尼}}（Alfréd Rényi）的名字命名。他们在1959年发明了这种模型。<ref name="er59">{{Cite journal|title=On Random Graphs. I|url=http://www.renyi.hu/~p_erdos/1959-11.pdf|last=Erdős|first=P.|last2=Rényi|first2=A.|journal=Publicationes Mathematicae|accessdate=|issue=|year=1959|volume=6|pages=290–297|id=|quote=|archive-date=2020-08-07|archive-url=https://web.archive.org/web/20200807021117/https://www.renyi.hu/~p_erdos/1959-11.pdf|dead-url=no}}</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>同年，Edward Gilbert独立提出了另外一个模型。<ref>{{Cite journal|title=Random Graphs|url=http://projecteuclid.org/euclid.aoms/1177706098|last=Gilbert|first=E. N.|date=1959-12|journal=The Annals of Mathematical Statistics|issue=4|doi=10.1214/aoms/1177706098|volume=30|pages=1141–1144|language=en|issn=0003-4851|access-date=2020-02-10|archive-date=2020-05-09|archive-url=https://web.archive.org/web/20200509005140/https://projecteuclid.org/euclid.aoms/1177706098|dead-url=no}}</ref> 
[[File:Erdos_generated_network-p0.01.jpg|缩略图|''p''&nbsp;=&nbsp;0.01]]在Erdős-Rényi模型中，在顶点集数目相同时，具有固定边数的所有图均具有同等的概率出现。在吉尔伯特（Gilbert）引入的模型中，每个边都有固定的出现概率，并且独立于其他边的概率。这些模型可用于概率方法中，以证明满足各种属性的图的存在，或者对几乎所有图具有属性的含义提供严格的定义。

==定义==
ER随机图主要有两种高度相关的模型。
*在''G''(''n'', ''M'')模型中，确定的图从具有''n''个顶点和''M''条边的所有图集合中等概率随机选择。例如，在''G''(3,&nbsp;2)模型中，具有三个顶点和两条边的图总共有3种，它们每一个都以1/3的概率出现在''G''(3,&nbsp;2)中。当0 ≤ ''M'' ≤ ''N'', ''G''(''n'',''M'') 总共有<math>\tbinom{N}{M}</math>种可能的确定图，每种图出现的概率是<math>1/\tbinom{N}{M}</math><ref name="Random Graphs2">[[Béla Bollobás]], ''Random Graphs'', 1985, Academic Press Inc., London Ltd.</ref>。
*在''G''(''n'', ''p'')模型中，通过随机连接''n''个独立节点构造一个图，每条边出现的概率是''p''，且不同边存在与否互相独立。对于具有''n''个顶点和''M''条边的图，其出现的概率是<math>p^M (1-p)^{{n \choose 2}-M}</math>。由此，''p''越大，''G''中出现边较多的图的概率会上升。

通常在顶点数''n''趋向于无穷大时研究随机图的性质和变化行为。尽管''p''或''M''可以为固定值，但它们也可以依赖''n''的取值。例如，''G''(''n'', 2ln(''n'')/''n'')中的每个图几乎都是连通图；随着''n''趋于无穷大，''G''(''n'', 2ln(''n'')/''n'')中几乎每个图都被连接。

==两种模型的比较==
''G''(''n'', ''p'')的边数[[期望]]值为<math>\tbinom{n}{2}p</math>，因此根据[[大数定理]]，几乎所有''G''(''n'', ''p'')模型中的图的边数都会有<math>\tbinom{n}{2}p</math>个。因此，一个粗略的想法是，如果''pn''<sup>2</sup> → ∞，并且<math>M=\tbinom{n}{2} p</math>，那么随着''n''的增大，''G''(''n'',''p'')的变化行为应该与''G''(''n'', ''M'')类似。

在''pn''<sup>2</sup> → ∞假设的基础上，我们考虑一个图的单调性质''P''（这意味着，若''A''是''B''的子图，并且''A''拥有性质''P'',那么''B''也将拥有性质''P''）；那么“''P''对于几乎所有''G''(''n'', ''p'')成立”等价于“''P''对于几乎所有''G''(''n'', ''M'')成立”。但对于非单调的性质''P''，表述的等价性不一定成立。

事实上，''G''(''n'', ''p'')模型是当今最常用的模型，部分原因是边存在的独立性简化了许多分析。

==G(n,p)的性质==
使用上面的符号，''G''(''n'', ''p'')中的图边数的平均值是<math>\tbinom{n}{2} p</math>。任何特定顶点的[[度 (图论)|度]]服从于[[二项分布]]：<ref>{{cite journal |last= Newman |first= 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|trans-title = 任意度分佈的隨機圖及其應用|journal= Physical Review E|volume=64 |pages=026118 |doi=10.1103/PhysRevE.64.026118|arxiv=cond-mat/0007235|bibcode=2001PhRvE..64b6118N |pmid= 11497662|language = en}}, 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''。

在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|trans-title = 論隨機圖的演化 |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=2020-12-19 |archive-date=2021-02-01 |archive-url=https://web.archive.org/web/20210201163041/https://www.renyi.hu/~p_erdos/1960-10.pdf |dead-url=no |language = en}} The probability ''p'' used here refers there to <math>N(n) = \tbinom{n}{2} p</math></ref>对于不同的''p''精准地描述了''G''(''n'',&nbsp;''p'')变化行为。这些结果包括：

*若''np'' < 1，那么''G''(''n'',&nbsp;''p'')中的图几乎一定没有大小大于O(log(''n''))的[[连通分量 (图论)|连通分支]]。
*若''np'' = 1，那么''G''(''n'',&nbsp;''p'')中的图几乎一定存在一个最大的连通分支，其大小约为''n''<sup>2/3</sup>。
*若''np'' → ''c''&nbsp;>&nbsp;1，''c''为常数，那么''G''(''n'',&nbsp;''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>是一个锋利阈值。

随着''n''趋于无穷大，''G''(''n'',''p'')可以几乎精确地描述图的其他属性。

==渗流理论==
[[完全图]]上的[[渗流理论]]是ER随机图，这也是一种[[平均场论]]。<ref name="er59" /><ref name="b01" /><ref name="Erdos1960"/><ref>{{Cite journal|title=Cliques in random graphs|url=https://www.cambridge.org/core/product/identifier/S0305004100053056/type/journal_article|last=Bollobas|first=B.|last2=Erdős|first2=P.|date=1976-11|journal=Mathematical Proceedings of the Cambridge Philosophical Society|issue=3|doi=10.1017/S0305004100053056|volume=80|pages=419–427|language=en|issn=0305-0041}}</ref>
==参考文献==
{{Reflist|30em}}

{{Authority control}}
[[Category:随机矩阵]]
[[Category:隨機圖]]