在图论 中，ER随机图 （Erdős–Rényi random graph） 是一种网络，以概率p连接N个节点中的每一对节点。ER随机图以埃尔德什·帕尔 和阿尔弗雷德·雷尼 [ 1] [ 2] [ 3]
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 ) 总共有
(
N
M
)
{\displaystyle {\tbinom {N}{M}}}
1
/
(
N
M
)
{\displaystyle 1/{\tbinom {N}{M}}}
[ 4]
在G (n , p )模型中，通过随机连接n 个独立节点构造一个图，每条边出现的概率是p ，且不同边存在与否互相独立。对于具有n 个顶点和M 条边的图，其出现的概率是
p
M
(
1
−
p
)
(
n
2
)
−
M
{\displaystyle 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 )的边数期望 值为
(
n
2
)
p
{\displaystyle {\tbinom {n}{2}}p}
大数定理 ，几乎所有G (n , p )模型中的图的边数都会有
(
n
2
)
p
{\displaystyle {\tbinom {n}{2}}p}
pn 2 → ∞，并且
M
=
(
n
2
)
p
{\displaystyle M={\tbinom {n}{2}}p}
n 的增大，G (n ,p )的变化行为应该与G (n , M )类似。
在pn 2 → ∞假设的基础上，我们考虑一个图的单调性质P （这意味着，若A 是B 的子图，并且A 拥有性质P ,那么B 也将拥有性质P ）；那么“P 对于几乎所有G (n , p )成立”等价于“P 对于几乎所有G (n , M )成立”。但对于非单调的性质P ，表述的等价性不一定成立。
事实上，G (n , p )模型是当今最常用的模型，部分原因是边存在的独立性简化了许多分析。
使用上面的符号，G (n , p )中的图边数的平均值是
(
n
2
)
p
{\displaystyle {\tbinom {n}{2}}p}
度 服从于二项分布 ：[ 5]
P
(
deg
(
v
)
=
k
)
=
(
n
−
1
k
)
p
k
(
1
−
p
)
n
−
1
−
k
,
{\displaystyle P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}
其中n 是图中顶点的数目。因为
P
(
deg
(
v
)
=
k
)
→
(
n
p
)
k
e
−
n
p
k
!
as
n
→
∞
and
n
p
=
constant
,
{\displaystyle 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[ 6] 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
<
(
1
−
ε
)
ln
n
n
{\displaystyle p<{\tfrac {(1-\varepsilon )\ln n}{n}}}
G (n , p )中的一个图几乎必有孤立点，因此这个图是不连通的。
若
p
>
(
1
+
ε
)
ln
n
n
{\displaystyle p>{\tfrac {(1+\varepsilon )\ln n}{n}}}
G (n , p )几乎一定连通。 因此
ln
n
n
{\displaystyle {\tfrac {\ln n}{n}}}
随着n 趋于无穷大，G (n ,p )可以几乎精确地描述图的其他属性。
Erdős, P.; Rényi, A. On Random Graphs. I (PDF) . Publicationes Mathematicae. 1959, 6 : 290–297. （原始内容存档 (PDF) 于2020-08-07）. Béla Bollobás , Random Graphs , 1985, Academic Press Inc., London Ltd.
Erdős, P.; Rényi, A. On the evolution of random graphs [論隨機圖的演化] (PDF) . Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences]. 1960, 5 : 17–61 [2020-12-19 ] . （原始内容存档 (PDF) 于2021-02-01） （英语） . The probability p used here refers there to
N
(
n
)
=
(
n
2
)
p
{\displaystyle N(n)={\tbinom {n}{2}}p}
