随机图

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
打豆豆讨论 | 贡献2020年11月21日 (六) 16:33的版本 →‎模型
跳到导航 跳到搜索


在数学领域中,随机图 Random Graph是指图上的概率分布的一般术语。随机图可以简单地用概率分布表示,也可以用生成它们的随机过程表示[1][2]。随机图的理论处于图论和概率论的交汇点上。从数学的角度来看,随机图可以用来回答有关典型图的性质的问题。在所有需要对复杂网络进行建模的领域都能看到它的实际应用——由于它反映了在不同领域遇到的不同类型的复杂网络,许多随机图模型就此被人们所熟知。在数学上,随机图几乎完全指的是 Erdős-Rényi 随机图模型。在其他情况下,任何图形模型都可以称为随机图。

模型

从一组 n 个孤立的顶点开始,在它们之间随机添加连续的边,这样就得到一个随机图。这个领域的研究的目的是确定在什么阶段图形的特殊性质可能出现[3]。不同的随机图模型在图上产生不同的概率分布。最常见的研究是由埃德加 · 吉尔伯特提出的,表示[math]\displaystyle{ G(n,M) }[/math] ,其中每个可能的边独立出现的概率为[math]\displaystyle{ 0 \lt p\lt 1 }[/math]。获得任意一个 m 边随机图的概率是 [math]\displaystyle{ p^m (1-p)^(N-m) }[/math] ,记号是 [math]\displaystyle{ N=\tbinom{n}{2} }[/math][4]

一个相关性强的模型,Erdős-Rényi模型表示[math]\displaystyle{ G(n,M) }[/math] ,给每一个正好有M条边的图赋予等概率。当[math]\displaystyle{ 0≤ M ≤ N }[/math]时,[math]\displaystyle{ G(n,M) }[/math]具有 [math]\displaystyle{ \tbinom{N}{M} }[/math] 元素,且每个元素都以概率[math]\displaystyle{ 1/\tbinom{N}{M} }[/math] 出现。后一个模型可以看作是随机图过程[math]\displaystyle{ \tilde{G}_n }[/math]某个特定时间(M)的一个快照,这个时间(M)是从 [math]\displaystyle{ n }[/math] 个顶点开始没有边的一个随机过程,每个步骤均匀地从缺失的边集中选择一个新的边。

如果我们从一个无限的顶点集合开始,然后再次让每个可能的边以概率[math]\displaystyle{ 0\lt p\lt 1 }[/math]独立出现,那么我们得到一个对象 [math]\displaystyle{ G }[/math] 称为无限随机图 Infinite Graph。除了在 [math]\displaystyle{ p = 0 }[/math]或1的平凡情况下,这样的 [math]\displaystyle{ G }[/math] 在大多数情况下肯定具有以下性质:

[math]\displaystyle{ v }[/math] 中,给定任何 [math]\displaystyle{ n + m }[/math] 个元素,[math]\displaystyle{ a_1,\ldots, a_n,b_1,\ldots, b_m \in V }[/math] 中有一个顶点[math]\displaystyle{ c }[/math],它与每个 [math]\displaystyle{ a_1,\ldots,a_n }[/math] 相邻,并且不与任何 [math]\displaystyle{ b_1,\ldots,b_m }[/math] 相邻。

结果表明,如果顶点集是可数的,那么在同构 Isomorphism意义下,只有一个图具有这个性质,即 Rado 图。因此,任何可数无限随机图几乎可以肯定是 Rado 图,由于这个原因,有时被简称为随机图。然而,对于不可数图 Uncountable Graph类似的结果是不正确的,不可数图中有许多不同构图 Nonisomorphic Graph满足上述性质。

另一个模型,概括了吉尔伯特的随机图模型,是随机点积模型 Random Dot-product Model。一个随机点积图 Random Dot-product Graph 将每个顶点与一个实向量相关联。任意顶点 [math]\displaystyle{ u }[/math][math]\displaystyle{ v }[/math]之间的边 [math]\displaystyle{ uv }[/math] 的概率是它们各自向量的点积 [math]\displaystyle{ u·v }[/math] 的某个函数。

网络转移矩阵 NetWork Probability Matrix通过边概率对随机图进行建模,这些边概率代表给定的边存在一个特定的时间段的概率。这个模型可以扩展到有向和无向,加权和无权,以及静态或动态的图形结构。

对于 Msomething pN,其中 N 是可能的最大边数,两个最广泛使用的模型,[math]\displaystyle{ G(n,M) }[/math][math]\displaystyle{ G(n,p) }[/math]在大多数情况下是可互换的[5]

随机正则图 Random Regular Graph是一种特殊情况,其性质可能与一般随机图不同。

一旦我们有了一个随机图的模型,图上的每个函数都变成了一个随机变量。对这个模型的研究是为了确定,或者至少估计一个属性可能发生的概率。

术语

在随机图的上下文中,“几乎每一个”这个术语指的是一系列空间和概率,使得出错概率趋于零。

性质

随机图理论研究随机图的典型性质,即从特定分布中抽取的图的高概率性质。例如,我们可以要求一个给定的值 [math]\displaystyle{ n }[/math][math]\displaystyle{ p }[/math]来表示[math]\displaystyle{ G(n,p) }[/math] 连接的概率。在研究这些问题时,研究人员往往集中在随机图的趋近行为上——各种概率收敛到的值变得非常大。渗流理论 Percolation Theory刻画了随机图,特别是无穷大图的连通性 Connectedness

'渗流 Percolation 与图形(也称为网络)的鲁棒性 Robustness有关。给定一个随机图形,其中的节点是 [math]\displaystyle{ n }[/math] 和一个平均度 [math]\displaystyle{ \langle k\rangle }[/math] 。接下来我们随机移除一部分概率为 [math]\displaystyle{ 1-p }[/math] 的节点,只留下一部分概率为 [math]\displaystyle{ p }[/math] 的节点。存在一个临界渗透阈值 Critical Percolation Threshold[math]\displaystyle{ p_c=\tfrac{1}{\langle k\rangle} }[/math],当低于这个临界渗透阈值,网络变得支离破碎,而高于临界渗透阈值 [math]\displaystyle{ p_c }[/math] 的网络则存在一个巨大的连接元件 Connected Component(图论)[6][7]

局部渗滤 Localized Percolation指的是去除一个节点的邻居、次近邻等。直到网络中概率为 [math]\displaystyle{ 1-p }[/math] 的一部分节点被移除。结果表明,对于服从泊松分布的随机图,其度分布为 [math]\displaystyle{ p_c=\tfrac{1}{\langle k\rangle} }[/math] ,和随机删除是一样的。对于其他类型的度分布[math]\displaystyle{ p_c }[/math],局部攻击和随机攻击是不同的。[8]

(阈值函数 Threshold Functions, [math]\displaystyle{ \tilde G }[/math] 的演化)

随机图在概率方法中得到了广泛的应用,它试图证明具有一定性质的图的存在性。通过 正则引理 Szemerédi Regularity Lemma,随机图上一个性质的存在常常意味着几乎所有图上该性质的存在。

在随机正则图中,[math]\displaystyle{ G(n,r-reg) }[/math][math]\displaystyle{ r=r(n) }[/math][math]\displaystyle{ r- }[/math]正则图的集合,其中 [math]\displaystyle{ n }[/math][math]\displaystyle{ m }[/math] 是自然数,[math]\displaystyle{ 3 \le r\lt n }[/math][math]\displaystyle{ rn = 2m }[/math] 是偶数。

[math]\displaystyle{ G^n }[/math] 中,图 [math]\displaystyle{ G }[/math] 的度序列仅取决于集合中的边数。

[math]\displaystyle{ V_n^{(2)} = \left \{ij \ : \ 1 \leq j \leq n, i \neq j \right \} \subset V^{(2)}, \qquad i=1, \cdots, n. }[/math]

如果随机图中的边 [math]\displaystyle{ M }[/math][math]\displaystyle{ G_M }[/math] 大到足以确保几乎每个 [math]\displaystyle{ G_M }[/math] 的最小阶数至少为1,那么几乎每个 [math]\displaystyle{ G }[/math] 是连通的,如果 [math]\displaystyle{ n }[/math] 是偶数,则几乎每个 [math]\displaystyle{ G_M }[/math] 都有一个完美匹配 Perfect Matching。特别是,在几乎每个随机图中,最后一个孤立点消失的那一刻,图会变连通。

几乎每个偶数顶点上的最小度提高到1的图或稍大于 [math]\displaystyle{ \tfrac{n}{4}\log(n) }[/math] 边且概率接近1的随机图都能确保图有完全匹配 Complete Matching,但最多只有一个顶点。

对于某些常数 [math]\displaystyle{ c }[/math] ,几乎所有带有 [math]\displaystyle{ n }[/math] 顶点和至少 [math]\displaystyle{ cn\log(n) }[/math] 边的标记图都是 哈密尔顿环 Hamiltonian Cycle的。在概率趋于1的情况下,将最小度增加到2的特殊边会使图成为哈密尔顿图。

在图变换下,随机图的性质可以改变或保持不变。例如,Mashaghi A.等人证明了将随机图转换为其 边-对偶图 Edge-Dual Graphs(或 线图 Liner Graph)的变换会产生一个度分布几乎相同,但具有 度相关性 Degree Correlations 和显著更高的 聚类系数 Clustering Coefficent的图的集合。[9]

着色

给定一个 n 阶随机图 G,其顶点 V(G) = {1,... ,n } ,通过关于颜色数的贪婪算法 Greedy Algorithm,可以用颜色1,2... (如果顶点1与顶点2不相邻,则顶点1与顶点2为染相同的颜色,否则染不同的颜色,以此类推。).

给定一个 q 颜色的随机图的真染色数,称为它的染色多项式 Chormatic Polynomial(到目前为止还没有确定的正式名称)。利用符号模式匹配算法 Algorithm Based On Symbolic Pattern Matching ,对参数为 n 、边数为 m 或连接概率为 p 的随机图的染色多项式零点的标度进行了实验研究。[10]

随机树图

随机树是由随机过程组成的树状图。在 n 阶和 M(n)大小的随机图的大范围内,k 阶树分量个数的分布是渐近泊松的。随机树的类型包括均匀生成树 Uniform Spanning Tree、随机最小生成树 Random Minimal Tree、随机二叉树 Random Binary Tree、树、快速检索随机树 Rapidly Exploring Random Tree、布朗树 Brownian Tree和随机森林 Random Forest

条件随机图

考虑一个给定的随机图模型定义在概率空间上[math]\displaystyle{ (\Omega,\mathcal{F},P) }[/math] ,并且让 [math]\displaystyle{ \mathcal{P}(G) : \Omega \rightarrow R^{m} }[/math] 是一个值是实数的函数,它在 [math]\displaystyle{ \Omega }[/math] 中为每个图赋值一个 m 属性的向量。

对于 [math]\displaystyle{ R^{m} }[/math] 中的一个固定的 [math]\displaystyle{ \mathbf{p} }[/math] ,条件随机图是这样的模型,在这个模型中,机率量测 [math]\displaystyle{ p }[/math] 给所有图分配零概率,例如“ [math]\displaystyle{ \mathcal{P}(G)\neq\mathbf{p} }[/math]

特殊情况是条件均匀随机图 Conditionally Uniform Graph,其中 [math]\displaystyle{ p }[/math] 给所有具有指定性质的图赋予相等的概率。它们可以被看作是 Erdős–Rényi 模型 G(nm)的一个推广,当条件信息不一定是边的个数 M,而是其他任意图性质 [math]\displaystyle{ \mathcal{P}(G) }[/math] 时。在这种情况下,很少有分析结果可用,就需要通过模拟来获得平均性质的经验分布。

相互依存图

在相互依存图中,一个网络(图)中的节点依赖于其他网络来工作。因此,一个或多个图中的故障会导致图之间的级联故障 Cascading Failures,从而引起网络突然崩溃。[11][12]

历史

最早使用随机图模型的是海伦·霍尔·詹宁斯和雅各布·莫雷诺,他们在1938年提出了一个“偶然社会记录模型”(一个有向的 Erdős-Rényi 模型)[13] ,用来比较他们的网络数据中的回传链接的比例和随机模型。另一个被称为“随机网络 Random Net”的随机图模型应用是1951年 Solomonoff 和 Rapoport 使用的有向图模型,这些有向图具有固定的出度,并且随机选择附加到其他顶点。[14]

随机图的Erdős–Rényi 模型是由Paul Erdős和Alfréd Rényi于1959年发表的论文《随机图论》中首次提出的,Gilbert 在他的论文《随机图论》中独立定义了这一模型。[15][16]

另请参见

References 参考文献

  1. Bollobás, Béla (2001). Random Graphs (2nd ed.). Cambridge University Press. 
  2. Frieze, Alan; Karonski, Michal (2015). Introduction to Random Graphs. Cambridge University Press. 
  3. Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
  4. Béla Bollobás, Probabilistic Combinatorics and Its Applications, 1991, Providence, RI: American Mathematical Society.
  5. Bollobas, B. and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003
  6. Newman, M. E. J. (2010). Networks: An Introduction. Oxford. 
  7. Reuven Cohen and Shlomo Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press. http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php. 
  8. Shao, Shuai; Huang, Xuqing; Stanley, H Eugene; Havlin, Shlomo (2015). "Percolation of localized attack on complex networks". New Journal of Physics. 17 (2): 023049. arXiv:1412.3124. Bibcode:2015NJPh...17b3049S. doi:10.1088/1367-2630/17/2/023049. ISSN 1367-2630.
  9. Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003). "Generating correlated networks from uncorrelated ones". Phys. Rev. E. 67 (46107): 046107. arXiv:cond-mat/0212469. Bibcode:2003PhRvE..67d6107R. doi:10.1103/PhysRevE.67.046107. PMID 12786436.
  10. Van Bussel, Frank; Ehrlich, Christoph; Fliegner, Denny; Stolzenberg, Sebastian; Timme, Marc (2010). "Chromatic Polynomials of Random Graphs". J. Phys. A: Math. Theor. 43 (17): 175002. arXiv:1709.06209. Bibcode:2010JPhA...43q5002V. doi:10.1088/1751-8113/43/17/175002.
  11. Buldyrev, Sergey V.; Parshani, Roni; Paul, Gerald; Stanley, H. Eugene; Havlin, Shlomo (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–1028. arXiv:1012.0206. Bibcode:2010Natur.464.1025B. doi:10.1038/nature08932. ISSN 0028-0836. PMID 20393559.
  12. Gao, Jianxi; Buldyrev, Sergey V.; Stanley, H. Eugene; Havlin, Shlomo (2011). "Networks formed from interdependent networks". Nature Physics. 8 (1): 40–48. Bibcode:2012NatPh...8...40G. CiteSeerX 10.1.1.379.8214. doi:10.1038/nphys2180. ISSN 1745-2473.
  13. Moreno, Jacob L; Jennings, Helen Hall (Jan 1938). "Statistics of Social Configurations". Sociometry. 1 (3/4): 342–374. doi:10.2307/2785588.
  14. Solomonoff, Ray; Rapopst, Anatol (June 1951). "Connectivity of random nets". Bulletin of Mathematical Biophysics. 13 (2): 107–117. doi:10.1007/BF02478357.
  15. Erdős, P. Rényi, A (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p. 290–297 [1]
  16. Gilbert, E. N. (1959), "Random graphs", Annals of Mathematical Statistics, 30 (4): 1141–1144, doi:10.1214/aoms/1177706098.

编者推荐

集智相关文章

ER随机图模型

随机图(random graph),顾名思义,是由随机过程产生的图,具有不确定性。这一理论处于图论和概率论的交叉地带,主要研究经典随机图的性质。

集智相关课程

巴拉巴西网络科学

本课程中,我们邀请了汪小帆、赵海兴、许小可、史定华、陈清华、张江、狄增如、陈关荣、樊瑛、刘宗华这十个来自六大不同高校、在网络科学领域耕耘许久的教授作为导师,依据教材框架,各有侧重地为我们共同勾勒出整个学科的美丽图景,展示这个学科的迷人魅力,指引这个学科的灿烂未来。

复杂网络的基本模型

本课程中,将详细介绍复杂网络的四个基本模型:规则网、随机图、小世界网络、Scale-Free 网络。