图极限
图极限(graphon),或称图极限函数(graphon function),是用统计网络分析中,用以描述一类具有顶点可交换性结构的图之结构的二元函数。概念上,图极限函数可以被理解为一个内在结构恒定的随机图,在顶点数趋于无穷时所收敛到的极限(假定其顶点已按恰当的次序排列)。
图极限函数为描述随机图的结构和渐近性质提供了基础工具,对图极限的估计和统计推断,是近年来统计网络分析的前沿课题之一。
目录
定义
在文献中,图极限函数的定义,通常必须和顶点可交换随机图(vertex/node exchangeable random graphon)的模型,以及Aldous-Hoover表示一起陈述。
顶点可交换随机图
“随机图”指的是一个顶点集合为
{
1
,
…
,
n
}
{\displaystyle \{1,\ldots ,n\}}
的图,其边是从某个统计模型中随机生成的。用邻接矩阵(adjacency matrix)
A
∈
{
0
,
1
}
n
×
n
{\displaystyle A\in \{0,1\}^{n\times n}}
表示该随机图,则
A
{\displaystyle A}
是一个随机矩阵。
“顶点可交换性”指的是,若任意交换两个下标
i
,
j
{\displaystyle i,j}
,不会改变
A
{\displaystyle A}
的边际分布。换句话说,
A
{\displaystyle A}
具有顶点可交换性质,当且仅当:

其中
=
d
{\displaystyle {\stackrel {d}{=}}}
表示同分布,
σ
:
{
1
,
…
,
n
}
→
{
1
,
…
,
n
}
{\displaystyle \sigma :\{1,\ldots ,n\}\to \{1,\ldots ,n\}}
是任意一个重排列(permutation),并定义
(
A
σ
,
σ
)
i
,
j
=
A
σ
−
1
(
i
)
,
σ
−
1
(
j
)
{\displaystyle (A_{\sigma ,\sigma })_{i,j}=A_{\sigma ^{-1}(i),\sigma ^{-1}(j)}}
.
Aldous-Hoover表示(Aldous-Hoover representation)
Aldous和Hoover在1980年代独立证明了如下结论:任何一个顶点可交换图的生成模型,都对应某个图极限函数
f
(
u
,
v
)
:
[
0
,
1
]
2
→
[
0
,
1
]
{\displaystyle f(u,v):[0,1]^{2}\to [0,1]}
,使得图的生成模型等价于如下的随机图生成模型:









对上述定义的理解
Aldous-Hoover表示可以描述一切顶点可交换图。也就是说,即使 A {\displaystyle A}











离散的随机图向图极限的收敛
此章节需要扩充。例子
随机区块模型(Stochastic Block Model,简称SBM)的图极限(graphon)是一个分块常数函数。具体而言,设一个随机区块模型由 K {\displaystyle K}









图极限的估计方法
此章节需要扩充。参考文献
此章节需要扩充。
{\displaystyle }