图极限

图极限（graphon），或称图极限函数（graphon function），是用统计网络分析中，用以描述一类具有顶点可交换性结构的图之结构的二元函数。概念上，图极限函数可以被理解为一个内在结构恒定的随机图，在顶点数趋于无穷时所收敛到的极限（假定其顶点已按恰当的次序排列）。

图极限函数为描述随机图的结构和渐近性质提供了基础工具，对图极限的估计和统计推断，是近年来统计网络分析的前沿课题之一。

定义

在文献中，图极限函数的定义，通常必须和顶点可交换随机图（vertex/node exchangeable random graphon）的模型，以及Aldous-Hoover表示一起陈述。

顶点可交换随机图

“随机图”指的是一个顶点集合为 ${\displaystyle \{1,\ldots ,n\}}$  的图，其边是从某个统计模型中随机生成的。用邻接矩阵（adjacency matrix） ${\displaystyle A\in \{0,1\}^{n\times n}}$  表示该随机图，则 ${\displaystyle A}$  是一个随机矩阵。

“顶点可交换性”指的是，若任意交换两个下标 ${\displaystyle i,j}$ ，不会改变 ${\displaystyle A}$  的边际分布。换句话说，${\displaystyle A}$  具有顶点可交换性质，当且仅当：

${\displaystyle A{\stackrel {d}{=}}A_{\sigma ,\sigma }}$ 

其中 ${\displaystyle {\stackrel {d}{=}}}$  表示同分布， ${\displaystyle \sigma :\{1,\ldots ,n\}\to \{1,\ldots ,n\}}$  是任意一个重排列（permutation），并定义 ${\displaystyle (A_{\sigma ,\sigma })_{i,j}=A_{\sigma ^{-1}(i),\sigma ^{-1}(j)}}$ .

Aldous-Hoover表示（Aldous-Hoover representation）

Aldous和Hoover在1980年代独立证明了如下结论：任何一个顶点可交换图的生成模型，都对应某个图极限函数 ${\displaystyle f(u,v):[0,1]^{2}\to [0,1]}$ ，使得图的生成模型等价于如下的随机图生成模型：

1. 从 ${\displaystyle [0,1]}$  上的均匀分布生成 ${\displaystyle n}$  个独立同分布的随机变量 ${\displaystyle X_{1},\ldots ,X_{n}\sim \mathrm {Uniform} [0,1]}$ ，它们是图顶点的隐含位置（latent space position）
2. 顶点 ${\displaystyle (i,j)}$  间有边相连的概率定义为 ${\displaystyle W_{ij}=f(X_{i},X_{j})}$ ，这里 ${\displaystyle W\in [0,1]^{n\times n}}$  是该随机图的概率矩阵
3. 从概率矩阵生成邻接矩阵： ${\displaystyle \mathbb {P} (A_{ij}=1|W_{ij})=W_{ij}}$ ，并且所有 ${\displaystyle A_{ij}}$  在给定 ${\displaystyle W}$  的条件下是互相条件独立的。

对上述定义的理解

• Aldous-Hoover表示可以描述一切顶点可交换图。也就是说，即使 ${\displaystyle A}$  的生成模型中边之间不是独立的（或给定某个期望矩阵后是条件独立的），只要 ${\displaystyle A}$  整体（考虑整个图所有边的联合分布）具备顶点可交换性质，那么该边不独立的随机图模型，就等价于由某个图极限函数 ${\displaystyle f}$  诱导的随机图模型，其中边在给定概率矩阵后是条件独立的。但Aldous-Hoover表示并不显式地构造这个 ${\displaystyle f}$ ，而对应一个边不独立的随机图的 ${\displaystyle f}$  有可能非常复杂和抽象，并未必具有良好的光滑性。
• 上述Aldous-Hoover表示所描述的生成模型中，${\displaystyle X_{1},\ldots ,X_{n}}$ ， ${\displaystyle f}$  以及 ${\displaystyle W}$  都是不可见的。唯一能观测到的数据是邻接矩阵 ${\displaystyle A}$ .
• 由于模型参数的可识别性问题，${\displaystyle X_{1},\ldots ,X_{n}}$  和 ${\displaystyle f}$  一般是不唯一的，因而也是无法估计的。实际应用中，唯一能被有意义地估计的参数是 ${\displaystyle W}$ .

离散的随机图向图极限的收敛

例子

• 随机区块模型（Stochastic Block Model，简称SBM）的图极限（graphon）是一个分块常数函数。具体而言，设一个随机区块模型由 ${\displaystyle K}$  个区块构成，成员所占百分比为 ${\displaystyle \pi _{1},\ldots ,\pi _{K}}$  ，满足 ${\displaystyle \pi _{1}+\cdots +\pi _{K}=1}$ 。又记第 ${\displaystyle k_{1}}$  和 ${\displaystyle k_{2}}$  个区块的成员之间有边相连的概率是 ${\displaystyle B_{k_{1},k_{2}}}$ ，则该随机区块模型可以等价地表为从下述图极限函数诱导的网络模型：

${\displaystyle f(u,v):=B_{k_{1},k_{2}}}$ ，其中 ${\displaystyle u\in (\pi _{1}+\cdots +\pi _{k_{1}-1},\pi _{1}+\cdots +\pi _{k_{1}}),v\in (\pi _{1}+\cdots +\pi _{k_{2}-1},\pi _{1}+\cdots +\pi _{k_{2}})}$  ，并为方便统一记号，令 ${\displaystyle \pi _{0}=0}$ . 一般而言，该图极限表示不是唯一的，例如随意交换 ${\displaystyle \pi _{1},\ldots ,\pi _{K}}$  的顺序，上述表述依然成立。

• Erdos-Renyi图（Erdos-Renyi graph）的图极限是一个常数函数，它是一种特殊的随机区块模型。

图极限的估计方法

参考文献

${\displaystyle }$