一種基于節(jié)點影響力的重疊社區(qū)發(fā)現(xiàn)算法

姚 越，程曉輝

（北京勞動保障職業(yè)學院，北京 100029）

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

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

1 相關知識

1.1 COPRA 算法

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

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

1.2 網絡嵌入學習

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

2 NI-COPRA 算法設計

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

2.1 融合重要性與相似性的節(jié)點影響力

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

2.1.1 節(jié)點重要性度量

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

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

2.1.2 節(jié)點相似性度量

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

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

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

圖1 隨機游走過程示意圖

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

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

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

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

2.1.3 節(jié)點影響力計算

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

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

2.2 基于節(jié)點影響力的NI-COPRA 算法

2.2.1 算法節(jié)點更新策略

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

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

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

2.2.2 基于節(jié)點影響力的重疊社區(qū)NI-COPRA 算法實現(xiàn)

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

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

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

2 實驗結果與分析

為了驗證本文提出的NI-COPRA 算法的有效性，與COPRA 算法、LPANNI 算法[16]進行對比。本文實驗所有算法均采用Python3 實現(xiàn)，基本配置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]作為重疊社區(qū)的評價指標。其公式如式（14）所示

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

2.2 實驗數據集

2.2.1 真實網絡數據集。

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

表1 真實網絡數據集

2.2.2 人工生成網絡數據集。

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

表2 LFR 基準網絡數據集

2.3 實驗過程與結果分析

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

2.3.1 重要性算法驗證

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

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

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

2.3.2 社區(qū)發(fā)現(xiàn)準確性驗證

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

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

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

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

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

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

4 結束語

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