圖數據挖掘：社區檢測演算法（一）

最近需要學習圖結構中的社區檢測演算法，在閱讀相關論文的同時跟了Stanford CS246: Mining Massive Datasets課程[1]的第11講Community Detection in Graphs，以下是我做的筆記。

1. 網路和社區(networks & communities)

我們通常認為網路中存在某種模組(modules)/簇(clusters)/社區(communitis)結構，我們常常需要從網路中提取這些結構。

遷移學習和多任務學習之間的區別

而提取這些結構的關鍵在於發現密集連接的簇，而這常常可以轉化為一個優化關於簇的目標函數的問題。

2.重疊(overlapping)和非重疊(non-overlapping)社區檢測

按照圖的社區劃分之間是否重疊，可分為重疊社區檢測和非重疊社區檢測。非重疊社區檢測是指圖的社區劃分之間沒有重疊，而重疊社區檢測則允許有重疊。

遷移學習和多任務學習之間的區別

3.基於conductance（電導）的圖劃分方法

3.1 割分數(cut score)

設有一個無向圖\(G(V,E)\)，我們將其節點劃分為兩個組\(A, B\)，其中\(B = V\backslash A\)，我們如何判斷我們劃分的品質呢？

我們運用直覺思考，好的劃分有什麼特性？一般而言，好的劃分有兩個特點：

  • 使單個簇內部的連接數量最大化
  • 使不同簇之間的連接最小化

遷移學習和多任務學習之間的區別

接下來我們需要定量地將簇的品質表示為該簇的「edge cut」（感覺翻譯成割邊不太妥當，為了表述方便，下面將兩個簇之間連接的邊形象地稱為「跨邊」）的函數。
割分數(cut score) 為只有一個節點在簇中的邊的邊權之和（如果為無權圖，則權值計為1）。用公式表達如下：

\[\operatorname{cut}(A)=\sum_{i \in A, j \notin A} w_{i j} \\
(注意，如果為無權圖，則w_{i j}為1)
\]

對於下面這張無權圖，則我們有\(cut(A) = 2\):

遷移學習和多任務學習之間的區別

也就是說，對於一個簇\(A\)，若\(cut(A)\)越小，則我們說這個簇的品質越好。那麼所謂的簇劃分，是否意味著我們只需要找到一組能夠時\(cut(A)\)盡量小的節點就可以呢？

光這樣還不夠，因為我們事實上只考慮了簇外部的聯繫，但是沒有考慮簇內部的聯繫，這樣容易導致很多問題。我們看下面這個退化的情形。很明顯，就下面這張圖而言，紅色的所謂「mimimum cut」確實做到使\(cut(A)\)最小了，但是明顯另外一種劃分方法才是我們想要的。

遷移學習和多任務學習之間的區別

那麼我們如何進一步考慮到簇內部的聯繫呢？這時就要引出簇的volume(體積)和conductance（好像翻譯成電導？）的概念了。

3.2 電導(conductance)

conductance是指一個簇和剩餘網路的聯繫，它和這個簇的的密度（體積）有關係。它在某種意義上可以理解為表面積和體積比(surface-to-volume ratio)。直觀地理解，它等於這個簇的割分數除以這個簇自身的密度（體積），這個值越小說明劃分得越好。
接下來我們再來看conductance這個有點可怕的公式（其實理解了它的意義後就會發現並不可怕）：

\[\phi(A)=\frac{|\{(i, j) \in E ; i \in A, j \notin A\}|}{\min (\operatorname{vol}(A), 2 m-\operatorname{vol}(A))}
\]

此公式中\(m\)指圖中邊的數量，\(2m\)即圖中所有點的度數之和，\(E\)指圖的邊集。\(vol(A)\)定義為簇\(A\)中所有點的度之和：

\[\begin{aligned}
vol(A) &= \sum_{i\in A} d_{i}
\end{aligned}\\
(這裡d_i指節點i的度)
\]

(也可以寫作\(vol(A)= 2\cdot \sharp\text{edges inside } A + \sharp \text{edges pointing out of } A\))
\(\phi(A)\)定義式的分母部分實質上就相當於從割邊分開的兩個簇的\(vol\)值中選小的那個。

我們再來用conductance重新審視圖的劃分。
很明顯，若我們關注紅色的簇，邊的那種劃分方式\(\phi = 2/(3+1)=0.5\)(其中\(2\)為紅色簇跨出去的邊數之和，\(3+1=4\)為紅色簇的度數之和)，右邊的那種劃分方式\(\phi = 6/92=0.065\)，很明顯右邊的那種劃分方式更好。

遷移學習和多任務學習之間的區別

根據這個劃分標準，有許多論文已經提出了相關的簇劃分演算法，如[2]，大家可以參考論文，此處略過不表。

4.基於模組性(modularity)的圖劃分方法

4.1 模組性

對於一個網路社區，我們定義其模組性(modularity)\(Q\)做為一個網路被劃分為社區的好壞度量。給定一個網路的劃分，該劃分將網路劃分為由多個組\(s\)組成的集合\(S\)，我們有:

\[Q \varpropto \sum_{s\in S}[(\sharp \text{edges within group }s) – (\text{expected }\sharp \text{edges within group } s)]
\]

我們給定一個有\(n\)個節點和\(m\)條邊的圖，我們據此構建重布線的(rewired)網路\(G^{‘}\)。該網路\(G^{‘}\)滿足：有同樣的度分布但是有著隨機的邊連接；是多重圖(multigraph)（即允許有多重邊的圖）；節點\(i\)（度為\(k_i\)）和\(j\)(度為\(k_j\))之間的期望邊數量為：\(k_i \cdot \frac{k_j}{2m} = \frac{k_i k_j}{2m}\)。
我們根據以上資訊，進一步圖\(G\)被劃分為組\(S\)的模組性寫為

\[Q(G, S)=\frac{1}{2 m} \sum_{s \in S} \sum_{i \in s} \sum_{j \in s}\left(A_{i j}-\frac{k_{i} k_{j}}{2 m}\right)
\]

這裡\(m\)為一個標準化常數，使得\(-1<Q<1\)。\(A_{ij}\)為節點\(i\)和節點\(j\)之間的邊權，若無連接則為0。
如果在簇內部的邊數量超過了其期望的邊數量，則模組性\(Q\)為正。比\(0.3-0.7\)大的\(Q\)意味著非常重要的社區結構。

等效地，模組性公式還能夠被寫作：

\[Q=\frac{1}{2 m} \sum_{i j}\left[A_{i j}-\frac{k_{i} k_{j}}{2 m}\right] \delta\left(c_{i}, c_{j}\right)
\]

這裡\(A_{ij}\)仍然指節點\(i\)和\(j\)之間的邊權，\(k_i\)分別\(k_j\)指以節點\(i\)和\(j\)做為端點的邊權之和，\(2m\)是凸中所有邊的權值之和，\(c_i\)和\(c_j\)是節點組成的社區，\(\delta\)是一個示性函數。此時，我們有一個想法： 我們能夠通過最大化模組性\(Q\)來識別社區。

4.2 Louvain（魯汶）方法

我們可以採用一個啟發式方法，也就是Louvain方法來解決該問題。這個演算法是一個貪心演算法，時間複雜度為\(O(n log n)\)，它支援帶權圖，能夠提供層次化的劃分方法（比如我們熟知的層次聚類）。該方法運行效率高、收斂快、輸出結果模組性高（也即輸出的社區劃分品質較好），被廣泛地應用於大規模網路。
Louvain演算法貪心地最大化模組性，它會進行多輪的迭代，每一輪迭代都由兩個步驟組成：

  • 步驟 1（劃分）：在只允許對社區做局部改變(local changes)的情況下優化模組性，得到一個初步的社區劃分。
  • 步驟 2（重構）：對已劃分出的社區做聚合，建立新的社區網路。

我們接下來詳細地敘述步驟1和步驟2。

步驟1（劃分）
對於步驟1，演算法先將圖中的每個節點(後面我們會提到演算法會將社區也縮為一個超節點)視為一個獨立的社區。然後對每個節點\(i\)，演算法執行兩步計算：首先，對節點\(i\)的每個鄰居\(j\)，計算將\(i\)從其現在的社區中放入\(j\)所在的社區時可獲得的模組性增益(modularity gain)\(\Delta Q\)；然後，將\(i\)移入能夠獲得最大\(\Delta Q\)的社區。

註：

當我們將節點\(i\)移入社區\(C\)中時，其模組性增益\(\Delta Q\)計算方式如下：

\[\Delta Q(i \rightarrow C)=\left[\frac{\sum_{i n}+k_{i, i n}}{2 m}-\left(\frac{\sum_{t o t}+k_{i}}{2 m}\right)^{2}\right]-\left[\frac{\sum_{i n}}{2 m}-\left(\frac{\sum_{t o t}}{2 m}\right)^{2}-\left(\frac{k_{i}}{2 m}\right)^{2}\right]
\]

這裡\(\sum_{in}\)對\(C\)中所有節點的”簇內”鄰邊（不包括跨邊）的邊權進行求和；\(\sum_{tot}\)對\(C\)中所有節點的鄰邊（包括跨邊）邊權進行求和;\(k_{i, in}\)是節點\(i\)和簇\(C\)之間的所有邊的權重之和；\(k_i\)指節點\(i\)所有鄰邊的權重之和（其實就是節點的度，注意帶權圖節點的度定義為節點所有鄰邊的權值和）。
同理，我們可以得到\(\Delta Q(D\rightarrow i)\)，這表示將節點\(i\)移出社區\(D\)所得的增益。
接下來，我們有\(\Delta Q=\Delta Q(i \rightarrow C)+\Delta Q\left(D\rightarrow i\right)\)

步驟2（重構）
將第一階段中劃分而成的社區縮為超節點(super-nodes)，然後我們按照以下的步驟來構建新的帶權網路：如果在兩個社區的節點之間至少有一條邊，那麼對應的兩個超節點之間就是連接的；在兩個超節點之間的邊的權值是其對應社區之間所有跨邊的權值之和。

最後，我們將Louvain方法用流程示意圖描述如下：

遷移學習和多任務學習之間的區別

參考文獻

  • [1] //www.mmds.org/
  • [2] Lu Z, Sun X, Wen Y, et al. Algorithms and applications for community detection in weighted networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 26(11): 2916-2926.
  • [3] Staudt C L, Meyerhenke H. Engineering parallel algorithms for community detection in massive networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 27(1): 171-184.
Tags:

VirMach 便宜 VPS

QNews

QNews