更改

{{#seo:

{{#seo:

|keywords=图论,集智,随机图，小世界模型

|keywords=图论,集智,随机图，小世界模型

|description=随机图，集智

|description=ER随机图，集智,Erdős–Rényi model

}}

}}

在[[图论]]的数学理论部分中，'''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随机图模型 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随机图模型有两个密切相关的版本。

ER随机图模型有两个密切相关的版本。

我们通常研究节点数<math>n</math>趋于无穷时随机图的表现。尽管在这种情况下，<math>p</math>和<math>M</math>可以固定，但是，它们也可以是关于<math>n</math>的函数。例如，命题“<math>G(n, 2ln(n)/n)</math>中几乎每个图都是连通的”的意思是，当<math>n</math>趋于无穷时，拥有<math>n</math>个节点、连边概率为<math>2ln'n)/n</math>的图连通的概率趋于1。

我们通常研究节点数<math>n</math>趋于无穷时随机图的表现。尽管在这种情况下，<math>p</math>和<math>M</math>可以固定，但是，它们也可以是关于<math>n</math>的函数。例如，命题“<math>G(n, 2ln(n)/n)</math>中几乎每个图都是连通的”的意思是，当<math>n</math>趋于无穷时，拥有<math>n</math>个节点、连边概率为<math>2ln(n)/n</math>的图连通的概率趋于1。

==两种模型的比较==

==两种模型的比较==

==与渗流的关系==

==与渗流的关系==

在[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模型的过程就是渗流的平均场情况。

在[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) 格子]上进行的。<math>np=1</math>时，由巨连通分量向小连通分量的转变与这些图类似，但对格子来说，确定临界点很难。物理学家通常将对完全图的研究称为[https://en.wikipedia.org/wiki/Mean_field_theory 平均场理论]，因此ER模型的过程就是渗流的平均场情况。

 

 

人们在随机图的渗流上也做了许多重要研究。从物理学家的角度看，这仍是一个平均场模型，所以它常被看成一个通信网络，研究结果常用图的鲁棒性来表示。设一个随机图有<math>n>>1</math>个节点，平均度为<math><k></math>。从网络中随机删除<math>1-p'</math>个节点，仅保留一部分<math>p'</math>。存在渗流临界值<math>p'_c=\tfrac{1}{\langle k\rangle}</math>，使得低于该值时，网络变得支离破碎，而高于<math>p'_c</math>时，会有<math>n</math>阶巨连通分量存在。巨连通分量的相对大小<math>P_∞ </math>由下式给出:<ref name="Erdos1960" /><ref name="er59">

人们在随机图的渗流上也做了许多重要研究。从物理学家的角度看，这仍是一个平均场模型，所以它常被看成一个通信网络，研究结果常用图的鲁棒性来表示。设一个随机图有<math>n>>1</math>个节点，平均度为<math><k></math>。从网络中随机删除<math>1-p'</math>个节点，仅保留一部分<math>p'</math>。存在渗流临界值<math>p'_c=\tfrac{1}{\langle k\rangle}</math>，使得低于该值时，网络变得支离破碎，而高于<math>p'_c</math>时，会有<math>n</math>阶巨连通分量存在。巨连通分量的相对大小<math>P_∞ </math>由下式给出:<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= }}

{{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= }}

==说明==

==说明==

<math>G(n,p)</math>模型的两个主要假设（连边独立，每条连边可能性相同）可能不适合为某些现实生活中的现象建模。尤其是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=  

<math>G(n,p)</math>模型的两个主要假设（连边独立，每条连边可能性相同）可能不适合为某些现实生活中的现象建模。尤其是ER图的度分布没有厚尾，而[https://en.wikipedia.org/wiki/Scale-free_network#Examples 许多实际网络的分布是厚尾的]。此外，与许多社交网络不同，ER图集聚系数较低。其他较好的替代模型可见[[BA网络模型]] Barabási–Albert model和[[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/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/PubMed_Identifier PMID]:[https://www.ncbi.nlm.nih.gov/pubmed/20393559 20393559]