ER随机图模型 - 版本历史

2020年11月21日 (六) 11:13 薄荷

2020-11-21T11:13:13Z

薄荷：/* 编者推荐 */

2020-05-02T03:32:08Z

编者推荐

费米子：/* 文献推荐 */

2020-04-28T08:16:48Z

文献推荐

费米子：/* 编者推荐 */

2020-04-28T08:16:21Z

编者推荐

费米子：/* 历史 */

2020-04-28T08:15:33Z

历史

费米子：/* 两种模型的比较 */

2020-04-28T08:14:24Z

两种模型的比较

乐多多：/* 集智文章推荐 */

2020-04-28T08:09:34Z

集智文章推荐

乐多多：/* 另请参阅 */

2020-04-28T08:07:46Z

另请参阅

乐多多：/* 说明 */

2020-04-28T07:59:42Z

说明

乐多多：/* 与渗流的关系 */

2020-04-28T07:57:39Z

与渗流的关系

@@ 第3行： / 第3行： @@
 |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随机图模型有两个密切相关的版本。

@@ 第103行： / 第103行： @@
 [[file:随机图.png|250px|thumb|right|  随机图 (平均度2.833 平均最短路径长度2.109 聚类系数0.167)]]
 通过生成随机图模型和可伸缩算法生成综合网络是网络分析中的一个经常性使用的工具，它为实际网络中各种属性的统计分析提供了一个有根据的基础。本文用Chung－Lu模型说明了如何生成具有幂律分布的大型随机图。此外，这篇文章提供了模型参数的显式公式，以便生成满足对最小、最大和平均期望度的行为的若干要求，并且具有若干期望特性的随机图，包括具有任意指定指数大于2的幂律度分布，存在一个巨大的组件并且没有潜在的孤立节点。
 ===课程推荐===

@@ 第101行： / 第101行： @@
 ====[http://arxiv.org/abs/1910.11341 基于Chung-Lu随机图模型生成大规模无标度网络]====
 通过生成随机图模型和可伸缩算法生成综合网络是网络分析中的一个经常性使用的工具，它为实际网络中各种属性的统计分析提供了一个有根据的基础。本文用Chung－Lu模型说明了如何生成具有幂律分布的大型随机图。此外，这篇文章提供了模型参数的显式公式，以便生成满足对最小、最大和平均期望度的行为的若干要求，并且具有若干期望特性的随机图，包括具有任意指定指数大于2的幂律度分布，存在一个巨大的组件并且没有潜在的孤立节点。
 ===课程推荐===

@@ 第111行： / 第111行： @@
 本课程沿着几何的线路重新梳理复杂网络，包括ER随机网、小世界网络、无标度网络，网络的分形特征等。之后，该课程重点讲述如何利用真实的网络数据来重构系统的空间几何特征。
+</br>
+</br>
 ----

@@ 第74行： / 第74行： @@
 ==历史==
 年，Edgar Gilbert在研究之前提到的连通性临界值的论文中，首次引入了<math>G(n,p)</math>模型。<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><math>G(n,M)</math>模型则是Erdős和Rényi在他们1959年的论文中提出来的。与Gilbert一样，他们首先研究的是G(n, M)的连通性，1960年，他们做了更详细的分析。
+.[https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1214/aoms/1177706098 10.1214/aoms/1177706098] }}</ref><math>G(n,M)</math>模型则是Erdős和Rényi在他们1959年的论文中提出来的。与Gilbert一样，他们首先研究的是<math>G(n, M)</math>的连通性，1960年，他们做了更详细的分析。
 ==另请参阅==

@@ 第18行： / 第18行： @@
 ==两种模型的比较==
 <math>G(n,p)</math>中可能的连边数为<math>\binom{n}{2}p</math>，由[https://en.wikipedia.org/wiki/Law_of_large_numbers 大数定律]，<math>G(n,p)</math>中的每个图几乎必有大概这么多连边（假设可能的连边数趋于无穷）。因此，粗略的结果是如果<math>pn^2 →∞</math>，那么当<math>M=\tbinom{n}{2} p</math>随着<math>n</math>的增加而增加时，<math>G(n,p)</math>将与<math>G(n,M)</math>有相似的表现。许多图的性质都是这样。如果P是满足对子图序[https://en.wikipedia.org/wiki/Monotonic_function 单调]的任意一种图的性质（即若<math>A</math>是<math>B</math>的子图且<math>A</math>满足<math>P</math>，则<math>B</math>也满足<math>P</math>），那么命题“<math>G(n,p)</math>中几乎所有图满足<math>P</math>”等价于“<math> G(n, \tbinom{n}{2} p) </math>中几乎所有图满足<math>P</math>”（其中<math>pn^2 →∞</math>）。
@@ 第25行： / 第26行： @@
 如今在实际应用中，<math>G(n,p)</math>模型更加常用，部分原因是通过连边的独立性进行分析较为容易。
 ==<math>G(n,p)</math>的性质==

@@ 第78行： / 第78行： @@
 ==另请参阅==
-*[https://en.wikipedia.org/wiki/Rado_graph 拉多图]（Rado graph），将G(n, p)模型扩展到[https://en.wikipedia.org/wiki/Countability 可数无穷]个顶点的图。与有限的情况不同，这种趋于无穷过程的结果（概率为1）是相同的图，直到同构。
+*[https://en.wikipedia.org/wiki/Rado_graph 拉多图] Rado graph，将<math>G(n,p)</math>模型扩展到[https://en.wikipedia.org/wiki/Countability 可数无穷]个顶点的图。与有限的情况不同，这种趋于无穷过程的结果（概率为1）是相同的图，直到同构。
-*[https://en.wikipedia.org/wiki/Dual-phase_evolution 双相演化]（Dual-phase evolution）描述了与ER模型相关的性质推动系统中秩序出现的方式。
+*[https://en.wikipedia.org/wiki/Dual-phase_evolution 双相演化] Dual-phase evolution 描述了与ER模型相关的性质推动系统中秩序出现的方式。
-*[https://en.wikipedia.org/wiki/Exponential_random_graph_models 指数随机图]（Exponential random graph models）描述的是给定网络统计数据和各种相关参数的“n”节点图的一般概率分布。
+*[https://en.wikipedia.org/wiki/Exponential_random_graph_models 指数随机图] Exponential random graph models 描述的是给定网络统计数据和各种相关参数的“n”节点图的一般概率分布。
-*[https://en.wikipedia.org/wiki/Stochastic_block_model 随机分块模型]（Stochastic block model），是ER模型的推广，是具有潜在社团结构的图。
+*[https://en.wikipedia.org/wiki/Stochastic_block_model 随机分块模型] Stochastic block model ，是ER模型的推广，是具有潜在社团结构的图。
 *[[WS小世界模型]]
 *[[BA网络模型]]

@@ 第70行： / 第70行： @@
 ==说明==
-<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|
+<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| doi = 10.1038/nature08932 |pmid=20393559|arxiv=0907.1182 |bibcode=2010Natur.464.1025B }}</ref>
 ==历史==

@@ 第65行： / 第65行： @@
 .[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|
+{{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= |doi= 10.1017/S0305004100053056 |bibcode=1976MPCPS..80..419B}}
 </ref>
 :<math> P_\infty= p'[1-\exp(-\langle k \rangle P_\infty)]. \, </math>