Erdos-Renyi随机图的生成方式及其特性

1 随机图生成简介

1.1 GnpGnp和GnmGnm

以下是我学习《CS224W：Machine Learning With Graphs》^[1]中随机图生成部分的笔记，部分补充内容参考了随机算法教材^[2]和wiki^[3]。随机图生成算法应用非常广泛，在NetworkX网络数据库中也内置的相关算法。我觉得做图机器学习的童鞋很有必要了解下。

Erdos-Renyi随机图^[4]以两位著名的匈牙利数学家P.Erdős和A. Rényi的名字命名的，是生成随机无向图最简单和常用的方法，包括以下两种紧密相关的变体：

• GnpGnp: 拥有nn个节点，且边(u,v)(u,v)以独立同分布的概率pp产生的无向图

• GnmGnm: 拥有nn个节点，且其中mm条边按照均匀分布采样生成的无向图。

(八卦：最常被讨论的GnpGnp其实是Gilbert^[5]提出的，不过由于P.Erdős和A. Rényi提出的GnmGnm更早一些，后来就将两种都统称Erdos-Renyi随机图了)

1.2 生成方法

• GnpGnp：按某个次序考虑(n2)(n2)条可能边中的每一条，然后以概率pp独立地往图上添加每条边。
• GnmGnm: 均匀选取(n2)(n2)条可能边中的一条，并将其添加为图的边，然后再独立且均匀随机地选取剩余(n2)−1(n2)−1可能边中的一条，并将其添加到图中，直到mm边为止（可以证明，虽然是无放回采样，但是每次采样是独立的，任意一种mm条边的选择结果是等概率的）。

值得一提的是，在GnpGnp中，一个有nn个顶点的图具有mm条边的概率满足分布：

((n2)m)pm(1−p)(n2)−m

((n2)m)pm(1−p)(n2)−m

该分布式二项分布，边的期望数为(n2)p(n2)p，每个顶点度的期望为(n−1)p(n−1)p。

1.3 两种方法比较

• 两者的相同点：节点数量都为nn，且边数量的期望为p(n2)p(n2)；

• 两者的区别：GnpGnp的可能边数量在(n2)p(n2)p上下波动，而GnmGnm则恒定有mm条边。

2 GnpGnp随机图

2.1 只用nn和pp够吗？

nn和pp并不能完全决定一个图。我们发现即使给定nn和pp，图也有许多实现形式。如当n=10,p=1/6n=10,p=1/6时，就可能产生如下的图：

2.2 GnpGnp的图属性

接下来我们考虑给定nn和pp，图GnpGnp所可能拥有的不属性，包括度分布p(k)p(k)、聚类系数CC、连通分量、平均最短路径长度ˉhh¯等。

• 度分布

GnpGnp的度分布是满足二项分布的，我们设p(k)p(k)为任意节点度数的概率分布函数。当节点数nn足够大时，p(k)p(k)可视为对度为kk的节点所占比例的近似。我们有：

p(k)=(n−1k)pk(1−p)n−1−k(k=0,1,...,n−1)

其中(n−1k)表示从n−1个节点中选k个节点，p为边产生的概率。该分布是二项分布，所以我们有以下均值和方差：

ˉk=(n−1)pσ2=(n−1)p(1−p)

二项分布的离散分布图像如下图所示：

当n足够大时，二项分布可以用正态分布去近似。

• 聚类系数

我们设

Ci=ei(ki2)

此处ei为节点i邻居之间的边数，ki为节点i的度，(ki2)为节点i的邻居间可能存在的边总数。由于Gnp中边都按照概率p独立同分布，我们有

E(ei)=(ki2)p

其中p为节点i的邻居间两两结合的概率，(ki2)为节点i的邻居间可能存在的边总数。

我们进一步可推知聚类系数：

C=E(Ci)=E(ei)(ki2)=p=ˉkn−1≈ˉkn

• 连通分量

图Gnp的图结构会随着p变化，如下图所示：

观察可知其中当巨大连通分量（gaint connected component）出现时，p=1/(n−1)，此时平均度ˉk=(n−1)p=1。

平均度k=1−ε(即小于1)时，所有的连通分量大小为Ω(logn)；

平均度k=1+ε（即高于1）时，存在一个连通分量大小为Ω(n)，其它的大小为Ω(logn)。且每个节点在期望值上至少有一条边。

如下图所示为Gnp中，n=100000，ˉk=(n−1)p=0.5,...,3 时的模拟实验图像：

根据模拟实验，在Gnp中，平均度大于1时，巨大连通分量恰好出现。

• 平均最短路径长度

Erdos-Renyi随机图即使扩展到很大，仍然可以保证节点之间只有几跳(hops)的距离，如下所示为图的平均最短路径长度ˉh随节点数量变化的关系图：

可以看到平均最短路径长度ˉh随着节点数量n增长并满足O(logn)的增长阶。

2.3 真实网络和Gnp的对比

相似点： 存在大的连通分量，平均最短路径长度

不同点： 聚类系数，度分布

在实际应用中，随机图模型可能有以下问题：

• 度分布可能和真实网络不同，毕竟真实网络不是随机的。
• 真实网络中巨大连通分量的出现可能不具有规律性。
• 可能不存在局部的聚类结构，以致聚类系数太小。

3 代码库

NetworkX中内置了Erdos-Renyi随机图的生成函数，包括Gnp和Gnm。就是需要注意Gnp的API^[6]是

erdos_renyi_graph(n, p, seed=None, directed=False)

该API与nx.binomial_graph 、nx.gnp_random_graph作用是相同的。

而Gnm的API^[7]是

nm_random_graph(n, m, seed=seed, directed=False)

故大家在实际使用中要注意区分。

参考

• [1] http://web.stanford.edu/class/cs224w/

• [2]
  Mitzenmacher M, Upfal E. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis[M]. Cambridge university press, 2017.

• [3] https://zh.m.wikipedia.org/zh-hans/随机图

• [4]
  Erdős P, Rényi A. On the evolution of random graphs[J]. Publ. Math. Inst. Hung. Acad. Sci, 1960, 5(1): 17-60.

• [5]
  Gilbert E N. Random graphs[J]. The Annals of Mathematical Statistics, 1959, 30(4): 1141-1144.

• [6] https://networkx.org/documentation/stable/reference/generated/networkx.generators.random_graphs.erdos_renyi_graph.html

• [7] https://networkx.org/documentation/stable/auto_examples/graph/plot_erdos_renyi.html?highlight=renyi

• 1 随机图生成简介
•     1.1 G_{np}G_{np}和G_{nm}G_{nm}
•     1.2 生成方法
•     1.3 两种方法比较
• 2 G_{np}G_{np}随机图
•     2.1 只用nn和pp够吗？
•     2.2 G_{np}G_{np}的图属性
•     2.3 真实网络和G_{np}G_{np}的对比
• 3 代码库
• 参考

__EOF__