ER随机图

图论中,ER随机图(Erdős–Rényi random graph)是一种网络,以概率p连接N个节点中的每一对节点。ER随机图以埃尔德什·帕尔阿尔弗雷德·雷尼英语Alfréd Rényi(Alfréd Rényi)的名字命名。他们在1959年发明了这种模型。[1][2]同年,Edward Gilbert独立提出了另外一个模型。[3]

p = 0.01

在Erdős-Rényi模型中,在顶点集数目相同时,具有固定边数的所有图均具有同等的概率出现。在吉尔伯特(Gilbert)引入的模型中,每个边都有固定的出现概率,并且独立于其他边的概率。这些模型可用于概率方法中,以证明满足各种属性的图的存在,或者对几乎所有图具有属性的含义提供严格的定义。

定义

ER随机图主要有两种高度相关的模型。

  • G(n, M)模型中,确定的图从具有n个顶点和M条边的所有图集合中等概率随机选择。例如,在G(3, 2)模型中,具有三个顶点和两条边的图总共有3种,它们每一个都以1/3的概率出现在G(3, 2)中。当0 ≤ MN, G(n,M) 总共有 种可能的确定图,每种图出现的概率是 [4]
  • G(n, p)模型中,通过随机连接n个独立节点构造一个图,每条边出现的概率是p,且不同边存在与否互相独立。对于具有n个顶点和M条边的图,其出现的概率是 。由此,p越大,G中出现边较多的图的概率会上升。

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

两种模型的比较

G(n, p)的边数期望值为 ,因此根据大数定理,几乎所有G(n, p)模型中的图的边数都会有 个。因此,一个粗略的想法是,如果pn2 → ∞,并且 ,那么随着n的增大,G(n,p)的变化行为应该与G(n, M)类似。

pn2 → ∞假设的基础上,我们考虑一个图的单调性质P(这意味着,若AB的子图,并且A拥有性质P,那么B也将拥有性质P);那么“P对于几乎所有G(n, p)成立”等价于“P对于几乎所有G(n, M)成立”。但对于非单调的性质P,表述的等价性不一定成立。

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

G(n,p)的性质

使用上面的符号,G(n, p)中的图边数的平均值是 。任何特定顶点的服从于二项分布[5]

 

其中n是图中顶点的数目。因为

 

此分布为泊松分布对于较大的n和常数np

在1960年的论文中,Erdős和Rényi[6]对于不同的p精准地描述了G(np)变化行为。这些结果包括:

  • np < 1,那么G(np)中的图几乎一定没有大小大于O(log(n))的连通分支
  • np = 1,那么G(np)中的图几乎一定存在一个最大的连通分支,其大小约为n2/3
  • npc > 1,c为常数,那么G(np)中的一个图几乎必有唯一的包含结点有限部分的巨型连通分支,其他连通分支不会包含超过O(log(n))个顶点。
  •  ,那么G(n, p)中的一个图几乎必有孤立点,因此这个图是不连通的。
  •  ,那么G(n, p)几乎一定连通。

因此 是一个锋利阈值。

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

渗流理论

完全图上的渗流理论是ER随机图,这也是一种平均场论[1][2][6][7]

参考文献

  1. ^ 1.0 1.1 Erdős, P.; Rényi, A. On Random Graphs. I (PDF). Publicationes Mathematicae. 1959, 6: 290–297. (原始内容存档 (PDF)于2020-08-07). 
  2. ^ 2.0 2.1 Bollobás, B. Random Graphs 2nd. Cambridge University Press. 2001. ISBN 0-521-79722-5. 
  3. ^ Gilbert, E. N. Random Graphs. The Annals of Mathematical Statistics. 1959-12, 30 (4): 1141–1144 [2020-02-10]. ISSN 0003-4851. doi:10.1214/aoms/1177706098. (原始内容存档于2020-05-09) (英语). 
  4. ^ Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
  5. ^ Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. Random graphs with arbitrary degree distributions and their applications [任意度分佈的隨機圖及其應用]. Physical Review E. 2001, 64: 026118. Bibcode:2001PhRvE..64b6118N. PMID 11497662. arXiv:cond-mat/0007235 . doi:10.1103/PhysRevE.64.026118 (英语). , Eq. (1)
  6. ^ 6.0 6.1 Erdős, P.; Rényi, A. On the evolution of random graphs [論隨機圖的演化] (PDF). Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences]. 1960, 5: 17–61 [2020-12-19]. (原始内容存档 (PDF)于2021-02-01) (英语).  The probability p used here refers there to  
  7. ^ Bollobas, B.; Erdős, P. Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society. 1976-11, 80 (3): 419–427. ISSN 0305-0041. doi:10.1017/S0305004100053056 (英语).