“ER随机图模型”的版本间的差异

来自集智百科
跳转到: 导航搜索
两种模型的比较
G(n, p)的性质
第33行: 第33行:
 
*若np<1,则G(n, p)中的一个图几乎一定没有连通分量的大小大于O(log(n))。
 
*若np<1,则G(n, p)中的一个图几乎一定没有连通分量的大小大于O(log(n))。
 
*若np=1,则G(n, p)中的一个图几乎必有最大的连通分量,其阶为n <sup>2/3</sup>。
 
*若np=1,则G(n, p)中的一个图几乎必有最大的连通分量,其阶为n <sup>2/3</sup>。
*若np→c>1,其中c为常数,则G(n, p)中的一个图几乎必有唯一的包含节点有限部分的[https://en.wikipedia.org/wiki/Giant_component  巨连通 分量]。没有连通分量会有超过O(log(n))个节点。
+
*若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>p>\tfrac{(1+\varepsilon)\ln n} n</math>,则G(n, p)中的一个图几乎一定是连通的。
 
*若 <math>p>\tfrac{(1+\varepsilon)\ln n} n</math>,则G(n, p)中的一个图几乎一定是连通的。

2018年8月30日 (四) 14:14的版本

该词条由【普天星相】翻译编辑,由【审校者】审校,【总审校者】总审校,翻译自Wikipedia词条 Erdős–Rényi model


图论的数学理论部分中,ER随机图模型(Erdős–Rényi model)可指代两个密切相关的随机图生成模型中的任意一个。ER随机图模型的名字源于最早提出上述模型之一的数学家Paul Erdős(保尔•厄多斯)和Alfréd Rényi(阿尔弗烈德•瑞利),他们在1959年首次提出了其中一个模型,[1][2]而几乎在同时期,Edgar Gilbert(埃德加•吉尔伯特)独立提出了另外一个模型。[3]在Erdős和Rényi的模型中,节点集一定、连边数也一定的所有图是等概率的;在Gilbert的模型中,每个连边存在与否有着固定的概率,与其他连边无关。在概率方法中,这两种模型可用来证明满足各种性质的图的存在,也可为几乎所有图的性质提供严格的定义。

目录

定义

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

  • 在模型G(n, M)中,从n个节点、M个连边构成的所有图的集合里随机选择一个图。例如,在G(3, 2)模型中,3个节点和2个连边能构成三种可能的图,每种图的概率为1/3。
  • 在模型G(n, p)中,随机连接节点构成一个图。图中每个连边彼此独立,连接的概率为p。等价地,拥有n个节点、M个连边的所有图具有相同的概率
 p^M (1-p)^{{n \choose 2}-M}

此模型中的参数p可以看成是加权函数;随着p从0增加到1,模型更倾向于包含拥有更多连边的图,而包含拥有较少连边的图的概率则降低。特别地,与p=0.5相对应的情况是,在拥有n个节点的2^\binom{n}{2}个图中,每个图被选择的概率相等。

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

两种模型的比较

G(n, p)中可能的连边数为\binom{n}{2}p,由大数定律G(n, p)中的每个图几乎必有大概这么多连边(假设可能的连边数趋于无穷)。因此,粗略的结果是如果pn2 → ∞,那么当M=\tbinom{n}{2} p随着n的增加而增加时,G(n, p)将与G(n, M)有相似的表现。许多图的性质都是这样。如果P是满足对子图序单调的任意一种图的性质(即若A是B的子图且A满足P,则B也满足P),那么命题“G(n, p)中几乎所有图满足P”等价于“ G(n, \tbinom{n}{2} p) 中几乎所有图满足P”(其中pn2 → ∞)。例如,当P是连通性时,或P是包含哈密顿圈的性质时,上述关系就成立。然而,它对非单调性质(如具有偶数连边的性质)未必成立。 如今在实际应用中,G(n, p)模型更加常用,部分原因是通过连边的独立性进行分析较为容易。

二项分布ER模型生成的一个图(p=0.01)

G(n, p)的性质

沿用上述符号,G(n, p)中的一个图平均有\binom{n}{2}p条连边。任意特定节点的度服从二项分布[4]

P(\deg(v) = k) = {n-1\choose k}p^k(1-p)^{n-1-k},

其中n为图中节点的总数。由于

P(\deg(v) = k) \to \frac{(np)^k \mathrm{e}^{-np}}{k!} \quad \text{ as } n \to \infty \text{ and } np = \text{ constant },

故当n很大且np=常数时,服从泊松分布。 在1960年的一篇论文中,Erdős和Rényi[5]非常精确地描述了p在不同取值下G(n, p)的表现。其结论有:

  • 若np<1,则G(n, p)中的一个图几乎一定没有连通分量的大小大于O(log(n))。
  • 若np=1,则G(n, p)中的一个图几乎必有最大的连通分量,其阶为n 2/3
  • 若np→c>1,其中c为常数,则G(n, p)中的一个图几乎必有唯一的包含节点有限部分的巨连通集团。没有连通分量会有超过O(log(n))个节点。
  • p<\tfrac{(1-\varepsilon)\ln n} n,则G(n, p)中的一个图几乎必有孤立节点,因而它是不连通的。
  • 解析失败 (<math_output_error>): p>\tfrac{(1+\varepsilon)\ln n} n

,则G(n, p)中的一个图几乎一定是连通的。 因此 \tfrac{\ln n} n是G(n, p)连通性的重要临界值。 当n趋于无穷大时,还有许多图的性质几乎处处成立。例如,存在k(n)(近似等于2log 2 (n))使得G(n, 0.5)中最大团的大小几乎必为k(n)或k(n)+1。[6] 因此,尽管确定图中最大团的大小是NP完全的,但“典型”图中最大团的大小(根据此模型)是非常好理解的。 ER图的连边对偶图是几乎有着相同度分布的图,但具有度相关性,且集聚系数更高。[7]

与渗流的关系

渗流理论中,人们研究有限或无限的图,并随机删除连边(或连接)。因此,ER模型的过程实际就是完全图上未加权连接的渗流。(所谓渗流,就是在加权的情况下以不同的权重移除节点和(或)连边)。渗流理论有很深的物理学根源,大部分研究都是在欧几里得空间中的格子上进行的。np=1时,由巨连通分量向小连通分量的转变与这些图类似,但对格子来说,确定临界点很难。物理学家通常将对完全图的研究称为平均场理论,因此ER模型的过程就是渗流的平均场情况。 人们在随机图的渗流上也做了许多重要研究。从物理学家的角度看,这仍是一个平均场模型,所以它常被看成一个通信网络,研究结果常用图的鲁棒性来表示。设一个随机图有n>>1个节点,平均度为<k>。从网络中随机删除1-p’个节点,仅保留一部分p’。存在渗流临界值p'_c=\tfrac{1}{\langle k\rangle},使得低于该值时,网络变得支离破碎,而高于p'_c时,会有n阶巨连通分量存在。巨连通分量的相对大小P由下式给出[5][1][2][8]

 P_\infty= p'[1-\exp(-\langle k \rangle P_\infty)]. \, 

说明

G(n, p)模型的两个主要假设(连边独立,每条连边可能性相同)可能不适合为某些现实生活中的现象建模。尤其是ER图的度分布没有厚尾,而许多实际网络的分布是厚尾的。此外,与许多社交网络不同,ER图集聚系数较低。其他较好的替代模型可见BA模型(Barabási–Albert model)和WS小世界网络模型(Watts and Strogatz model)。这两个替代模型不是渗流过程,它们分别是生长模型和断边重连模型。Buldyrev(布尔德列夫)等人最近又设计了一种用于交互的ER网络模型。[9]

历史

1959年,Edgar Gilbert在研究之前提到的连通性临界值的论文中,首次引入了G(n, p)模型。[3]G(n, M)模型则是Erdős和Rényi在他们1959年的论文中提出来的。与Gilbert一样,他们首先研究的是G(n, M)的连通性,1960年,他们做了更详细的分析。

另请参阅

  • 拉多图(Rado graph),将G(n, p)模型扩展到可数无穷个顶点的图。与有限的情况不同,这种趋于无穷过程的结果(概率为1)是相同的图,直到同构。
  • 双相演化(Dual-phase evolution)描述了与ER模型相关的性质推动系统中秩序出现的方式。
  • 指数随机图模型(Exponential random graph models)描述的是给定网络统计数据和各种相关参数的“n”节点图的一般概率分布。
  • 随机块模型(Stochastic block model),是ER模型的推广,是具有潜在社团结构的图。
  • WS小世界网络模型
  • BA模型


参考文献

  1. 1.0 1.1 Erdős, P.; Rényi, A. (1959). "On Random Graphs. I". Publicationes Mathematicae 6: 290–297. http://www.renyi.hu/~p_erdos/1959-11.pdf.
  2. 2.0 2.1 Bollobás, B. (2001). Random Graphs (2nd ed.). Cambridge University Press. ".ISBN 0-521-79722-5"
  3. 3.0 3.1 E.N. Gilbert (1959). "Random Graphs". Annals of Mathematical Statistics 30 (4): 1141–1144. ".doi:10.1214/aoms/1177706098"
  4. Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. (2001). "Random graphs with arbitrary degree distributions and their applications". Physical Review E 64: 026118. ".doi:10.1103/PhysRevE.64.026118 .arxiv:cond-mat/0007235 .bibcode:2001PhRvE..64b6118N", Eq. (1)
  5. 5.0 5.1 Erdős, P.; Rényi, A. (1960). "On the evolution of random graphs". Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences] 5: 17–61. http://www.renyi.hu/~p_erdos/1960-10.pdf. 这里的概率p指的是N(n) = \tbinom{n}{2} p
  6. Matula, David W. (February 1972). "The employee party problem". Notices of the American Mathematical Society 19: A-382.
  7. Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (April 2003). "Generating correlated networks from uncorrelated ones". Physical Review E 67 (4): 046107 .doi:10.1103/PhysRevE.67.046107 .arxiv:cond-mat/0212469 .bibcode:2003PhRvE..67d6107R.
  8. Bollobás, B.; Erdős, P. (1976). "Cliques in Random Graphs". Mathematical Proceedings of the Cambridge Philosophical Society 80 (3): 419–427. ".doi:10.1017/S0305004100053056 .bibcode:1976MPCPS..80..419B"
  9. Buldyrev, S. V.; Parshani, R.; Paul, G.; Stanley, H. E.; Havlin, S. (2010). "Catastrophic cascade of failures in interdependent networks". Nature 464 (7291): 1025–8. ".doi:10.1038/nature08932 .PMID:20393559 .arxiv:0907.1182 .bibcode:2010Natur.464.1025B"

进一步阅读

本词条内容翻译自 en.wikipedia.org,遵守 CC3.0协议。

个人工具
名字空间
操作
导航
工具箱