求n→∞且p固定时Erdős–Rényi随机图的期望全局聚类系数

要解决这个问题，我们可以从你给出的全局聚类系数定义出发，结合随机图的期望线性性和大数定律来推导结果：

首先明确你给出的定义：

$C_{GC}={\frac {3\times {\mbox{三角形数量}}}{{\mbox{顶点连通三元组数量}}}}={\frac {{\mbox{闭合三元组数量}}}{{\mbox{顶点连通三元组数量}}}}$

这里的关键是准确理解术语：

• 三角形数量：图中所有无序三元组${u,v,w}$满足$u\sim v$、$v\sim w$、$u\sim w$的数量，记为$T$。
• 闭合三元组数量：每个三角形对应3个有序三元组$(v,u,w)$（以三角形的一个顶点$v$为中心，另外两个顶点$u,w$互为邻居），因此总数为$3T$，和你的定义一致。
• 顶点连通三元组数量：所有有序三元组$(v,u,w)$（$v,u,w$互不相同）满足$v\sim u$且$v\sim w$的数量，记为$P$——这些三元组代表“共享一个中心顶点的边对”，不管另外两个顶点是否相连。

步骤1：计算期望 #

利用随机图中边的独立性，我们可以计算各部分的期望：

• 对于任意一组互不相同的顶点$v,u,w$：
  • $v\sim u$且$v\sim w$的概率是$p^2$（两条独立边的概率乘积）。
  • $v\sim u$、$v\sim w$且$u\sim w$的概率是$p^3$（三条独立边的概率乘积）。
• 图中共有$n(n-1)(n-2)$个这样的有序三元组，因此：
  • $\mathbb{E}[3T] = n(n-1)(n-2) \cdot p^3$（所有闭合三元组的期望数量）。
  • $\mathbb{E}[P] = n(n-1)(n-2) \cdot p^2$（所有顶点连通三元组的期望数量）。

步骤2：渐近行为（$n\rightarrow\infty$） #

当$n$趋向于无穷大时，根据大数定律，随机变量$T$和$P$几乎必然趋近于它们的期望（即$T \approx \mathbb{E}[T]$，$P \approx \mathbb{E}[P]$）。因此全局聚类系数的比值可以近似为期望的比值：
$$\mathbb{E}[C_{GC}] \approx \frac{\mathbb{E}[3T]}{\mathbb{E}[P]} = \frac{n(n-1)(n-2)p^{3}{n(n-1)(n-2)p}2} = p$$

更严谨地说，由于边的独立性，给定$v\sim u$和$v\sim w$，$u\sim w$的条件概率就是$p$——这直接决定了全局聚类系数的极限值为$p$，而期望$\mathbb{E}[C_{GC}]$也会随着$n\rightarrow\infty$趋近于$p$。

总结：当$n\rightarrow\infty$且$p$固定时，$\mathcal{G}(n,p)$的期望全局聚类系数$\mathbb{E}[C_{GC}]$趋近于$p$。

内容的提问来源于stack exchange，提问作者Fabian Ying