隨機塊模型

隨機塊模型（英文：stochastic block model，SBM），或者隨機壆模型，係隨機圖嘅一種生成模型。個模型傾向於生成啲圖包含有啲所謂「社群」，即係啲子集、互相褦埋程度係有特定嘅檠密度嘅。譬如，啲檠喺啲社群內部可能多過喺互相之間嘅。個模型嘅數學公式由 Holland 等首次提出喺 1983 年、喺社交網絡領域。隨機塊模型喺統計學、機械學習同網絡科學當中幾重要，可以作為一項有用嘅基準畀圖數據入便社群結構嘅恢復任務。

定義

隨機塊模型採用有以下啲參數：

• 數字$n$頂點數；
• 對頂點集$\{1,\ldots ,n\}$嘅劃分，分成嘸相交嘅啲子集$C_{1},\ldots ,C_{r}$，即「社群」；
• 對稱嘅$r\times r$矩陣$P$畀啲檠概率。

然之後個檠集有得隨機採樣如下：任意兩粒頂點$u\in C_{i}$同$v\in C_{j}$由一條檠以概率$P_{ij}$褦埋。作爲例子，一個可能問題等求解嘅係：畀定一幅圖有埋$n$粒頂點嘅，其中按照描述採樣啲檠，嚟恢復啲群$C_{1},\ldots ,C_{r}$ .

特別案例

同配案例示例畀個隨機塊模型。

若果概率矩陣係常數，某種意義上講對所有$i,j$都有$P_{ij}=p$，噉個結果就係Erdős-Rényi模型$G(n,p)$。呢個係個退化案例：社群劃分變得嘸係咁緊要，但講明到同Erdős-Rényi模型嘅密切關係。

植入性分割模型（英文：planted partition model，PPM）係一種特殊情況，概率矩陣$P$啲值係常數$p$喺對角線、其他位係常數$q$。係噉，同一社群裏便每兩粒頂點係以概率$p$共享一條檠，而嘸同社群嘅兩粒頂點以概率$q$共享一條檠。有時隨機塊模型係指呢種受限嘅模型。$p>q$情況下喊做同配模型（assortative model），而$p<q$下喊做異配（disassortative）模型。

對於一般嘅隨機塊模型，強同配模型係指有親$j\neq k$即有$P_{ii}>P_{jk}$ ：所有啲對角線欄支配澌所有啲非對角線欄。弱同配模型係指有親$i\neq j$即有$P_{ii}>P_{ij}$：每個對角線欄只需要支配佢自己行同列啲其餘部分。掉轉啲嘸等式，可以有啲異配形式。算法式恢復對於有呢種形式嘅啲同配或者異配條件嘅塊模型，通常會容易啲。

典型嘅統計任務

好多啲關於算法式社群檢測嘅文獻都涉及三個統計任務：檢測、部分恢復同埋精確恢復。

檢測

檢測演算法嘅目標係簡單噉確定，畀定一幅採樣圖，呢幅圖係有潛在嘅社群結構定係冇。準確啲講，可以由一啲已知嘅先驗概率生成一幅圖，憑已知嘅隨機塊模型或者類似嘅Erdos-Renyi模型。算法式嘅任務係正確噉識別嗰兩個底層模型當中係邊一個生成到幅圖。

部分恢復

部分恢復嘅目標係大概確定到啲潛在嘅劃分、分出啲社群嘅，即搵到一種劃分係同真實劃分相關得多過隨機斷估嘅。

準確恢復

精確恢復嘅目標係準確噉恢復個潛在分區成社群。社群啲規模同埋概率矩陣可能已知亦都可能未知。

統計下限同閾值行為

隨機塊模型表現出明顯嘅閾值效應，令人惗到湆流閾值（percolation threshold）。假設允許大細係$n$嘅圖增長，又保持啲社群規模比例固定。若果個概率矩陣保持固定，對於所有啲非退化參數設置都做得到啲類似部分恢復同精確恢復嘅任務。但係，若果$n$增加同時憑比較啱嘅比率縮細個概率矩陣，劇烈嘅相變（phase transition）就着觀察到：對於某啲參數設置，可以憑趨向 1嘅概率嚟實現個恢復；而喺參數閾值嘅另一便，無論使乜演算法，恢復嘅概率都趨向 0。

對於部分恢復，啱嘅縮放值係對於固定${\tilde {P}}$取$P_{ij}={\tilde {P}}_{ij}/n$，產生啲圖係有恆常嘅平均度數（帶權連接數）嘅。喺兩個社群大細相等嘅情況下，喺個同配PPM入便、個有以下概率矩陣嘅：

$$P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right)$$

部分恢復對佢嚟講係可行嘅，概率係$1-o(1)$，逢親$({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})$，而部分恢復對任何估計器都失敗嘅概率係$1-o(1)$，逢親$({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})$。

對於準確恢復，啱嘅縮放值係取$P_{ij}={\tilde {P}}_{ij}\log n/n$，產生啲圖係有對數平均度數嘅。噉樣都有一個類似嘅閾值：對於個同配PPM、有$r$個同等規模嘅社群嘅，閾值係喺${\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}$。實質上，個準確恢復閾值係已知嘅，對於完全普適嘅隨機塊模型嚟講。

演算法

原則上，精確恢復喺個可行範圍內可以使最大似然估計解決，但噉樣相當於解決一個帶約束或者正則化唨嘅切分問題，譬如最細二分法（好多時係NP完備）。係噉，冇啲有效演算法已知嘅可以喺最壞情況下計啱個最大似然估計。

之不過，喺平均情況下有好多種演算法表現都幾好，並且有好多高概率嘅性能保證喺部分恢復同精確恢復入便經已得到證明。成功嘅演算法包括頂點譜聚類、半正定規劃、信念傳播、 社群檢測等。

變體

呢個模型存在有多種變體。一個細嘅調整係根據類別分佈（categorical distribution）隨機分配啲頂點畀社群，而嘸係劃到固定嘅分割。更加重要啲嘅變體包括度數校正隨機塊模型（degree-corrected stochastic block model）、 分層隨機塊模型（hierarchical stochastic block model）、 幾何塊模型（geometric block model）、 刪審塊模型（censored block model）同埋混合成員塊模型（mixed-membership block model）。

主題模型

隨機塊模型得公認係一個主題模型喺啲二分網絡上。喺關於文檔同單詞嘅一個網絡入便，隨機塊模型可以識別到啲主題：即一組單詞係有相似含義嘅。

睇埋

• Girvan–Newman演算法：社群檢測算法
• Lancichinetti–Fortunato–Radicchi基準：演算法，攞嚟生成啲基準網絡帶社群嘅