ER随机图

  提示：此条目页的主题不是ER模型。

在图论中，ER随机图（Erdős–Rényi random graph）是一种网络，以概率p连接N个节点中的每一对节点。ER随机图以埃尔德什·帕尔和阿尔弗雷德·雷尼（Alfréd Rényi）的名字命名。他们在1959年发明了这种模型。同年，Edward Gilbert独立提出了另外一个模型。

p = 0.01

在Erdős-Rényi模型中，在顶点集数目相同时，具有固定边数的所有图均具有同等的概率出现。在吉尔伯特（Gilbert）引入的模型中，每个边都有固定的出现概率，并且独立于其他边的概率。这些模型可用于概率方法中，以证明满足各种属性的图的存在，或者对几乎所有图具有属性的含义提供严格的定义。

定义

ER随机图主要有两种高度相关的模型。

• 在G(n, M)模型中，确定的图从具有n个顶点和M条边的所有图集合中等概率随机选择。例如，在G(3, 2)模型中，具有三个顶点和两条边的图总共有3种，它们每一个都以1/3的概率出现在G(3, 2)中。当0 ≤ M ≤ N, G(n,M) 总共有${\tbinom {N}{M}}$种可能的确定图，每种图出现的概率是$1/{\tbinom {N}{M}}$。
• 在G(n, p)模型中，通过随机连接n个独立节点构造一个图，每条边出现的概率是p，且不同边存在与否互相独立。对于具有n个顶点和M条边的图，其出现的概率是$p^{M}(1-p)^{{n \choose 2}-M}$。由此，p越大，G中出现边较多的图的概率会上升。

通常在顶点数n趋向于无穷大时研究随机图的性质和变化行为。尽管p或M可以为固定值，但它们也可以依赖n的取值。例如，G(n, 2ln(n)/n)中的每个图几乎都是连通图；随着n趋于无穷大，G(n, 2ln(n)/n)中几乎每个图都被连接。

两种模型的比较

G(n, p)的边数期望值为${\tbinom {n}{2}}p$，因此根据大数定理，几乎所有G(n, p)模型中的图的边数都会有${\tbinom {n}{2}}p$个。因此，一个粗略的想法是，如果pn² → ∞，并且$M={\tbinom {n}{2}}p$，那么随着n的增大，G(n,p)的变化行为应该与G(n, M)类似。

在pn² → ∞假设的基础上，我们考虑一个图的单调性质P（这意味着，若A是B的子图，并且A拥有性质P,那么B也将拥有性质P）；那么“P对于几乎所有G(n, p)成立”等价于“P对于几乎所有G(n, M)成立”。但对于非单调的性质P，表述的等价性不一定成立。

事实上，G(n, p)模型是当今最常用的模型，部分原因是边存在的独立性简化了许多分析。

G(n,p)的性质

使用上面的符号，G(n, p)中的图边数的平均值是${\tbinom {n}{2}}p$。任何特定顶点的度服从于二项分布：

$P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},$

其中n是图中顶点的数目。因为

$P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}\quad {\text{ as }}n\to \infty {\text{ and }}np={\text{constant}},$

此分布为泊松分布对于较大的n和常数np。

在1960年的论文中，Erdős和Rényi对于不同的p精准地描述了G(n, p)变化行为。这些结果包括：

• 若np < 1，那么G(n, p)中的图几乎一定没有大小大于O(log(n))的连通分支。
• 若np = 1，那么G(n, p)中的图几乎一定存在一个最大的连通分支，其大小约为n^2/3。
• 若np → c > 1，c为常数，那么G(n, p)中的一个图几乎必有唯一的包含结点有限部分的巨型连通分支，其他连通分支不会包含超过O(log(n))个顶点。
• 若$p<{\tfrac {(1-\varepsilon )\ln n}{n}}$，那么G(n, p)中的一个图几乎必有孤立点，因此这个图是不连通的。
• 若$p>{\tfrac {(1+\varepsilon )\ln n}{n}}$，那么G(n, p)几乎一定连通。

因此${\tfrac {\ln n}{n}}$是一个锋利阈值。

随着n趋于无穷大，G(n,p)可以几乎精确地描述图的其他属性。

渗流理论

完全图上的渗流理论是ER随机图，这也是一种平均场论。