並行Louvain社區檢測演算法
因為在我最近的科研中需要用到分散式的社區檢測（也稱為圖聚類（graph clustering））演算法，專門去查找了相關文獻對其進行了學習。下面我們就以這篇論文IPDPS2018的文章[1]為例介紹並行社區檢測演算法。
關於基本的單機/串列社區檢測演算法，大家可以參考我的另一篇部落格《圖數據挖掘：社區檢測演算法（一）》(鏈接：//www.cnblogs.com/orion-orion/p/15662253.html)。總而言之，目前對於圖的簇/社團劃分，目前最廣泛的測量方法是使用模組性(modularity)。然而模組性的優化是NP完全問題，目前最有名的一種啟發式求解方法是基於貪心準則的Louvain方法。由於其速度和對社區檢測結果的高品質，Louvain方法在串列/單機社區檢測中一直是最常用的方法之一。
目前有許多方式可以對Louvain方法進行並行化。目前最快的基於共享記憶體多執行緒的Louvain方法是Grappolo軟體包[2]。該軟體能夠在812s內在20個核上處理現實世界中大型的網路（soc-friendER; 18億條邊）。
在本篇論文中，作者將這個方法擴展到了分散式記憶體領域（和前面基於共享記憶體的領域不同）。而設計一個分散式的Louvain演算法的挑戰在於執行高效的鄰居節點掃描（為了捕捉鄰居節點所屬社區狀態的變化），因為在圖的分散式表示的情況下，通訊開銷會變得非常重要。另一個關鍵的挑戰是我們對哪個社區的狀態進行查詢和更新。串列演算法的好處在於每輪迭代之間有同步操作，然而在分散式的環境下維護與傳播最新的資訊是被禁止的。此外，在分散式環境下一條邊跨幾個進程的處理也是一個棘手的問題。
1. 串列Louvain方法
我們這裡簡要描述一下串列的Louvain方法（詳細描述見另一篇部落格）。Louvain方法是一個多輪的迭代過程，每輪迭代分幾個步驟。第一步，將每個節點視為一個社區，然後遍歷每個節點——其中對於節點\(v\)，計算將\(v\)移入各鄰居可能導致的模組性增益\(\Delta Q\)，如果最大的增益為正，那麼\(v\)就會從其現在的社區移入該社區；第二步，進行圖重建，即將所有劃分好的社區縮為超節點。這個迭代過程一直持續直到不再獲得模組性的增益（可以人工給定一個閾值\(\tau\)）。
該演算法的偽程式碼描述如下(偽程式碼中省略了圖重建的過程)：
2. 並行Louvain方法
我們開始敘述並行演算法部分。我們使用\(p\)表示進程的數量，編號\(i\)表示區間\([0, p-1]\)內的任意進程編號。
首先，我們將輸入的節點及它們的邊集列表（edge list）（我們採用鄰接表進行存儲）分攤到各進程上，使每個進程接收到的邊數量大致相同（這裡沒有用高級的圖劃分演算法）。每個進程除了它本身擁有的節點集合之外，還存儲了雖然屬於其他進程、但與本進程中節點相關聯的其他節點的拷貝（後面我們統一把這類節點稱為影子節點）。論文採用稀疏行（CSR）的方式存儲點和邊集列表。
類似地，每個進程也獲得一個任意集合的社區（大致使每個進程獲得的社區數量相同），同時也保存了和本進程的社區之間有關聯邊（incident edges，即「跨邊」）的社區（我們稱為影子社區）。
下面的偽程式碼給出了並行的Louvain演算法的大致框架，它包含了LouvainIteration過程（也就是前面的模組性增益最大化過程）和BuildNextPhaseGraph（對應前面的圖的重構）這兩個過程。注意，LouvainIteration過程的步驟我們還沒有展開，其中包括了進程之間通訊的過程。
接下來我們詳細的看LouvainIteration過程和BuildNextPhaseGraph是怎麼實現的。
(a)Louvain Iteration
下面的偽程式碼展示了LouvainIteration過程：
在這個過程中，每個進程都擁有節點和社區的集合，而進程之間的通訊主要交換的資訊也是節點和社區之間的資訊。對每個局部的節點，都會存儲一個社區ID。對每個局部的社區，關聯度(\(a_c\))也被局部地存儲。因為節點和進程編號的映射關係沒輪迭代都在變化，每個進程需要存儲其影子節點的列表以及這些影子節點對應的進程。此外，因為在每輪迭代開始時每個節點都在其自身的社區，故初始化的影子社區資訊能夠由節點資訊推導出來。
下面我們解釋一下LouvainIteration過程的主要步驟：
-
2行（即過程開始），因為節點到進程的映射在每輪迭代（這裡的迭代是指
LouvainIteration過程外的迭代，別搞混了）會改變（由於圖的縮點重構），我們會調用ExchangeGhostVertices操作執行一次通訊操作來自交換影子的坐標資訊。 -
4-5行（相當於每輪迭代的開始），論文進行了每輪迭代一次的
send-receive通訊步驟來交換對應的影子節點資訊（參照演算法4），send操作指將進程的局部節點資訊發往以這些節點做為影子節點的其他進程；receive操作指從其他進程獲得影子節點的更新。 -
7-9行，使用最新的節點資訊來計算所有局部節點的社區分配。
-
10-11行(相當於每輪迭代的末尾），我們需要將影子社區已更新的資訊送往它們所屬的進程，並且使各進程的社區接受相關更新的社區。
-
12-13行，先新的社區狀態計算當前進程子圖的模組性，然後採用
AllReduce操作規約得到全局模組性。 -
如果網路的模組性增益(\(\Delta Q\))相對於前面的迭代低於需要的一個閾值下限，我們就終止迭代（否則繼續迭代）。
其中，ExchangeGhost函數的定義如下：
ExchangeGhost函數中6-7行表示當\(u\)節點的所有者\(owner\)不是當前節點，就將\(u\)增加到列表 \(vmap[owner]\) 中（\(vmap\)做為一個局部緩衝區，後面在第10行將\(vmap\)發給進程\(j\)，然後在第11行接受傳到第\(j\)個進程的影子節點數據）。
(b)Graph reconstruction
下面我們來看圖的重構過程。上一個社區劃分過程中所劃分的社團將在圖的重構過程中被壓縮為單個節點。在一個社區內部的邊會形成自環，對於連接兩個不同社區的「跨邊」會形成連接兩個節點的一條邊（權重為所有"跨邊"之和）。圖的重建過程可以參考下圖：
我們可以看到，模組性優化步驟最初始將節點\(\{0, 1, 3\}\)分配給社區\(0\)，節點\(2\)分配給社區\(2\)，節點\(4\)分配給社區\(4\)（節點\(2\)和\(4\)各自成為一個社區）。由於社區ID由節點ID產生，我們認為\(0-2\)號社區屬於(存儲在)進程\(0\)，\(3-4\)號社區屬於（存儲在）進程\(1\)。注意，圖例中[Array]表示數組，<Map>表示字典映射。<Vlocal, C> 字典中存儲了節點編號和社區編號的映射關係;[Edges]數組中存儲了邊的權重;<Vremote, C>字典存儲了影子節點編號與其所屬社區的映射關係。
然後圖的重建可分為7個步驟：
(1) 每個進程將其局部社區進行重編號。重編號使用一個關聯原始社區ID和新社區ID的哈希表<Cold, Cnew>來實現。
(2) 每個進程檢查可能已分配給遠程節點（但和局部節點已無任何聯繫）的局部社區的ID。
(3) 基於前\(N\)個進程中局部社區的數量，為第\(N+1\)個進程的局部社區進行全局編號（並行前綴和計算）。
(4) 將最新的局部社區ID和全局社區ID編號的映射關係(<C, Cnew>) 以AllReduce的方式更新到各個進程上。
(5) 每個進程會檢查其所擁有的節點並構建部分的新的邊集列表。對進程所擁有的每個節點，進程會檢查其鄰居列表，其中和新的社區ID相關聯的鄰居會形成一個自環。
(6) 一旦新的「部分邊集列表」生成，它們就會被重新分配到各進程，然後生成新的圖劃分並調整邊的權重（每個進程會儘可能獲得相同數量的節點）。
(7) 根據新的超節點的帶權鄰接列表<Cnew, <Cnew, weight>>構建新的圖。
參考文獻
-
[1] Ghosh S, Halappanavar M, Tumeo A, et al. Distributed louvain algorithm for graph community detection[C]//2018 IEEE international parallel and distributed processing symposium (IPDPS). IEEE, 2018: 885-895.
-
[2] Lu H, Halappanavar M, Kalyanaraman A. Parallel heuristics for scalable community detection[J]. Parallel Computing, 2015, 47: 19-37.
