基于SLPA優化的重疊社區發現算法

陳界全 王占全* 李 真 湯敏偉

1(華東理工大學信息科學與工程學院 上海 200237) 2(天翼電子商務有限公司風險管理部 上海 200080)

0 引 言

社區檢測是一種在網絡中探索集群或社區的行為。集群或者社區是一組緊密連接的實體，它們在組內的連接比與其他實體的連接更高[1]。對各種領域的真實網絡進行社區的發現，對于理解復雜網絡的結構和模式起著重要的作用。例如，在社交網絡領域，可以根據不同的興趣和背景將其劃分為不同的社會群體進行準確的推薦；在生物學領域，傳播網絡由疾病和病毒兩部分組成，通過對其進行研究和分析，找到易感染人群的關鍵社區或關鍵節點，預測傳播路徑，從而及時控制疾病。綜上所述，社區檢測在復雜網絡的研究中有重要意義。

然而，目前的研究主要集中在檢測非重疊的社區，然而真實社交網絡中的社區通常是互相重疊的[2]。例如，一個研究者可能屬于多個研究群組中，一個人在現實生活或者網絡中會加入多個興趣小組。所以，重疊社區的發現對于進一步分析和利用復雜網絡結構具有重要的意義，重疊社區如圖1所示。

圖1 重疊社區

本文提出一種改進的重疊社區發現算法(L-SLPA)，其擴展了SLPA，在算法的初始階段先對網絡進行一次非重疊社區劃分，然后給同一社區中的節點分配相同的標簽，而不是像SLPA一樣給所有的節點分配不同的標簽。標簽分配完成后，僅對邊界節點執行Speaker-Listener標簽傳遞的迭代過程，最后對各節點包含的所有標簽進行過濾。

1 相關工作

1.1 重疊社區發現算法

重疊社區結構更加貼合現實網絡的實際情況，這一理論和實踐上的重要意義促使世界上很多研究人員對復雜網絡的社區進行研究，很多有效的模型被不斷提出。派系過濾算法(CPM)基于這樣的假設：一個社區由重疊的完全連接的子圖集組成，并通過搜索相鄰的團來檢測社區[3]，它適用于密集連接的網絡中，對于稀疏的網絡算法效率將會變得很低。Raghavan等[4]提出了一種簡單的標簽傳播算法(Label Propagation Algorithms)，每個節點都用一個唯一的標簽初始化，并且在每一步中，每個節點都采用它的大多數鄰居當前擁有的標簽。該算法時間復雜度低、簡單、實用性強、效果好。Gregory等[5]基于LPA引入了社區從屬系數，提出具備重疊社區發現能力的COPRA，但是該算法并沒有解決標簽傳播所帶來的隨機性問題。Lancichinetti等[6]定義了一個可以衡量節點緊密連接程度的fitness函數，LFM算法隨機選擇一個沒有被分配社區的節點作為種子，通過優化fitness函數以形成一個社區，但是LFM算法較高的時間復雜度使得其在大型網絡中的效率并不理想。

1.2 Louvain算法

Blondel等[7]提出的基于啟發式和模塊度Q優化的Louvain算法，是一種近線性運行時間的貪婪算法。該算法對多層次的圖進行操作，在每個層次上應用頂點移動程序(VM)來提高模塊性,具有運行速度快、效果穩定等優點。

(1)

(2)

式中：Aij為節點i和節點j之間邊的權值；ki為與頂點i相連的邊的權值和；ci為頂點i所在的社區；m為圖中所有邊的數量的1/2；如果u=v則δ(u,v)為1，反之為0；∑in為社區c中所有邊的權重和;∑tot為社區c中節點關聯的所有邊的權值和；ki,in為頂點與社區c中節點所有相連邊的權重和。

1.3 SLPA

SLPA(Speaker-ListenerLabel Propagation Algorithms)是一種基于一般說話者和收聽者的信息傳播過程的算法。SLPA在LPA的基礎上引入了Speaker(標簽傳播節點)和Listener(標簽接受節點)兩個概念[8]，如圖2所示。它根據成對的交互規則在節點之間傳播標簽。當一個節點忘記了在前一個迭代中獲得的知識時，SLPA為每個節點提供一個大小為T的內存來存儲接收到的信息(即標簽)。節點內存中觀察到標簽的概率被解釋為成員強度。SLPA不需要提前指定社區數量，時間復雜度為O(Tm)，與邊數m呈線性關系，其中T為預定義的最大迭代次數(如T≥20)。SLPA還可以通過一般化交互規則(SLPAw)來適應加權和定向網絡。

圖2 SLPA中的Speaker和Listener

SLPA的大致步驟如下：

(1) 初始化每個節點，給每個節點一個唯一的標簽。

(2) 隨機挑選一個節點作為Listener，其鄰居節點為Speaker。

(3) Speaker以各個標簽在其內存所有標簽中存在概率隨機發送一個標簽，Listener接收所有發送過來的標簽中最多的那個標簽。

(4) 統計每個節點各類標簽數量，將個數超過要求的標簽作為節點最終的社團標簽。

但是由于SLPA在初始化過程中，為每個節點都分配了一個唯一的標簽，對于復雜網絡而言，標簽的分配和傳播會消耗大量的資源。而且標簽的傳播過程中的隨機選擇策略會造成SLPA的不穩定性和隨機性。

2 基于SLPA優化的社區發現算法

在SLPA的初始階段，每個節點都被分配了一個單獨的標簽，當網絡規模較大時，這無疑消耗了巨大的資源。所以，可以先對復雜的網絡進行一次初步的劃分，然后給相似的一類節點分配一個相同的標簽，這樣能夠大大減少標簽分配的資源消耗。同時，重疊節點通常處于社區的邊緣，因此，本文在改進的算法中引入了邊界節點的概念(定義3)。在T次迭代中，只需要對邊界節點進行Speaker-Listener的標簽傳遞過程，而不是對所有的節點都進行標簽傳遞，從而提高算法的效率。最后根據閾值r，過濾每個節點中的無效標簽(定義4)，保留下來的標簽所對應的社區即為該節點歸屬的社區。

定義1一個復雜網絡可以表示為G=(V,E)，E為所有邊的集合。

定義2假設網絡G劃分得到的社區集為C={c1,c2,…,cn}，ci表示劃分得到的第i個社區。

定義3對于G=(V,E)的社區劃分C={c1,c2,…,cn}，若vi∈ci，vj∈cj，i≠j，并且?eij∈E(eij為兩節點間的邊)，則稱vi和vj為邊界節點。

定義4當某類標簽li出現的概率P(li)小于閾值r，則將該標簽稱為無效標簽，具體條件表示為：

(3)

本文將改進后的算法稱為L-SLPA，算法的具體步驟如算法1所示。其中步驟1-步驟3為非重疊社區劃分階段，步驟4-步驟5為標簽分配和邊界節點統計階段，步驟6-步驟9為Speaker-Listener標簽傳遞的迭代階段。

算法1L-SLPA

輸入：復雜網絡G(V,E)。

輸出：重疊社區{c1,c2,…,cn}。

步驟1初始化所有節點，每個節點為一個單獨的社區。

步驟2每個節點分別加入鄰居社區中，按式(2)計算模塊度增益ΔQ。假如存在ΔQ大于零，則將該節點加入ΔQ最大的社區中。

步驟3將社區合并成超點，重復步驟1和步驟2，直到模塊度Q不再變化。

步驟4為同社區中的節點分配一個相同的標簽，不同社區中的節點分配到的標簽不同。

步驟5統計邊界節點。

步驟6在邊界節點中隨機挑選一個節點作為Listener，其鄰居節點為Speaker。

步驟7Speaker以各個標簽在其內存所有標簽中存在概率隨機發送一個標簽，Listener接收所有發送過來的標簽中最多的那個標簽。

步驟8重復步驟6和步驟7，直到達到最大迭代次數T。

步驟9統計每個節點各類標簽的數量，根據閾值r，過濾無效標簽，將剩下的標簽作為節點最終的社團標簽。

假設有這樣一個圖，其中包含7個節點和11條邊。先對其進行非重疊社區發現，節點1-節點3被劃分為社區1，節點4-節點7被劃分為社區2。給社區1中的所有節點分配一個標簽1，給社區2中的所有節點分配一個標簽2。同時，圖中的節點1、節點3、節點4和節點7為邊界節點，對這4個邊界節點執行Speaker-Listener的標簽傳遞過程。算法結束后，發現節點1同時包含著標簽1和標簽2，則可以認為，節點1同時歸屬于兩個社區，是一個重疊節點，如圖3所示。

圖3 L-SLPA舉例

當復雜網絡的規模不斷增大，時間復雜度是算法需要考慮的一個重要問題。在本文算法的第一階段，非重疊社區發現的時間復雜度為O(m)，其中m為復雜網絡中邊的數量。第二階段中，統計邊界節點的時間復雜度為O(m)，SLPA的整個標簽傳遞過程的時間復雜度為O(Tn)，其中：T為算法的迭代次數；n為節點的數量。所以，L-SLPA整體的時間復雜度為O(m+Tn)，基本與網絡中邊的數量呈線性關系。

3 實 驗

本文將L-SLPA與幾種具有代表性的重疊社區發現算法進行對比，分別為SLPA、Copra[5](另一種標簽傳播算法)、CPM算法[3](派系過濾算法)和LFM算法[6](一種基于適應度函數的社區擴展算法)，以驗證L-SLPA的性能。本文實驗所有算法均采用Python實現，運行環境為PC，基本配置：CPU為3.1 GHz Intel Core i5，內存為8 GB。

3.1 實驗數據集

本文選取了6個規模不同的真實網絡數據集[9-17]，對改進的L-SLPA及4種對比的重疊社區發現算法進行測試。真實網絡數據集的具體參數如表1所示。

表1 真實網絡數據集

Lancichinetti 等[18]提出的LFR基準網絡被廣泛應用于復雜網絡分析中，通過調整參數生成規模不同的人工合成數據集。本文實驗中的基準測試網絡參數設置如表2所示，其中：節點的數量N分別被設為1 000和5 000；節點的平均度k被設為10；最大的節點度kmax為50；混合參數μ控制著網絡中潛在的社區結構，μ越大社區結構越模糊，μ被設置為0.1和0.3；社區的規模設定為10～50之間；重疊節點數量on為總節點數的10%；每個節點歸屬的社區數om則為2～8。

表2 LFR基準網絡參數

3.2 評價指標

3.2.1重疊模塊度QE

模塊度Q是由Newman提出，用于評價社區劃分結果的好壞，但是該函數僅適用于非重疊社區劃分的結果。為了能夠合理地評價重疊社區發現的結果，Chen等[19]在模塊度函數的基礎上提出了重疊社區的模塊度指標QE，QE的值在0到1之間，值越高代表社區劃分得越準確。

(4)

式中：m為圖中邊的總數；A為網絡的鄰接矩陣，若節點i和節點j之間存在一條邊，則Aij=1，反之為0；ki、kj分別為節點i和節點j的度；oi、oj為節點i和j所屬的社區數。

3.2.2標準互信息NMI

模塊度能夠對社團劃分結果好壞進行評價。如果知道網絡的真實社區劃分情況，則可以通過得到的社區劃分結果與真實的社區劃分情況進行對比，這樣就能測算出社區發現算法的準確性。NMI(標準化互信息)[6]，評價一個社區劃分和標準劃分結果之間差異性的指標，通常被用來評價一個社區發現算法的準確性。NMI的值在0到1之間，值越高代表社區劃分得越準確。

(5)

式中：X和Y分別代表真實的社區結構和社區發現算法得到的社區結構；H(X|Y)norm和H(Y|X)norm為社區分布的條件信息熵。

3.3 算法參數選取

L-SLPA最終的結果依賴于閾值r和T的選取。其中r的取值范圍為0～1，如果閾值r取值過小，很多節點會被錯誤地劃分為重疊節點，影響重疊劃分結果的準確性，但是當閾值r的取值接近1時，又會使該算法退化成非重疊社區發現算法。本文在N=1 000的人工數據集上測試選取不同閾值r時算法結果的收斂情況，根據圖4可以發現，當r大于0.04時，算法檢測到的社區數量和真實社區數量之比趨于穩定。所以，本文在后續的實驗中取r的值為0.05。

圖4 閾值r的收斂表現

根據圖5可以發現，隨著算法的最大迭代次數T取值的增大，算法的準確性會有增長的趨勢，但是過多的迭代次數會降低算法的運行速度。因為T大于20后，更多的迭代次數并沒有給算法結果帶來很大的提升，所以在本文中，選取T的值為20。

圖5 迭代次數T的收斂表現

3.4 實驗結果

本文首先在6個規模不同的真實網絡數據集上對算法的性能和效果進行對比驗證，這些對比算法的參數設置如下：對于Copra，v被設置為1到10不等，取值間隔為1；對于CPM算法，k被設置為2到8不等，取值間隔為1；對于LFM算法，設置α的值為1.0；對于SLPA和L-SLPA，將迭代次數T設置為20，過濾參數r被設置為0.05。實驗結果選取各參數下得到的最大值進行對比。

本文實驗將5種算法在規模不同的真實網絡上各運行100次，對得到的運行時間取均值，最終的結果如圖6所示。可以發現，當網絡的節點數較少時，除SLPA外，其余4種算法的時間開銷相當。但是隨著網絡規模的不斷增大，4種對比算法的運行時間明顯增加。L-SLPA的運行時間仍然呈現線性增長，并且遠低于其他4種算法的運行時間，效率更高，可擴展性更好。

(a)

同樣地，采用上述參數設置，將5種算法分別在每個數據集上運行10次，對得到的重疊模塊度QE取平均值，最終的結果如圖7所示。總體來看，當網絡規模較小時，Copra的劃分結果的重疊模塊度最高，但是隨著節點數量增加，劃分結果明顯有所下降。而L-SLPA在各網絡上的劃分結果都具有較高的重疊模塊度QE，SLPA次之。結果表明，L-SLPA能夠在不同規模的網絡中發現較高質量的重疊社區。

圖7 真實網絡劃分結果的重疊模塊度QE

為了測試L-SLPA是否能夠有效地降低標簽傳遞策略所引起的隨機性問題，使用SLPA和L-SLPA分別在N=1 000和N=5 000的LFR基準測試網絡上進行了100次社區發現，每次劃分得到的社區數量如圖8所示。可以發現，SLPA得到的社區數量隨機性較大，結果并不穩定。在N=1 000的LFR基準測試網絡上，得到的社區數量在65～95個之間波動；在N=5 000的LFR基準測試網絡上，得到的社區數量在352～396個之間波動。相同情況下，L-SLPA得到的社區數量波動較小，結果比較穩定。

圖8 LFR基準測試網絡上劃分的社區數量

最后，生成了4組不同參數的LFR基準測試數據集，結合式(5)，對SLPA和L-SLPA進行了性能對比。將兩種算法分別在每個數據集上運行10次，對得到的NMI值取平均值，最終結果如圖9所示。

圖9 LFR基準測試網絡實驗結果

總體上，隨著每個節點歸屬的社區數om和混合參數μ的增加，兩種算法的社區發現結果均有所下降。在N=1 000的LFR基準測試網絡中，L-SLPA的劃分結果和SLPA的劃分結果大致相等。然而隨著網絡規模的變大，當N=5 000時，相較于SLPA，L-SLPA的性能下降比較多。這是由于L-SLPA的第一階段執行了一次基于模塊度Q優化的非重疊社區劃分，而隨著網絡規模不斷增大，基于模塊度Q優化的方法的解析度問題便會逐漸凸顯出來，算法得到的社區數量有可能遠小于真實的社區數量，這會導致NMI值的下降。雖然此方法發現的社區數量小于實際情況，但是劃分得到的社區結構穩定，與實際情況吻合度較高，所以并不會影響社區發現結果的模塊度。

4 結 語

由于標簽傳遞策略的隨機性，SLPA的社區發現結果并不夠穩定。同時，SLPA初始的標簽分配需要消耗大量的資源。為了解決SLPA的這些缺點，本文基于SLPA提出一種更加高效的重疊社區發現算法，在算法的初始階段，基于模塊度Q優化對網絡進行一次非重疊社區劃分，對同社區的節點分配一個相同的標簽后再對邊界節點執行Speaker-Listener標簽傳播的迭代步驟。實驗結果表明，相較于其他重疊社區發現算法，L-SLPA運行速度快，具有更好的可擴展性，在降低了標簽傳播算法結果的隨機性的同時保證了結果的準確性。