图极限

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

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

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

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

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

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

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

${\displaystyle }$