随机图

在数学中，随机图是指由随机过程产生的图^[1]。随机图的理论处于图论和概率论的交叉地带，主要研究各种经典随机图的性质。随机图的实际应用主要在复杂网络中所有建模领域中。第一批关于随机图的结果是保罗·埃尔德什和阿尔弗雷德·雷尼在1959年至1966年的一系列论文中提出的ER随机图。^[2]。在其他语义中，任何图模型都可以被称为随机图。

定义与模型

随机图的“随机”二字体现在边的分布上。一个随机图实际上是将给定的顶点之间随机地连上边。假设将一些纽扣散落在地上，并且不断随机地将两个纽扣之间系上一条线，这样就得到一个随机图的例子^[3]。边的产生可以依赖于不同的随机方式，这样就产生了不同的随机图模型。最常被讨论的模型是Edgar Gilbert提出的 G(n,p)模型：p为边概率，即G中任意两个顶点之间相连的概率。在这种模型下，一个特定的图出现的概率为${\displaystyle p^{m}(1-p)^{N-m}}$，其中${\displaystyle N={\tbinom {n}{2}}}$^[4].

与G(n,p)模型紧密相关的模型是埃尔德什和雷尼共同研究的ER模型，表示为G(n,M)：拥有M个边的图出现概率是相同的。当0 ≤ M ≤ N, G(n,M) 总共有${\displaystyle {\tbinom {N}{M}}}$种可能的确定图，每种图出现的概率是${\displaystyle 1/{\tbinom {N}{M}}}$^[5]。若将随机图的生成过程描述为一个随机过程：开始时有n个顶点且互相没有边连接，每次迭代都从缺失的边集合中均匀的选择一条新边；那么ER模型可以被看作是随机图生成过程中迭代M次时的一个快照。

另一种随机图模型叫做内积模型，是GilbertG(n,p)模型的推广形式。内积模型的机制是对每一个顶点指定一个实系数的向量，而两个顶点之间是否连接的概率则是它们的向量的内积的函数。

定义更广泛的随机图模型的方法是定义所谓的网络概率矩阵。这个矩阵的系数就是边概率，因此详细刻画了随机图的模型。网络概率矩阵模型可以推广到有向图和带有权重的图。

随机正则图是随机图中特殊的一类，它的性质可能会与一般的随机图不同。

性质

随着边概率的不同，随机图可能会呈现不同的属性。对于最典型的ER模型，埃尔德什与雷尼研究了当顶点数目 n 趋向于正无穷大时，ER随机图的性质与概率 p 之间的关系。他们发现，当 p 的值越过某些门槛时，ER随机图的性质会发生突然的改变^[3]。ER随机图的许多性质都是突然涌现的，比如说，当 p 的值小于某个特殊值之前，随机图具有某个性质的可能性等于0，但当 p 的值大于这个特殊值以后，随机图具有这个性质的可能性会突然变成1。

举例来说，当概率 p 大于某个临界值 p_c(n) 后，生成的随机图几乎必然是连通的（概率等于1）。也就是说，对于散落在地上的 n 个纽扣，如果你以这样的概率 p 将两个纽扣之间系上线，那么你拿起一颗纽扣时就几乎能带起所有的纽扣了^[3]。

随机树

主条目：随机树

随机树是随机图的一类。如同随机图一样，随机树是一个经由随机过程建立的树或有向树。随机数的类型包括随机最小生成树、随机二叉树、随机二叉查找树和随机森林等。

当顶点数n较大时，顶点数目为k的随机树的分布接近于泊松分布。

随机树的一种生成方法是利用随机置换。首先生成一个 ${\displaystyle \scriptstyle {\frac {n}{2}}(n-1)}$ 阶随机置换函数，将 ${\displaystyle \scriptstyle {\frac {n}{2}}(n-1)}$ 个可能连起来的边标上 1 至 ${\displaystyle \scriptstyle {\frac {n}{2}}(n-1)}$ 的序号。然后按照从小到大的序号排列为原本没有边的图一一添加边。添加第 ${\displaystyle \scriptstyle k}$ 条边时，如果发现添加后会导致图中出现一个圈，那么就放弃添加这条边，而开始添加第 ${\displaystyle \scriptstyle k+1}$ 条边。最后得到的就是一个随机树^[6]。

参见

• 玻色-爱因斯坦凝聚
• 腔体法
• 复杂网络
• 小世界网络
• 无尺度网络
• ER随机图

参考来源

1. Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press
2. 第一篇论文发表于1959年，标题为“On Random Graphs I”（《论随机图 I》），Publ. Math. Debrecen 6, p290.
3. 汪小帆,李翔,陈关荣. 《复杂网络理论及其应用》. 清华大学出版社. 2006. ISBN 9787302125051 （中文）.
4. Béla Bollobás, Probabilistic Combinatorics and Its Applications, 1991, Providence, RI: American Mathematical Society.
5. Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
6. Alexandr Kazda. The Random Tree Process. Center for Discrete Mathematics and Theoretical Computer Science. [2011-04-24]. （原始内容存档于2016-03-04）.