基于網絡嵌入的異質網絡重疊社區發現算法

趙宇紅，韓麗文

(內蒙古科技大學 信息工程學院，內蒙古 包頭 014010) E-mail：zhaoyuhong35@163.com

1 引 言

真實世界中存在著各種各樣的網絡，這些網絡中的實體可以抽象為節點，而實體間的聯系可以抽象為邊.為了挖掘這些節點和邊的豐富信息，社區發現研究隨之而生.社區發現，是指將網絡中相似性高的節點劃分到個同一社區中，使得社區內節點聯系強于社區間聯系.社區發現可以為個性化服務、信息推送、疾病傳播中斷、信息檢索等提供數據.2009年之前對于社區發現的研究都集中在同質網絡，即將所有的節點和邊都看作是同一種.但是現實中的網絡大多是異質的，即網絡中有多種類型的節點和邊，異質信息網絡[1]包含更多的信息和更豐富的語義.另一方面，社區具有重疊性是真實社區的一個顯著特征，某些節點并不僅存在于單一社區，可能同時屬于多個社區，這些節點被稱為重疊節點，它們所屬的社區被稱為重疊社區.對異質網絡進行重疊社區發現，能夠更加準確的描述網絡真實的結構信息，因此研究異質網絡重疊社區具有突出的現實意義.

隨著社區發現的概念被提出，學者們相繼提出了很多社區發現算法，如基于分裂的算法，基于派系過濾的算法，基于局部擴展的算法，基于標簽傳播的算法等.其中標簽傳播算法因接近線性的時間復雜度且不需要提前指定社區的個數而被廣泛的應用于大規模網絡的社區劃分.擴展標簽傳播算法SLPA[2](Speaker-listener Label Propagation Algorithm)通過定義節點標簽序列來存儲節點歷史標簽信息，可以用于重疊社區的發現.但是SLPA算法忽略了網絡中節點和鏈接的多樣性，所以不適宜直接用于異質網絡社區發現，且算法在標簽傳播過程中心節點的隨機選取方法，造成了社區發現的結果不穩定.

元路徑[3]是可以用來捕獲異質網絡豐富語義信息的獨特屬性.基于元路徑的相似性度量是異質網絡中相似性度量的一個重要方法，如PathSim算法、HeteSim算法和AvgSim算法等.但這些方法僅關注了路徑中所包含的節點，并沒有考慮是否覆蓋了網絡中所有類型的節點，這將降低相似性的度量精度，進而影響社區劃分的質量.基于元路徑的網絡嵌入學習，可以深度學習、訓練以獲得更精確的相似性度量，也大大降低元路徑對模型限制的程度.

在對現有異質網絡社區發現算法的學習及問題分析的基礎上，為解決上述問題，本文結合異質網絡嵌入模型和節點排序方法對SLPA算法進行改進，在異質網絡重疊社區下提出了一種基于網絡嵌入模型的標簽傳播算法(Network Embedding-based Lable Propagation Algorithm，NELPA).該算法首先用節點排序方法來確定標簽傳播過程中心節點更新的順序，然后通過結合元路徑和Skip-gram模型，得到任意類型節點對間的相似性值，以該相似性值對標簽傳播進行指導，最終完成社區發現.

本文的貢獻歸結如下：

1)在異質網絡中提出一種基于網絡嵌入的相似性度量方法，該方法在構建元路徑集合并學習元路徑權重后，通過對不同元路徑下的相似性度量進行加權融合.方法充分考慮了節點類型、節點關聯及元路徑所表達的不同語義，提高了節點相似性準確率；

2)提出了一種基于鄰居節點影響力的節點排序方法SAIN(Sorting Algorithm based on the Influence of Neighbor-nodes)，通過引入節點相似性來改進LeaderRank算法，提升了排序算法的有效性；

3)將異質網絡嵌入學習所獲取的的節點相似性及節點排序SAIN方法，分別用于標簽傳播的判定依據及中心節點更新策略，克服了SLPA算法的局限性，提出了一種可用于異質網絡重疊社區發現算法NELPA.

2 相關知識介紹

2.1 SLPA算法

SLPA算法通過定義節點標簽列表，使節點可以保留歷史標簽信息，從而可用于重疊社區發現.該算法描述如下：

1)為每一個節點的標簽列表初始化一個唯一的標簽；

2)隨機選擇一個節點作為中心節點listener，該節點的鄰居節點就為speaker；每一個speaker將統計自己的標簽列表中各標簽出現的次數，將出現次數最多的那個標簽傳遞給listener；Listener將統計所有speaker傳遞過來的標簽個數，將出現次數最多的那個標簽加入到它的標簽列表中.重復該過程直到所有的節點都更新完成；

3)重復上述過程，直到達到最大迭代次數，最后，根據閾值和標簽信息將具有相同標簽的節點劃分到同一社區.

SLPA算法作為經典的標簽傳播算法LPA的改進版，繼承了算法的效率及有效性，但仍存在如下問題：

1)算法假定網絡中所有的節點和邊都是一種類型，不適合直接應用于異質網絡中；

2)隨機選擇listener，會造成每一次標簽傳播過程中節點更新順序不同，影響算法的穩定性；

3)在listener選擇由speaker傳遞過來的標簽時，僅以標簽出現次數作為相似性度量指標使得傳播的準確性較低.

2.2 網絡嵌入模型

網絡嵌入旨在用低維的向量表示網絡的結構或內容，用低維的連續特征表示原有的高維離散特征，不僅能獲取數據之間的相似性而且能夠緩解數據的稀疏性.并且由于低維的向量容易被機器學習算法處理，被有效的運用到社區發現領域.

DeepWalk是第一個被用于社區發現領域的網絡嵌入模型，其主要思想是利用自然語言處理中的Skip-gram模型[4]來進行網絡中節點的向量表示.Node2vec模型[5]改進了DeepWalk節點游走的方式，將廣度優先搜索和深度優先搜索引入到隨機游走序列生成過程中去，能夠更好地反映網絡結構.以上幾種模型都是用于同質網絡的嵌入模型.Dong Y[6]提出的metapath2vec和metapath2vec++模型通過基于元路徑的隨機游走得到異質網絡節點序列，然后基于Skip-gram模型進行節點嵌入.HIN2Vec模型[7]的核心是一個神經網絡模型，不僅能學習節點的嵌入向量，還可以學習元路徑的嵌入向量.AttrHIN2Vec模型[8]利用基于元路徑隨機游走的節點屬性信息和權重信息來捕獲大規模異質網絡中的潛在特征向量.張等人[9]考慮異質網絡自身的聚類結果，利用隨機梯度下降算法學習異質網絡節點的低維嵌入表示.CNE[10]算法通過結合節點嵌入和社區嵌入，把社區嵌入表示為低維空間中的高斯分布，從而獲得融合結構信息和屬性信息的節點表示.

3 NELPA算法

3.1 相關概念

定義1.異質信息網絡.對于一個信息網絡G=(V，E，T，R)，其中V表示網絡中節點的集合，E表示邊集合，T是節點類型集合，R是邊類型集合.當網絡中的節點類型數量|T|>1或邊類型數量|R|>1時，此時的信息網絡稱為異質信息網絡.

定義2.網絡模式.網絡模式是帶有對象類型映射τ：V→T和鏈接映射φ：E→R的異質網絡G=(V，E，T，R)的元模板，記為TG=(T，R).

定義4.網絡嵌入.通過將一個節點嵌入到一個新的嵌入空間中，使得相似的節點在嵌入空間中的距離相近，節點在嵌入空間中的向量表示就為該節點的嵌入向量.

3.2 NELPA算法的基本思想

本文提出的基于異質網絡嵌入模型的標簽傳播算法NELPA，通過改進傳統SLPA算法的中心節點更新方式，融合網絡嵌入模型中多條元路徑對應的節點相似性并將其運用到標簽傳播過程中，從而提升算法的穩定性和準確性，完成異質網絡重疊社區發現.該算法主要包含兩個部分：網絡嵌入模塊和NELPA模塊.本文的算法框架如圖1所示.

圖1 NELPA算法框架圖Fig.1 NELPA algorithm frame diagram

3.3 基于網絡嵌入模型的節點相似性度量

該模塊首先構建元路徑集合，然后進行元路徑權重學習，通過多條元路徑的遍歷得到節點序列，應用Skip-gram模型進行訓練得到不同元路徑下節點相似性，并對同一節點對間的相似性進行加權融合得到最終的節點相似性.

3.3.1 構建元路徑集合

元路徑是異質網絡中節點關聯的路徑，能豐富的表達對象間的語義信息.不同元路徑表達了不同的含義和不同的鏈接網絡，也就導致網絡分析結果的不同.為了更準確的度量節點相似性，本文采用多條元路徑對網絡進行遍歷.通過給不同元路徑賦予不同的權重，來表明不同元路徑對網絡嵌入表征學習的不同重要程度.

在構建元路徑集合時，給定網絡模式、源類型對象和目標類型對象后可構建出很多不同長度的元路徑，但是絕大多數的元路徑沒有實際的語義信息，如果考慮全部的元路徑會增加計算量和計算時間而且由于較長的元路徑會降低相似性的精度.所以為了保證效率的同時詮釋網絡豐富且真實的信息，我們在設定元路徑集合時，要保證能夠覆蓋所有類型的節點，介于上述，本文將元路徑長度l設為2～5.從而構建元路徑集合P={p1，p2，…，pr}，其中p為元路徑，r為元路徑條數.

3.3.2 基于邊類型概率計算元路徑權重

現有的確定元路徑權重的方法大多是基于元路徑實例數這一指標的.在大型網絡中，各類型節點間的連邊數量差別很大.如在DBLP數據集中，每一篇論文具有的關鍵詞的數目遠遠超過論文作者數和論文所投稿的會議/期刊數目，即論文與關鍵字間的連邊數目遠遠大于與其它類型節點的連邊數，包含論文-關鍵字這種連邊的元路徑數目也遠多于沒有包含這類型連邊的元路徑.如果以元路徑實例數作為元路徑權重的一個指標，會導致包含這種極大數目邊類型的元路徑的權重遠遠超過其它元路徑.為了消解這種極大邊類型對元路徑權重的過度影響，本文定義了邊類型概率，如第k條元路徑邊類型概率指標Fk如公式(1)所示：

(1)

其中，ng表示第g種連邊的數量，|R|為網絡中邊類型數，s為第k條元路徑所包含的連邊種類數.

第k條元路徑的權重θpk定義如公式(2)所示：

(2)

其中，mpk是第k條元路徑對應的路徑實例數，lpk是第k條元路徑的長度.由式(2)可以看出，基于邊類型概率的元路徑權重不僅考慮路徑的數量，而且考慮組成每條路徑的各段邊的類型.

元路徑權重歸一化如公式(3)所示：

(3)

利用公式(3)對元路徑集合P={p1，p2，…，pr}進行權重學習，構建相對應的元路徑權重集合Wp={Wp1，Wp2，…，Wpr}，且Wp1+Wp2+…+Wpr=1.

3.3.3 異質信息網絡的節點相似性

Skip-gram是一個最初應用在自然語言處理中的簡單三層神經網絡模型，模型基于輸入的中心詞來預測上下文單詞出現的概率，結構如圖2(b)所示.

圖2 基于Skip-gram模型的相似性計算Fig.2 Similarity calculation based on skip-gram model

輸入層輸入中心詞的向量表示，通過設置窗口大小來指定中心詞的上下文詞匯出現的最大數.如給定窗口大小為m，那么會選擇中心詞前后各m個詞為中心詞的上下文詞匯.然后隱藏層將執行其權重矩陣和中心詞向量的點積運算，點積運算的結果是每個輸入詞的嵌入詞向量.輸出層是一個softmax回歸分類器，將計算其權重矩陣和輸入詞的嵌入詞向量的點積，然后用softmax激活函數計算在給定上下文的情況下每一個詞是輸出單詞的概率，即中心詞與上下文單詞共現的概率.

將Skip-gram模型應用到社會網絡分析中，如何將異質網絡結構轉化成類似于語料庫中連續的單詞，本文基于給定的多條元路徑對異質網絡進行遍歷，從而來得到異質網絡節點序列.以圖2(a)為例，在DBLP數據集中給定元路徑APTPA.假設當前節點是A類型的a1節點，那么下一步將遍歷尋找a1所有鄰居中的P類型節點，直到找到鄰居中所有的P類型節點后，這些P類型節點再繼續尋找它們的鄰居節點中所有T類型節點，如此反復迭代，直到遍歷完整個網絡.

我們將基于元路徑遍歷得到的節點序列類比為自然語言處理中的語料庫文本，其中每一個節點都看作是一個詞，給定窗口大小即確定了中心節點的鄰居范圍，最終模型輸出的概率即為中心節點vi與網絡中任意節點vj在第k條元路徑下的相似性概率值Spk(vi，vj)，其表述如公式(4)所示：

(4)

其中，Xvi表示節點vi的嵌入向量，·表示兩節點間嵌入向量的點積運算，點積運算值越大，則兩節點間的相似性就越大.為了保證輸出值的非負性，且將其映射為0-1之間的數值，使用以e為底的指數函數.

3.3.4 基于元路徑權重融合的節點相似性

此階段基于元路徑權重集合Wp={Wp1，Wp2，…，Wpr}對節點相似性進行加權融合.將不同元路徑遍歷得到的不同節點序列輸入到Skip-gram模型進行訓練得到的同一節點對間的相似性概率是不同的，基于任意一條元路徑pk得到的節點對相似性Spk(vi，vj)缺失其它元路徑的語義信息.因此，對不同元路徑下相同節點間的相似性值進行加權融合可以得到更加準確的相似性值.本文提出了節點相似性融合方法，其表述如公式(5)所示：

(5)

其中，r為元路徑條數.

3.4 NELPA算法

3.4.1 基于鄰居節點影響力的節點排序算法SAIN

網絡中節點的重要性是不同的，重要節點相較于其他節點更能影響網絡的布局，能更大程度影響網絡的流通性.現有的節點排序算法有很多，如度中心性、介數中心性、接近中心性、PageRank和LeaderRank[11]等.LeaderRank算法通過加入一個背景節點vg，得到一個與網絡中所有的節點雙向連接的強連通網絡，該算法在衡量社會網絡中節點的影響力等方面有著較好的表現.其表示如公式(6)所示：

(6)

(7)

其中，αi為節點vi的鄰居節點，SAIN值越大節點重要性就越大，將SAIN值進行降序排列，得到節點更新順序.

3.4.2 基于SLPA的改進的社區發現算法NELPA

1)為所有節點的標簽列表初始化一個唯一的標簽；

2)由公式(7)對網絡中所有節點進行排序，選擇當前未處理的SAIN值最大的節點為listener，其所有一階鄰居節點為speaker.Speaker將統計標簽列表中各標簽的個數，將個數最多的那個標簽傳遞給listener.Listener將對比自己與每個speaker的相似性值Sim(vi，vj)，選擇值最大的那個speaker所對應的標簽加入標簽列表中.若最大值speaker不止一個，那么將所有最大值speaker所對應的標簽出現次數最多的一個加入到標簽列表中.

3)重復第2步，直到達到最大迭代次數T.根據閾值和標簽信息完成社區劃分.

達到最大迭代次數后，每個節點都有T個標簽，每種標簽的概率反映了節點所屬社區的關聯強度，為了確定一個節點是否最終屬于一個社區，要執行閾值化過程.如果某一標簽的概率小于給定的閾值r，則把該類標簽從節點序列中刪除.閾值化后，具有相同標簽的節點被分到一組，形成一個社區.如果一個節點包含多個標簽，那么該節點屬于多個社區，是重疊節點.

NELPA算法具體描述如下：

算法1.NELPA(T，r)

[n，Nodes]=loadnetwork(G)；

FORi=1：nDO

Nodes(i).Mem=i

END FOR

FORt=1：TDO

FORi=1：nDO

Listener=max(sorted(SAIN))

Speakers=Listener.getNbs()；

FORj=1：Speakers.lenDO

LableList(j)=Speakers(j).frequent()；

IFlen(MaxSim(LableList))=1：

w=Listener.MaxSim(LableList)；

ELSE

w=Listener.MaxSim(LableList).frequent()

END IF

Listener.Mem.add(w)

END FOR

END FOR

END FOR

FORi=1：nDO

Remove Nodes(i)lables seen with probability

END FOR

4 實驗與分析

為驗證本文提出的基于邊類型概率的元路徑權重確定方法的合理性、基于鄰居節點影響力的節點排序算法SAIN的有效性和異質網絡社區發現算法NELPA的社區聚類效果，進行了以下的實驗.

4.1 數據集

本文數據集選取2個真實的異質網絡，其詳述如下：

1)DBLP數據集：本文實驗采用DBLP數據集的子網絡構建異質網絡，包含作者(Author，A)、會議(Conference，C)、論文(Paper，P)和術語(Term，T)4種節點.

2)LastFM數據集：該數據集在fm在線音樂系統截取，包含音樂家(Artist，A)、用戶(User，U)、音樂標簽(Tag，T)3種節點.

2個數據集參數如表1所示.

表1 數據集參數Table 1 Data set parameter

4.2 評價指標

社區發現經典的評價指標模塊度Q常被用來評價社區劃分的好壞，由于本文算法涉及到重疊社區的發現，所以選取衡量重疊社區劃分質量的擴展模塊度EQ[12]作為評價指標.其表示如公式(8)所示：

(8)

其中，m是網絡中連邊總數，Qi、Qj為節點vi、vj所屬的社區個數，Aij為網絡鄰接矩陣中的元素，ki、kj分別為節點vi、vj的度，Cy為第y個社區包含的節點集.EQ值取在0-1之內，值越大，意味著社區劃分的結構性越強.

4.3 結果與分析

4.3.1 元路徑選擇與權重確定

為盡可能得到每個節點與其它所有節點間的的相似性，在選擇元路徑時，要能夠涵蓋異質網絡中所有的節點類型.所以實驗中，綜合考慮節點類型和元路徑語義及長度后，對于DBLP數據集指定APA、APAPA、APCPA、APTPA這4條元路徑，LastFM數據集指定TAT、TUT、UAU、UTU這4條元路徑.由給定的元路徑集合對網絡遍歷之后，得到每一條元路徑對應的實例數.計算得到邊類型概率值后，再計算每條元路徑的歸一化權重值如表2中Wpk所示，表2中θ是只由元路徑實例數和路徑長度計算得到的每一條元路徑所對應的權重值.

表2 元路徑權重分配Table 2 Metapath weight allocation

在DBLP數據集中，對比每條元路徑所對應的Wpk值和θ值可以發現元路徑權重變化最明顯的是APCPA和APTPA，這兩條元路徑所包含的不同邊類型是P-T和P-C，P-T邊的數量約是P-C邊的8倍.APCPA的權重Wpk相較于θ提高了41.68%，而APTPA的權重Wpk相較于θ降低了45.44%.實際上，由期刊相連的兩個作者的關系比那些通過術語相連的關系更可信，因為許多術語能夠在不同的研究領域中使用，而作者通常更關注有限的研究主題.實驗中的這兩組數據能夠明顯的說明，本文提出的關于元路徑權重確定的方法能夠更好的反映實際的元路徑權重.

而在LastFM數據集中，對比每條元路徑所對應的Wpk值和θ值可以發現無明顯變化，這是因為該數據集中各類型邊數差距不是很大，導致邊類型對元路徑權重的影響很小.

由實驗中Fk指標對兩個數據集中元路徑權重的影響可以得出以下結論：本文提出的邊類型概率指標能夠更好的優化元路徑權重，由本文方法得到的元路徑權重相較與傳統只由路徑數和路徑長度確定的元路徑權重更接近對現實世界的理解.

4.3.2 節點排序算法驗證

在該部分實驗中，用PageRank算法、LeaderRank算法和本文提出的SAIN算法對DBLP數據集中的會議/期刊類節點進行排序，取排序結果前10的節點，排序結果如表3所示.為了對排序算法的結果進行初步評估，我們在計算機科學知識發現網上(AMine)根據CCF Level對DBLP數據集中的會議/期刊進行分類，A類會議的檔次高于B類會議.發現3種算法給出的排名靠前的會議基本為A類會議，靠后的是B類會議.但是數據集中的CVPR和WWW這兩個A類會議并沒有排在前10，而一些B類會議卻排在了前10.這是因為排名算法更多考慮的是網絡的拓撲結構(節點的連邊情況)而忽略了會議的影響因子，即排序算法更多關注的是在會議上所發表的論文數目，而并非是論文被引數所占論文的比例.

表3 DBLP數據集會議/期刊類節點排序Table 3 DBLP data set meeting/journal node sorting

本文采用傳染病SIR模型[13]來評估排序算法的好壞，選定初始感染節點，擬合病毒傳播過程，以一段時間后感染節點的數目衡量初始感染節點的傳播影響力.若一個排序算法的結果使得網絡傳播速度快于其它算法，說明由該排序算法得到的排序結果使得節點具有好的傳播影響力，即可以說明該排序算優于其它排序算法.圖3顯示了以每種排序算法排序前10的節點為初始感染源進行SIR傳播的過程，其中時間步長(t)為橫坐標，累計感染數(N)為縱坐標.由圖3可見，本文提出的SAIN算法較PageRank算法和LeaderRank算法有著更快的增長速度和更高的被感染的飽和人數，說明由SAIN排序算法得到的重要節點對整個網絡進行傳播時，其速度更快范圍更廣.即在識別高影響力節點方面，SAIN較PageRank算法和LeaderRank算法更有效.

圖3 SAIN與LeaderRank、PageRank算法對比驗證Fig.3 Comparison and verification of SAIN，LeaderRank and PageRank algorithms

4.3.3 社區發現準確性驗證

為了驗證NELPA算法的準確性，本文選擇原始SLPA算法以及近幾年效果較好的一些異質網絡社區發現算法作為對比算法.表4所示為不同算法在數據集DBLP和LastFM上得到的社區聚類效果，用EQ進行評價.

表4 NELPA算法和對比算法在不同數據集的EQ值比較Table 4 Comparison of EQ values between NELPA algorithm and comparison algorithm in different data sets

各算法參數設置如下：SLPA算法實驗最大迭代次數T設為100，標簽閾值r設為0.35.HCD_all[14]算法在兩個數據集上選擇表2給出的所有元路徑進行元路徑融合實驗.HIN2Vec算法設定以每個節點為起始游走節點的游走步長為1280，向量維度為128.Metapath2vec算法在DBLP數據集上指定單條元路徑APCPA，LastFM數據集上指定UTU，以每個節點為起始節點游走次數為1000次，隨機游走序列長度為100，窗口大小為7，向量維度為128.本文NELPA算法使用表2列出的所有元路徑，窗口大小為7，向量維度為128.

由表4可知，本文提出的NELPA算法的EQ值高于其它算法.這是因為NELPA算法不僅在標簽傳播算法中通過融合多條具有不同權重的元路徑來體現網絡的異質性，而且以節點相似性和標簽數同時作為標簽傳播的依據提升了算法的準確性.因此，本文提出的NELPA算法對不同類型的異質網絡具有良好的表征學習能力，可有效的提高異質網絡重疊社區發現的模塊度，得到的社區聚類效果更好.

5 總結與展望

本文研究了異質信息網絡中的重疊社區發現問題，提出了一種基于網絡嵌入的標簽傳播算法NELPA.首先，考慮了不同的元路徑的權重，通過構建網絡嵌入模型學習并完成了單條元路徑下節點相似性度量并進行了多路徑加權融合，提升了節點相似性準確度，并用該相似性來指導標簽傳播過程.其次，提出一種新的節點排序方法SAIN，并用于節點更新順序策略，加速了標簽傳播速率且提高了傳播的穩定性，提升了社區發現的準確性.實驗結果表明，本算法對不同的網絡具有良好的表征學習能力，可有效的應用于網絡社區發現領域.但是，NELPA只是基于靜態網絡的，現實中的網絡是動態變化的，所以，未來可以進一步考慮時間因素，用于動態異質網絡社區發現.