隨機塊模型

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

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

數字頂點數；
 對頂點集嘅劃分，分成嘸相交嘅啲子集，即「社群」；
 對稱嘅矩陣畀啲檠概率。

然之後個檠集有得隨機採樣如下：任意兩粒頂點同由一條檠以概率褦埋。作爲例子，一個可能問題等求解嘅係：畀定一幅圖有埋粒頂點嘅，其中按照描述採樣啲檠，嚟恢復啲群 .

特別案例 

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

植入性分割模型係一種特殊情況，概率矩陣啲值係常數喺對角線、其他位係常數。係噉，同一社群裏便每兩粒頂點係以概率共享一條檠，而嘸同社群嘅兩粒頂點以概率共享一條檠。有時隨機塊模型係指呢種受限嘅模型。情況下喊做同配模型，而下喊做異配模型。

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

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

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

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

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

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

對於部分恢復，啱嘅縮放值係對於固定取，產生啲圖係有恆常嘅平均度數嘅。喺兩個社群大細相等嘅情況下，喺個同配PPM入便、個有以下概率矩陣嘅：部分恢復對佢嚟講係可行嘅，概率係，逢親，而部分恢復對任何估計器都失敗嘅概率係，逢親。

對於準確恢復，啱嘅縮放值係取，產生啲圖係有對數平均度數嘅。噉樣都有一個類似嘅閾值：對於個同配PPM、有個同等規模嘅社群嘅，閾值係喺。實質上，個準確恢復閾值係已知嘅，對於完全普適嘅隨機塊模型嚟講。

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

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

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

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

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

考 

網絡
機械學習