2. W-随机图

回想一下我们之前见过的 Erdős-Rényi 随机图 $G(n,p)$. 我们现在介绍它的 graphon. 我们从一个特殊情形开始, 即随机块模型. 2-随机块模型是一个顶点颜色随机 (蓝色或红色) 的图, 两个红色顶点以概率 $p_{rr}$ 相连, 一个红色顶点和一个蓝色顶点以概率 $p_{rb}=p_{br}$ 相连, 并且两个蓝色顶点以概率 $p_{bb}$ 相连. (...)2-随机块模型

定义 2.1. 从区间 $[0,1]$ 中均匀随机选取 $x_1,\dots ,x_n$ . 我们记一个 $W$ -随机图为 $G(n,W)$, 其顶点集 $[n]$ , 顶点 $i$ 和 $j$ 以概率 $W\left(x_i,x_j\right)$ 连接.

一个重要的统计问题是给定一个图, 是否有一种好的构造方法来构造该图? 这是我们研究 $W$ -随机图的重要动力. 我们还了解到 Erdős-Rényi 随机图的序列收敛到一个常数 graphon, 下面是一个类似的陈述.

定理 2.2. 记 $W$ 是一个 graphon. 假设对于所有的 $n$, $G_n$ 是从 W-随机图中独立选出的, 那么 $G_n\stackrel{a.s.}{\to }W$ .

笔记 2.3. 具体的, 每个 graphon $W$ 都是某个图序列的极限. 这为我们提供了某种形式的图近似.