交通地理与网络科学/随机图

随机图

随机图是由一些随机过程生成的图。随机图理论是由 Erdős 和 Rényi 在 1950 年代的一系列论文中创立的。

在大多数随机图模型中，顶点的数量是固定的，它们之间的边以某种随机方式放置。最简单的方法之一是固定边的数量，并将它们均匀地随机放置在所有可能的顶点对中。换句话说，我们生成一个具有 v 个顶点和 e 个边的图的概率分布，它们都具有相同的概率。该模型通常称为 G(v,e)，其中 v 表示顶点的数量，e 表示边的数量。

虽然 G(v,e) 似乎是一个简单的模型，但事实证明，获得我们感兴趣的一些重要属性并不容易。因此，已经提出了另一个略有不同的模型，并且大多数数学工作都是在被称为 G(v,p) 的模型上进行的，其中 v 表示顶点的数量，p 表示在每对顶点之间存在边的概率。 换句话说，G(v,p) 模型中的图是通过扫描 n 个顶点的每对顶点并以概率 p 在它们之间放置边来构建的。

属性

G(v,p) 中存在 e 个边的概率为

$p^{e}(1-p)^{{\binom {v}{2}}-e}$

例如，考虑一个随机图 G(3,0.8)，该图具有一个、两个或三个边的概率如下所示

随机图 G(3,0.8)

具有 e 个边的图的概率

$P(e)={\binom {\binom {v}{2}}{e}}p^{e}(1-p)^{{\binom {v}{2}}-e}$

具有 e 个边的随机图数量（v 个顶点）

$N(e)={\binom {\binom {v}{2}}{e}}$

例如，有 15 个不同的随机图，它们有 4 个顶点和 2 个边

具有 4 个顶点和 2 个边的随机图

度数的期望值

${\binom {v}{2}}p$

期望度数值

$c=(v-1)p$

度数分布

$p_{k}={\binom {v-1}{k}}p^{k}(1-p)^{v-1-k}$

在平均度数近似恒定的大型网络（例如社交网络）中，度数分布变为泊松分布

聚类系数

聚类系数衡量网络的传递性。它被定义为一个顶点的两个网络邻居也是彼此邻居的概率。由于在 G(v,p) 中，每对顶点都以概率 p 相连，并且与其他任何事无关，因此聚类系数 C 为

$C=p={\frac {c}{v-1}}$

巨型连通分量

随机图研究的一个重要特征是当顶点数量v变大时，图是如何演化的。更具体地说，如果我们知道当v趋于无穷大时，图中的大多数顶点都是连通的，那么这意味着存在一个连通分量的增长速度与图的增长速度相当。这个连通分量被称为巨型连通分量。可以证明，当且仅当平均度大于1时，存在巨型连通分量。