随机图算法

ER随机图算法

Erdös-Rényi随机图模型是最简单的图模型。这个简单的模型具有经过验证的网络属性，并且是比较实际现实世界图属性的良好基准。
此随机图模型有两个变体：

1. $G_{np}$: 具有 $n$ 个节点的无向图，并且每条边 $(u,v)$ 出现的概率符合概率为 $p$ 的独立同步分布
2. $G_{nm}$: 具有n个节点的无向图，随机地均匀地选择 $m$ 条边

请注意，$G_{np}$ 和 $ G_{nm}$图不是唯一确定的，而是随机产生的。 在ER生成算法中，通过n个节点和边的生成概率P来生成的无向图不是唯一的，如下图所示：

根据上图所示，我们可以根据n个节点和概率p来生成不同的边来生成一个随机的图。

ER图的相关属性

相关属性

ER Graph是Erdos-Renyi Graph的缩写，它是最简单、最符合直觉的随机图，常用 $G_{np}$ 表示，$n$ 表示节点数，$p$ 表示一个给定的概率值。ER Graph是一张无向图，有 $n$ 个节点，每条边的连接概率是 $p$，且各条边是否连接是彼此独立的。

换句话说，给定 $n$ 和 $p$，我们就可以生成一张ER图了。

注意，同样的n和p，生成的两张ER图可能是不一样的。

下面来计算ER图的四个度量指标。

ER图的度分布

ER图 $G_{np}$ 的度分布符合二项分布，设 $P(k)$ 表示具有度为 $k$ 的节点数，则

$$P(k)=\left(\begin{array}{c} n-1 \\ k \end{array}\right) p^{k}(1-p)^{n-1-k}$$

如果一个节点的度为 $k$，那么在图中，除了他自身之外就有 $N-1$ 个节点中的 $k$ 个节点需要和其相连接。对于该节点而言，产生一条边的概率为 $p$，并且边的产生是独立同分布的，那么也就是说该点生成 $k$ 条边的概率为 $p^k$，剩余 $n-1-k$ 个节点与该节点没有产生边，那么也就是说其概率为$(1−p)^{n−1−k}$。

二项分布的均值为：

$$\bar{k}=p(n-1)$$

二项分布的方差为：

$$\sigma^{2}=p(1-p)(n-1)$$

而其标准差和均值的比值为：

$$\frac{\sigma}{\bar{k}}=\left[\frac{1-p}{p} \frac{1}{n-1}\right]^{1 / 2} \approx \frac{1}{(n-1)^{\frac{1}{2}}}$$

二项式分布的一个特性是，根据数字定律，随着网络规模的增加，度的分布原来越集中，分布变得越来越狭窄。也就是说，图中的节点的概率分布越来越接近，节点的度在 $k$ 附近。如果图具有无限个节点，则所有节点将具有相同的度数。（大数分布）

[注意]我们在这里讨论的度分布是概率意义上的，可以理解为，在已知n和p的前提下，针对所有可能的ER图计算度分布，上一讲给出的度分布定义是频率意义上的，是针对某一个确定的图的，这是两者的区别所在。其他度量指标也需要以概率视角来理解。

ER图的聚类系数

聚类系数的计算公式为 $C_{i}=\frac{2e_{i}}{k_{i}(k_{i}-1)}$ 其中 $e_{i}$ 是节点 $i$ 的相邻节点之间的边数。因为在 $G_{np}$ 中边出现的概率符合概率为 $p$ 的独立同分布，所以图 $G_{np}$ 中期望的 $e_{i}$ 为

$$\mathbb{E}\left[e_{i}\right]=p \frac{k_{i}\left(k_{i}-1\right)}{2}$$

这是因为 $\frac {k_{i}(k_{i}-1)} {2}$ 是度为 $k_{i}$ 的节点 $i$ 的邻居的不同对的数量，并且每一对以概率 $p$ 相连接。

因此，期望的聚类系数为：

$$\mathbb{E}\left[C_{i}\right]=\frac{p \cdot k_{i}\left(k_{i}-1\right)}{k_{i}\left(k_{i}-1\right)}=p=\frac{\bar{k}}{n-1} \approx \frac{\bar{k}}{n}$$

$\bar{k}$ 表示平均度，从上面公式可以得到，$G_{np}$ 的聚类系数非常小，如果我们以固定的平均度生成 $\bar{k}$ 一个非常非常大的图，那么 $C$ （即聚类系数）随着规模 $n$ 的增大而减小。$\mathbb{E}\left[C_{i}\right] \rightarrow 0$ as $n \rightarrow \infty$。

ER图的路径长度

这里涉及扩展性（expansion）的定义及相关定理，暂时无法给出讲解。只能给出一个定性的结论：在 $n*p=const$ 的前提下，平均路径长度与 $n$ 呈对数关系。

ER图的连通分量

首先，我们先给出关于概率p增长和图的关系，如下图所示：
从上面的图中，可以确定以下几种情况：

• 当 $p$ 的值为$\frac{1}{(n-1)}$ 的时候，会出现巨大的连通子图
• 当 $p$ 的值为 $\frac{c}{(n-1)}$ 的时候，会生成大量的孤立点
• 当 $p$ 的值为 $\frac{log(n)}{(n-1)}$ 的时候，孤立节点的数量会减少
• 当 $p$ 的值为 $\frac{2*log(n)}{(n-1)}$ 的时候，孤立节点消失
• 当 $p$ 的值为1的时候，随机图是一个完全图

$p$ 的均值为 $\frac{k}{(n-1)}$，设定一个阈值 $\epsilon$，有如下的关系：

• $k=1-\epsilon$，所有的子图的规模均在$\Omega(\log n)$
• $\bar{k}=1+\epsilon$，则存在1个连通组件的大小为 $\Omega(n)$，而所有其他组件大小都为 $\Omega(\log n)$
  用图来展示一下效果，有：
  

扩展因子

首先定义扩展系数的概念。图 $G(V,E)$ 对于 $\forall S \subset V$ 具有扩展系数 $\alpha$ ，剩下的边的数量 $S \geq \alpha \cdot \min (|S|,|V \backslash S|)$。
用一个图来展示一下：

扩展系数回答了一个问题，即“如果我们随机选择一组节点，那么有多少条边要离开该组？” 扩展系数是一种鲁棒性的度量：要断开 $\ell \ell$ 个节点，必须切断 $≥\alpha⋅\ell$边缘。
同样的，我们也可以认为图 $G(V,E)$ 具有扩展系数 $\alpha$

$$\alpha=\min _{S \subset V} \frac{\# \text { edges leaving } S}{\min (|S|,|V \backslash S|)}$$

多个随机图结构

对一个原始的随机图，我们可以将其拆分成多个随机子图，拆分的过程满足我们上面定义的扩展因子的中的公式定义，如下图所示：

关于扩展系数的一个重要事实是，在具有 $n$ 个节点且扩展系数为 $\alpha$ 的图中，对于所有的节点对，将有 $O((\log n)/\alpha)$ 条路径连接他们。对于一个随机的 $G_{np}$ 图，$\log n>n p>c$，所以，$diam(G_{np})=O(\log n/ \log(np))$，因此，我们可以看到随机图具有良好的扩展性，因此BFS访问所有节点的步数为对数。

我们将原始的n个节点的随机图可以拆分成三个子图，其中子图中的边的数量关系满足我们之前的数量定义。我们以左边的第一图中某一个节点开始，我们寻找其和其他子图中的节点之间的路径，我们不难发现，从某一个节点开始，这种查找的过程很类似于一个树结构。如下图所示：

根据树的特性，两个节点之间的路径的长度是一种对数的长度，也就是说整个图中任意的两个节点之间的最大的路径长度为 $O((\log (n)) / \alpha)$。因此 $G_{np}$ 的路径长度为 $O(\log n)$。尽管随机图中节点数量上涨的很快，但是节点的之间的最短距离的上涨速度通过对数规律，其上涨的速度是很慢的。其上涨的规律如下图所示：

真实网络和ER随机图的关系总结

真实网络和ER随机图的关系

• 对于一个大的连通图而言，其分布和随机图相似
• 对于平均的路径长度，真实网络和随机图相似
• 聚类系数和度的分布和随机图有所不同

ER随机图的局限性

• 随机图的度分布和真实网络的度分布不同
• 真实网络的大的连通子图不是通过随机图的变形来实现的
• 由于聚类系数过小，很难去确定一个局部结构
• 真实网络并不是一个随机图，我们只能通过这种随机生成的方式去逼近模拟

随机图的作用

• 作为一种比较标准，与真实网络进行比较
• 使我们能够了解到，随机过程会影响到图中的某个属性