一種基于節點影響力的重疊社區發現算法

姚 越，程曉輝

（北京勞動保障職業學院，北京 100029）

復雜網絡是復雜系統的高度抽象，可以用節點和邊構建的圖模型表示，其中社區結構性表達的是網絡中節點的聚合群體特性，該特性的挖掘即社區發現[1]是通過節點與鄰居節點間的緊密聯系程度進行社區聚類，同一社區彼此緊密連接而不同社區節點聯系相對較弱[2]。社區發現對理解復雜網絡系統的功能和組織至關重要[3]。

經典的重疊社區發現算法是Gregory[4]提出的COPRA 算法，該算法是一個多標簽傳播算法，操作簡單且執行較高效，但在更新標簽中存在傳播隨機性和結果魯棒性差的問題。Ma 等[5]在COPRA 的基礎上提出了COPRAPC 算法，該算法通過聚類系數限制每個節點擁有的標簽數量。張靜宜[6]提出了基于節點PR 值和優化Jaccard 相似性指標的DSLPA，改善了SLPA 標簽傳播隨機性的問題。王林等[7]提出以LeaderRank 重要性排序算法作為SLPA 算法節點標簽更新順序的依據，獲得了更穩定的重疊社區生成結果。郭峰等[8]以DOCNet 算法框架，在初始節點選取和節點隸屬度計算2 個方面尋求改進，提出了改進的重疊社區發現算法DOCLLE。陳晶等[9]提出基于COPRA 改進的OCKELP多標簽傳播算法，融合k-shell 解決了COPRA 選擇初始節點隨機性的問題。賈慧娟等[10]提出的COPRA-S 算法，以邊緣節點為中心的橋梁節點群內進行標簽傳播，以此提升發現重疊社區的速度。不同研究者針對標簽傳播的隨機性進行改進，但在標簽傳播中均沒有充分考慮節點的屬性信息及節點間關聯影響，對于COPRA隨機性和魯棒性的改進仍是一個開放性問題，本文提出了一種基于節點影響力的標簽傳播算法NI-COPRA（Node Influence based-Community Overlap Propagation Algorithm），通過對節點重要性的量化解決標簽傳播過程中選擇初始節點的隨機性，利用節點影響力的度量改善標簽傳播過程中選取鄰居節點標簽的隨機性，以挖掘更加穩定的重疊社區。

1 相關知識

1.1 COPRA 算法

COPRA 算法是較經典的多標簽傳播算法，COPRA中定義每個節點最多屬于v 個社區，每個標簽隸屬系數為b（c，u）表示節點u 從屬社區c 的強度，每個節點可以有多個標簽。算法初始，節點用自身標號作為標簽，隸屬系數為1，隨機選取1 個初始節點，在鄰居節點間進行標簽傳播和更新，在標簽更新的過程中，通過設置v 值篩選出隸屬系數大于1/v 的標簽，通過多次迭代發現重疊社區。隸屬系數的計算方式如式（1）所示

式中：N（u）為節點u 的鄰居節點集合；bt-1（c，y）為上次迭代節點u 的鄰居節點標簽信息。

1.2 網絡嵌入學習

網絡嵌入是用低維的連續特征表示網絡原有的高維離散特征，其目的是為獲取網絡結構數據之間的相似性并改善稀疏性。近年來，眾多網絡嵌入方法應用于社區發現，并取得了一定研究成果。如DeepWalk[11]首次采用自然語言處理中的模型與社交網絡領域的網絡結構結合，較貼切地表示了網絡拓撲結構。Node2vec模型[12]改進了DeepWalk 節點游走的方式，將廣度優先遍歷和深度優先遍歷引入到隨機游走中，較好地反映了網絡真實結構，且具有較高的靈活性和普適性。Line[13]考慮了節點1 階和2 階相似性，實驗結果表明，該模型適用于規模較大網絡中可應對傳統梯度下降方法的限制。文獻[12]中實驗結果顯示，在多標簽分類任務上，Node2vec 取得了比Deepwalk 和LINE 算法較好的劃分效果。本文采用Node2vec 模型遍歷網絡結構并生成節點序列，通過Skip-gram 模型訓練目標節點序列得到節點的低維向量表示。

2 NI-COPRA 算法設計

COPRA 算法在初始節點的選擇及標簽傳播時存在隨機性的問題，本文所提NI-COPRA 算法，首先采用基于信息熵的節點重要性排序算法確定節點更新順序，其次在融合節點重要性與節點相似性的基礎上，提出1 種計算節點影響力的方法定義隸屬系數進行標簽傳播，以發現準確穩定的重疊社區。

2.1 融合重要性與相似性的節點影響力

本文提出NI-COPRA 算法中節點通過鄰居節點的綜合影響力選擇標簽，節點影響力是將節點重要性與相似性進行融合，應用在隸屬系數中進行標簽傳播，獲得更準確穩定的重疊社區。

2.1.1 節點重要性度量

現有研究中具有眾多的節點重要性度量方法，例如節點度、中心度、介數中心性及vote 算法等。信息熵[14]以特定信息的出現概率量化來間接表達信息的價值，文獻[14]以信息熵的角度度量復雜網絡中的關鍵節點識別，不僅在信息屬性的準確度量有很好的效果且在計算性能與其他一些經典排序算法相比，獲得了較好性能。本文提出了基于信息熵的EnRenew[15]重要性算法，從局部范圍開始最終獲得網絡的重要性排序，在選取了初始最大信息熵的節點之后，通過多階步長的鄰居節點迭代削弱傳播能力獲得最終網絡的節點排序。相比于傳統排序算法僅用節點1 階信息，節點的熵可以衡量節點的多階局部信息，從而使得后續迭代選取關鍵節點更加有效。受到文獻[13]的啟發，本文提出的算法使用2 階步長迭代。節點初始重要性公式如式（2）所示

式中：ul為節點ν 通過l 步長達到的節點集合，例如ul是節點ν 的一階鄰居集合；k 為網絡中平均度，當k 為整數時，En＜k＞可以看作是k 正則圖中任意一個節點的信息熵。

2.1.2 節點相似性度量

本文中對于節點相似性的量化是通過節點嵌入學習而獲得的。首先，基于Node2vec 模型遍歷網絡拓撲結構生成節點序列，通過Skip-gram 訓練目標節點序列得到節點低維向量表示，最后利用余弦相似度計算節點間的相似值。

Node2vec 模型中提出1 種有偏的隨機游走算法，可同時滿足節點之間的同質性與結構相似性。給定一個源節點μ，假設隨機游走的步長為固定長度L，從源節點μ 開始，使用式（5）生成鄰居序列

式中：ci為隨機游走中的第i 個節點；Z 為歸一化因子，πνx為節點ν 到節點x 轉移概率；πνx=αpq（t，x）·ωνx，α 為p、q 參數確定的帶偏置搜索算子。具體游走過程如圖1所示，p 控制訪問ν 后返回t 的概率，q 控制圖中未發現部分的概率。當p＞max（q，l）時，采樣不會回溯；當p＜max（q，l）時，采樣會更傾向于返回上1 個節點。當q＜1 時，采樣會傾向遍歷遠離t 的節點，即深度優先遍歷；當q＞1時，采樣會傾向遍歷周圍的節點，即廣度優先遍歷。

圖1 隨機游走過程示意圖

Skip-gram 是一種語言模型，該模型能夠極大化單詞出現在上下文中的概率。其是使用1 個單詞來預測句子。模型優化目標函數如式（6）所示

式中：w 為當前詞；c 為類似自然語言的語料庫；Context（w）為詞的上下文。在本文中，該語料庫為網絡中節點隨機游走后產生的線性序列。

該模型是由輸入層、隱含層和輸出層組成。輸入層和隱含層之間的權重矩陣為W1，隱含層和輸出層之間的權重矩陣為W2。如式（7）所示

通過Skip-gram 嵌入得到節點的特征向量，用余弦相似度計算作為節點間相似性的度量標準，節點相似性公式如式（8）所示

2.1.3 節點影響力計算

標簽傳播過程中，NI-COPRA 算法充分考慮節點自身，及其鄰居節點在網絡中的不同重要性與動態相關性，結合節點重要性與節點間相似性度量量化鄰居節點的綜合影響力，進一步應用在隸屬系數計算中使得節點標簽的更新更為合理。鄰居節點v 對節點u 的影響力定義如式（9）所示

式中：Ng（u）為節點u 的鄰居節點集合。

2.2 基于節點影響力的NI-COPRA 算法

2.2.1 算法節點更新策略

（1）在標簽傳播過程中，節點接收到來自鄰居節點的主標簽組成標簽集合，es（c，b）表示為c 社區，b 為隸屬系數

（2）標簽傳播過程中考慮鄰居節點的影響力，計算更新標簽后節點u 對社區c 的隸屬系數

（3）對剩余標簽的歸屬系數進行歸一化

2.2.2 基于節點影響力的重疊社區NI-COPRA 算法實現

NI-COPRA 算法的具體算法步驟如下所述。

（1）節點重要性和影響力計算。初始化時將網絡中每個節點主標簽設置為節點ID 號，隸屬系數均設置為1。利用節點重要性得到每個節點信息熵S 并按升序排列得到序列E，通過Node2vec 模型生成節點序列，然后使用Skip-gram 訓練得到節點特征向量，利用余弦相似度公式（8）得到節點間的相似性值。利用式（9）計算網絡拓撲結構中的每個節點與鄰居節點的節點影響力值。

（2）標簽傳播。節點u 鄰居節點將主標簽（隸屬系數最大的標簽）傳遞給節點u，主標簽形成集合ES。利用式（11）更新標簽隸屬系數形成標簽集合，刪除隸屬系數小于，形成新的標簽集合。利用式（12）歸一化生成新的標簽集合ESu，該集合中隸屬系數最大的標簽作為主標簽Lu。

2 實驗結果與分析

為了驗證本文提出的NI-COPRA 算法的有效性，與COPRA 算法、LPANNI 算法[16]進行對比。本文實驗所有算法均采用Python3 實現，基本配置CPU 為Intel（R）Core（TM）I7-8700 CPU @ 3.20 GHz，內存為32 GB。

2.1 評價指標

2.1.1 標準互信息NMI

NMI 函數的取值為[0，1]，其取值越大表示與標準結果越接近，NMI 評價指標如式（13）所示：

2.1.2 擴展模塊度EQ

使用擴展模塊度（EQ）[17]作為重疊社區的評價指標。其公式如式（14）所示

式中：m 為網絡中連邊總數；Qi、Qj為節點νi、νj所屬的社區個數，Aij為網絡鄰接矩陣中的元素；ki、kj分別為節點νi、νj的度；Cy為第y 個社區包含的節點集合。EQ函數的取值為[0，1]，其取值越大，表示社區劃分的結果越有效。

2.2 實驗數據集

2.2.1 真實網絡數據集。

本文采用6 個真實網絡數據集，其中3 個小規模數據集，分別是cora 引文網絡數據集、wiki 數據集及CA-GrQc 科學合作網絡數據集，另外包括3 個中等規模數據集，分別是優良保密協議網絡PGP 數據集、condmat 科學論文作者的協作網絡數據集及cit-hepph高能物理現象引文網絡數據集。表1展示了數據集的具體信息。

表1 真實網絡數據集

2.2.2 人工生成網絡數據集。

本文使用LFR 基準發生器生成參數指定分布的人工生成網絡，om 代表重疊節點所屬社區個數，om 從2 到8 生成了7 個不同的網絡數據集，LFR 基準網絡中參數的具體信息見表2。

表2 LFR 基準網絡數據集

2.3 實驗過程與結果分析

本文實驗驗證了節點重要性排序算法與社區發現效果，其中節點重要性是通過SIR 模型進行傳播實驗對比，社區發現有效性是通過EQ 模塊度評價指標及NMI 標準化互信息指標進行驗證。

2.3.1 重要性算法驗證

本文采用SIR 模型驗證排序算法，選擇初始感染節點擬合病毒的傳播過程，一段時間后感染節點的規模衡量初始感染節點傳播影響力。圖2是本文所提的重要性算法與degree 算法、vote 算法及k-shell 算法進行傳播實驗對比。

圖2 各算法在不同時間t 下的F（t）變化情況

在相同傳播時間t 下，先到達穩定狀態且F（t）值較大表明網絡中的影響規模越大，傳播速度越快。

2.3.2 社區發現準確性驗證

（1）模塊度EQ 實驗結果分析。為了驗證本文NI-COPRA 算法社區劃分結果的有效性，該算法將COPRA 算法及LPANNI 算法作為對比實驗，重疊社區發現結果用EQ 指標進行評價。出于對實驗效果與有效性的考慮，參數p 和q 分別取0.25 和4，Skip-gram 模型隨機游走序列長度設置為80，窗口大小設置為5，向量維度設置為128，最大迭代次數T 設置為100，COPRA 算法中參數V 取值2～10，在每個數據集上均取最佳參數值，COPRA 算法運行10 次取平均EQ 值，LPANNI 算法及本文算法是穩定的社區發現算法取運行一次的EQ 值。實驗結果見表3。

表3 真實網絡數據集重疊模塊度EQ 值比較

表3展示了各算法在6 個真實網絡數據集上EQ值。NI-COPRA 劃分的重疊社區模塊化度量值EQ 是明顯高于COPRA 算法和LPANNI 算法的。本文算法在小規模數據集和中等規模數據集上，都發揮了很好的優勢。

（2）NMI 實驗結果分析。在人工生成網絡G 上，將對比實驗COPRA 算法在7 個數據集上取平均NMI 值，LPANNI 算法和本文NI-COPRA 穩定算法取1 次運行的NMI 值，最終NMI 的評價對比結果如圖3所示。

圖3展示了各算法在人工生成網絡7 個數據集上NMI 值。由圖3可知，對于具有復雜重疊社區的網絡，NI-COPRA 在復雜重疊社區發現中表現優良，準確性和穩定性都比之前的標簽傳播算法有了很大改進。

圖3 人工生成網絡不同om 精度下NMI 值對比

4 結束語

本文在COPRA 算法基礎上，主要針對其標簽傳播過程中存在隨機性及發現重疊社區穩定性差的問題，提出了1 種基于節點影響力的重疊社區發現算法NI-COPRA。首先，通過信息熵量化節點的個體價值，進行重要性度量以確定節點標簽更新順序；其次，引入節點影響力進行標簽選擇，利用節點重要性與相似性融合確定影響力，更新社區隸屬系數并進行標簽傳播，在迭代更新中，以穩定的節點標簽確定歸屬的社區。在真實網絡和人工生成網絡上驗證了本文算法的有效性。在今后將進一步優化算法，引入到有向加權網絡中及動態重疊網絡中，滿足如今更多的復雜網絡結構需要。