圖極限

圖極限（graphon），或稱圖極限函數（graphon function），是用統計網絡分析中，用以描述一類具有頂點可交換性結構的圖之結構的二元函數。概念上，圖極限函數可以被理解為一個內在結構恆定的隨機圖，在頂點數趨於無窮時所收斂到的極限（假定其頂點已按恰當的次序排列）。

圖極限函數為描述隨機圖的結構和漸近性質提供了基礎工具，對圖極限的估計和統計推斷，是近年來統計網絡分析的前沿課題之一。

定義[編輯]

在文獻中，圖極限函數的定義，通常必須和頂點可交換隨機圖（vertex/node exchangeable random graphon）的模型，以及Aldous-Hoover表示一起陳述。

頂點可交換隨機圖[編輯]

「隨機圖」指的是一個頂點集合為 $\{1,\ldots ,n\}$ 的圖，其邊是從某個統計模型中隨機生成的。用鄰接矩陣（adjacency matrix） $A\in \{0,1\}^{n\times n}$ 表示該隨機圖，則 $A$ 是一個隨機矩陣。

「頂點可交換性」指的是，若任意交換兩個下標 $i,j$ ，不會改變 $A$ 的邊際分布。換句話說， $A$ 具有頂點可交換性質，若且唯若：

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

其中 ${\stackrel {d}{=}}$ 表示同分布， $\sigma :\{1,\ldots ,n\}\to \{1,\ldots ,n\}$ 是任意一個重排列（permutation），並定義 $(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}\to [0,1]$ ，使得圖的生成模型等價於如下的隨機圖生成模型：

從 $[0,1]$ 上的均勻分布生成 $n$ 個獨立同分布的隨機變量 $X_{1},\ldots ,X_{n}\sim \mathrm {Uniform} [0,1]$ ，它們是圖頂點的隱含位置（latent space position）
頂點 $(i,j)$ 間有邊相連的概率定義為 $W_{ij}=f(X_{i},X_{j})$ ，這裡 $W\in [0,1]^{n\times n}$ 是該隨機圖的概率矩陣
從概率矩陣生成鄰接矩陣： $\mathbb {P} (A_{ij}=1|W_{ij})=W_{ij}$ ，並且所有 $A_{ij}$ 在給定 $W$ 的條件下是互相條件獨立的。

對上述定義的理解[編輯]

Aldous-Hoover表示可以描述一切頂點可交換圖。也就是說，即使 $A$ 的生成模型中邊之間不是獨立的（或給定某個期望矩陣後是條件獨立的），只要 $A$ 整體（考慮整個圖所有邊的聯合分布）具備頂點可交換性質，那麼該邊不獨立的隨機圖模型，就等價於由某個圖極限函數 $f$ 誘導的隨機圖模型，其中邊在給定概率矩陣後是條件獨立的。但Aldous-Hoover表示並不顯式地構造這個 $f$ ，而對應一個邊不獨立的隨機圖的 $f$ 有可能非常複雜和抽象，並未必具有良好的光滑性。
上述Aldous-Hoover表示所描述的生成模型中， $X_{1},\ldots ,X_{n}$ ， $f$ 以及 $W$ 都是不可見的。唯一能觀測到的數據是鄰接矩陣 $A$ .
由於模型參數的可識別性問題， $X_{1},\ldots ,X_{n}$ 和 $f$ 一般是不唯一的，因而也是無法估計的。實際應用中，唯一能被有意義地估計的參數是 $W$ .

離散的隨機圖向圖極限的收斂[編輯]

例子[編輯]

隨機區塊模型（Stochastic Block Model，簡稱SBM）的圖極限（graphon）是一個分塊常數函數。具體而言，設一個隨機區塊模型由 $K$ 個區塊構成，成員所占百分比為 $\pi _{1},\ldots ,\pi _{K}$ ，滿足 $\pi _{1}+\cdots +\pi _{K}=1$ 。又記第 $k_{1}$ 和 $k_{2}$ 個區塊的成員之間有邊相連的概率是 $B_{k_{1},k_{2}}$ ，則該隨機區塊模型可以等價地表為從下述圖極限函數誘導的網絡模型：