基于網(wǎng)絡(luò)嵌入的異質(zhì)網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法

趙宇紅，韓麗文

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

1 引 言

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

隨著社區(qū)發(fā)現(xiàn)的概念被提出，學(xué)者們相繼提出了很多社區(qū)發(fā)現(xiàn)算法，如基于分裂的算法，基于派系過濾的算法，基于局部擴(kuò)展的算法，基于標(biāo)簽傳播的算法等.其中標(biāo)簽傳播算法因接近線性的時(shí)間復(fù)雜度且不需要提前指定社區(qū)的個(gè)數(shù)而被廣泛的應(yīng)用于大規(guī)模網(wǎng)絡(luò)的社區(qū)劃分.擴(kuò)展標(biāo)簽傳播算法SLPA[2](Speaker-listener Label Propagation Algorithm)通過定義節(jié)點(diǎn)標(biāo)簽序列來存儲(chǔ)節(jié)點(diǎn)歷史標(biāo)簽信息，可以用于重疊社區(qū)的發(fā)現(xiàn).但是SLPA算法忽略了網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈接的多樣性，所以不適宜直接用于異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，且算法在標(biāo)簽傳播過程中心節(jié)點(diǎn)的隨機(jī)選取方法，造成了社區(qū)發(fā)現(xiàn)的結(jié)果不穩(wěn)定.

元路徑[3]是可以用來捕獲異質(zhì)網(wǎng)絡(luò)豐富語義信息的獨(dú)特屬性.基于元路徑的相似性度量是異質(zhì)網(wǎng)絡(luò)中相似性度量的一個(gè)重要方法，如PathSim算法、HeteSim算法和AvgSim算法等.但這些方法僅關(guān)注了路徑中所包含的節(jié)點(diǎn)，并沒有考慮是否覆蓋了網(wǎng)絡(luò)中所有類型的節(jié)點(diǎn)，這將降低相似性的度量精度，進(jìn)而影響社區(qū)劃分的質(zhì)量.基于元路徑的網(wǎng)絡(luò)嵌入學(xué)習(xí)，可以深度學(xué)習(xí)、訓(xùn)練以獲得更精確的相似性度量，也大大降低元路徑對(duì)模型限制的程度.

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

本文的貢獻(xiàn)歸結(jié)如下：

1)在異質(zhì)網(wǎng)絡(luò)中提出一種基于網(wǎng)絡(luò)嵌入的相似性度量方法，該方法在構(gòu)建元路徑集合并學(xué)習(xí)元路徑權(quán)重后，通過對(duì)不同元路徑下的相似性度量進(jìn)行加權(quán)融合.方法充分考慮了節(jié)點(diǎn)類型、節(jié)點(diǎn)關(guān)聯(lián)及元路徑所表達(dá)的不同語義，提高了節(jié)點(diǎn)相似性準(zhǔn)確率；

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

3)將異質(zhì)網(wǎng)絡(luò)嵌入學(xué)習(xí)所獲取的的節(jié)點(diǎn)相似性及節(jié)點(diǎn)排序SAIN方法，分別用于標(biāo)簽傳播的判定依據(jù)及中心節(jié)點(diǎn)更新策略，克服了SLPA算法的局限性，提出了一種可用于異質(zhì)網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法NELPA.

2 相關(guān)知識(shí)介紹

2.1 SLPA算法

SLPA算法通過定義節(jié)點(diǎn)標(biāo)簽列表，使節(jié)點(diǎn)可以保留歷史標(biāo)簽信息，從而可用于重疊社區(qū)發(fā)現(xiàn).該算法描述如下：

1)為每一個(gè)節(jié)點(diǎn)的標(biāo)簽列表初始化一個(gè)唯一的標(biāo)簽；

2)隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為中心節(jié)點(diǎn)listener，該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)就為speaker；每一個(gè)speaker將統(tǒng)計(jì)自己的標(biāo)簽列表中各標(biāo)簽出現(xiàn)的次數(shù)，將出現(xiàn)次數(shù)最多的那個(gè)標(biāo)簽傳遞給listener；Listener將統(tǒng)計(jì)所有speaker傳遞過來的標(biāo)簽個(gè)數(shù)，將出現(xiàn)次數(shù)最多的那個(gè)標(biāo)簽加入到它的標(biāo)簽列表中.重復(fù)該過程直到所有的節(jié)點(diǎn)都更新完成；

3)重復(fù)上述過程，直到達(dá)到最大迭代次數(shù)，最后，根據(jù)閾值和標(biāo)簽信息將具有相同標(biāo)簽的節(jié)點(diǎn)劃分到同一社區(qū).

SLPA算法作為經(jīng)典的標(biāo)簽傳播算法LPA的改進(jìn)版，繼承了算法的效率及有效性，但仍存在如下問題：

1)算法假定網(wǎng)絡(luò)中所有的節(jié)點(diǎn)和邊都是一種類型，不適合直接應(yīng)用于異質(zhì)網(wǎng)絡(luò)中；

2)隨機(jī)選擇listener，會(huì)造成每一次標(biāo)簽傳播過程中節(jié)點(diǎn)更新順序不同，影響算法的穩(wěn)定性；

3)在listener選擇由speaker傳遞過來的標(biāo)簽時(shí)，僅以標(biāo)簽出現(xiàn)次數(shù)作為相似性度量指標(biāo)使得傳播的準(zhǔn)確性較低.

2.2 網(wǎng)絡(luò)嵌入模型

網(wǎng)絡(luò)嵌入旨在用低維的向量表示網(wǎng)絡(luò)的結(jié)構(gòu)或內(nèi)容，用低維的連續(xù)特征表示原有的高維離散特征，不僅能獲取數(shù)據(jù)之間的相似性而且能夠緩解數(shù)據(jù)的稀疏性.并且由于低維的向量容易被機(jī)器學(xué)習(xí)算法處理，被有效的運(yùn)用到社區(qū)發(fā)現(xiàn)領(lǐng)域.

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

3 NELPA算法

3.1 相關(guān)概念

定義1.異質(zhì)信息網(wǎng)絡(luò).對(duì)于一個(gè)信息網(wǎng)絡(luò)G=(V，E，T，R)，其中V表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E表示邊集合，T是節(jié)點(diǎn)類型集合，R是邊類型集合.當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)類型數(shù)量|T|>1或邊類型數(shù)量|R|>1時(shí)，此時(shí)的信息網(wǎng)絡(luò)稱為異質(zhì)信息網(wǎng)絡(luò).

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

定義4.網(wǎng)絡(luò)嵌入.通過將一個(gè)節(jié)點(diǎn)嵌入到一個(gè)新的嵌入空間中，使得相似的節(jié)點(diǎn)在嵌入空間中的距離相近，節(jié)點(diǎn)在嵌入空間中的向量表示就為該節(jié)點(diǎn)的嵌入向量.

3.2 NELPA算法的基本思想

本文提出的基于異質(zhì)網(wǎng)絡(luò)嵌入模型的標(biāo)簽傳播算法NELPA，通過改進(jìn)傳統(tǒng)SLPA算法的中心節(jié)點(diǎn)更新方式，融合網(wǎng)絡(luò)嵌入模型中多條元路徑對(duì)應(yīng)的節(jié)點(diǎn)相似性并將其運(yùn)用到標(biāo)簽傳播過程中，從而提升算法的穩(wěn)定性和準(zhǔn)確性，完成異質(zhì)網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn).該算法主要包含兩個(gè)部分：網(wǎng)絡(luò)嵌入模塊和NELPA模塊.本文的算法框架如圖1所示.

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

3.3 基于網(wǎng)絡(luò)嵌入模型的節(jié)點(diǎn)相似性度量

該模塊首先構(gòu)建元路徑集合，然后進(jìn)行元路徑權(quán)重學(xué)習(xí)，通過多條元路徑的遍歷得到節(jié)點(diǎn)序列，應(yīng)用Skip-gram模型進(jìn)行訓(xùn)練得到不同元路徑下節(jié)點(diǎn)相似性，并對(duì)同一節(jié)點(diǎn)對(duì)間的相似性進(jìn)行加權(quán)融合得到最終的節(jié)點(diǎn)相似性.

3.3.1 構(gòu)建元路徑集合

元路徑是異質(zhì)網(wǎng)絡(luò)中節(jié)點(diǎn)關(guān)聯(lián)的路徑，能豐富的表達(dá)對(duì)象間的語義信息.不同元路徑表達(dá)了不同的含義和不同的鏈接網(wǎng)絡(luò)，也就導(dǎo)致網(wǎng)絡(luò)分析結(jié)果的不同.為了更準(zhǔn)確的度量節(jié)點(diǎn)相似性，本文采用多條元路徑對(duì)網(wǎng)絡(luò)進(jìn)行遍歷.通過給不同元路徑賦予不同的權(quán)重，來表明不同元路徑對(duì)網(wǎng)絡(luò)嵌入表征學(xué)習(xí)的不同重要程度.

在構(gòu)建元路徑集合時(shí)，給定網(wǎng)絡(luò)模式、源類型對(duì)象和目標(biāo)類型對(duì)象后可構(gòu)建出很多不同長度的元路徑，但是絕大多數(shù)的元路徑?jīng)]有實(shí)際的語義信息，如果考慮全部的元路徑會(huì)增加計(jì)算量和計(jì)算時(shí)間而且由于較長的元路徑會(huì)降低相似性的精度.所以為了保證效率的同時(shí)詮釋網(wǎng)絡(luò)豐富且真實(shí)的信息，我們?cè)谠O(shè)定元路徑集合時(shí)，要保證能夠覆蓋所有類型的節(jié)點(diǎn)，介于上述，本文將元路徑長度l設(shè)為2～5.從而構(gòu)建元路徑集合P={p1，p2，…，pr}，其中p為元路徑，r為元路徑條數(shù).

3.3.2 基于邊類型概率計(jì)算元路徑權(quán)重

現(xiàn)有的確定元路徑權(quán)重的方法大多是基于元路徑實(shí)例數(shù)這一指標(biāo)的.在大型網(wǎng)絡(luò)中，各類型節(jié)點(diǎn)間的連邊數(shù)量差別很大.如在DBLP數(shù)據(jù)集中，每一篇論文具有的關(guān)鍵詞的數(shù)目遠(yuǎn)遠(yuǎn)超過論文作者數(shù)和論文所投稿的會(huì)議/期刊數(shù)目，即論文與關(guān)鍵字間的連邊數(shù)目遠(yuǎn)遠(yuǎn)大于與其它類型節(jié)點(diǎn)的連邊數(shù)，包含論文-關(guān)鍵字這種連邊的元路徑數(shù)目也遠(yuǎn)多于沒有包含這類型連邊的元路徑.如果以元路徑實(shí)例數(shù)作為元路徑權(quán)重的一個(gè)指標(biāo)，會(huì)導(dǎo)致包含這種極大數(shù)目邊類型的元路徑的權(quán)重遠(yuǎn)遠(yuǎn)超過其它元路徑.為了消解這種極大邊類型對(duì)元路徑權(quán)重的過度影響，本文定義了邊類型概率，如第k條元路徑邊類型概率指標(biāo)Fk如公式(1)所示：

(1)

其中，ng表示第g種連邊的數(shù)量，|R|為網(wǎng)絡(luò)中邊類型數(shù)，s為第k條元路徑所包含的連邊種類數(shù).

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

(2)

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

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

(3)

利用公式(3)對(duì)元路徑集合P={p1，p2，…，pr}進(jìn)行權(quán)重學(xué)習(xí)，構(gòu)建相對(duì)應(yīng)的元路徑權(quán)重集合Wp={Wp1，Wp2，…，Wpr}，且Wp1+Wp2+…+Wpr=1.

3.3.3 異質(zhì)信息網(wǎng)絡(luò)的節(jié)點(diǎn)相似性

Skip-gram是一個(gè)最初應(yīng)用在自然語言處理中的簡單三層神經(jīng)網(wǎng)絡(luò)模型，模型基于輸入的中心詞來預(yù)測上下文單詞出現(xiàn)的概率，結(jié)構(gòu)如圖2(b)所示.

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

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

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

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

(4)

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

3.3.4 基于元路徑權(quán)重融合的節(jié)點(diǎn)相似性

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

(5)

其中，r為元路徑條數(shù).

3.4 NELPA算法

3.4.1 基于鄰居節(jié)點(diǎn)影響力的節(jié)點(diǎn)排序算法SAIN

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

(6)

(7)

其中，αi為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)，SAIN值越大節(jié)點(diǎn)重要性就越大，將SAIN值進(jìn)行降序排列，得到節(jié)點(diǎn)更新順序.

3.4.2 基于SLPA的改進(jìn)的社區(qū)發(fā)現(xiàn)算法NELPA

1)為所有節(jié)點(diǎn)的標(biāo)簽列表初始化一個(gè)唯一的標(biāo)簽；

2)由公式(7)對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行排序，選擇當(dāng)前未處理的SAIN值最大的節(jié)點(diǎn)為listener，其所有一階鄰居節(jié)點(diǎn)為speaker.Speaker將統(tǒng)計(jì)標(biāo)簽列表中各標(biāo)簽的個(gè)數(shù)，將個(gè)數(shù)最多的那個(gè)標(biāo)簽傳遞給listener.Listener將對(duì)比自己與每個(gè)speaker的相似性值Sim(vi，vj)，選擇值最大的那個(gè)speaker所對(duì)應(yīng)的標(biāo)簽加入標(biāo)簽列表中.若最大值speaker不止一個(gè)，那么將所有最大值speaker所對(duì)應(yīng)的標(biāo)簽出現(xiàn)次數(shù)最多的一個(gè)加入到標(biāo)簽列表中.

3)重復(fù)第2步，直到達(dá)到最大迭代次數(shù)T.根據(jù)閾值和標(biāo)簽信息完成社區(qū)劃分.

達(dá)到最大迭代次數(shù)后，每個(gè)節(jié)點(diǎn)都有T個(gè)標(biāo)簽，每種標(biāo)簽的概率反映了節(jié)點(diǎn)所屬社區(qū)的關(guān)聯(lián)強(qiáng)度，為了確定一個(gè)節(jié)點(diǎn)是否最終屬于一個(gè)社區(qū)，要執(zhí)行閾值化過程.如果某一標(biāo)簽的概率小于給定的閾值r，則把該類標(biāo)簽從節(jié)點(diǎn)序列中刪除.閾值化后，具有相同標(biāo)簽的節(jié)點(diǎn)被分到一組，形成一個(gè)社區(qū).如果一個(gè)節(jié)點(diǎn)包含多個(gè)標(biāo)簽，那么該節(jié)點(diǎn)屬于多個(gè)社區(qū)，是重疊節(jié)點(diǎn).

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 實(shí)驗(yàn)與分析

為驗(yàn)證本文提出的基于邊類型概率的元路徑權(quán)重確定方法的合理性、基于鄰居節(jié)點(diǎn)影響力的節(jié)點(diǎn)排序算法SAIN的有效性和異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法NELPA的社區(qū)聚類效果，進(jìn)行了以下的實(shí)驗(yàn).

4.1 數(shù)據(jù)集

本文數(shù)據(jù)集選取2個(gè)真實(shí)的異質(zhì)網(wǎng)絡(luò)，其詳述如下：

1)DBLP數(shù)據(jù)集：本文實(shí)驗(yàn)采用DBLP數(shù)據(jù)集的子網(wǎng)絡(luò)構(gòu)建異質(zhì)網(wǎng)絡(luò)，包含作者(Author，A)、會(huì)議(Conference，C)、論文(Paper，P)和術(shù)語(Term，T)4種節(jié)點(diǎn).

2)LastFM數(shù)據(jù)集：該數(shù)據(jù)集在fm在線音樂系統(tǒng)截取，包含音樂家(Artist，A)、用戶(User，U)、音樂標(biāo)簽(Tag，T)3種節(jié)點(diǎn).

2個(gè)數(shù)據(jù)集參數(shù)如表1所示.

表1 數(shù)據(jù)集參數(shù)Table 1 Data set parameter

4.2 評(píng)價(jià)指標(biāo)

社區(qū)發(fā)現(xiàn)經(jīng)典的評(píng)價(jià)指標(biāo)模塊度Q常被用來評(píng)價(jià)社區(qū)劃分的好壞，由于本文算法涉及到重疊社區(qū)的發(fā)現(xiàn)，所以選取衡量重疊社區(qū)劃分質(zhì)量的擴(kuò)展模塊度EQ[12]作為評(píng)價(jià)指標(biāo).其表示如公式(8)所示：

(8)

其中，m是網(wǎng)絡(luò)中連邊總數(shù)，Qi、Qj為節(jié)點(diǎn)vi、vj所屬的社區(qū)個(gè)數(shù)，Aij為網(wǎng)絡(luò)鄰接矩陣中的元素，ki、kj分別為節(jié)點(diǎn)vi、vj的度，Cy為第y個(gè)社區(qū)包含的節(jié)點(diǎn)集.EQ值取在0-1之內(nèi)，值越大，意味著社區(qū)劃分的結(jié)構(gòu)性越強(qiáng).

4.3 結(jié)果與分析

4.3.1 元路徑選擇與權(quán)重確定

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

表2 元路徑權(quán)重分配Table 2 Metapath weight allocation

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

而在LastFM數(shù)據(jù)集中，對(duì)比每條元路徑所對(duì)應(yīng)的Wpk值和θ值可以發(fā)現(xiàn)無明顯變化，這是因?yàn)樵摂?shù)據(jù)集中各類型邊數(shù)差距不是很大，導(dǎo)致邊類型對(duì)元路徑權(quán)重的影響很小.

由實(shí)驗(yàn)中Fk指標(biāo)對(duì)兩個(gè)數(shù)據(jù)集中元路徑權(quán)重的影響可以得出以下結(jié)論：本文提出的邊類型概率指標(biāo)能夠更好的優(yōu)化元路徑權(quán)重，由本文方法得到的元路徑權(quán)重相較與傳統(tǒng)只由路徑數(shù)和路徑長度確定的元路徑權(quán)重更接近對(duì)現(xiàn)實(shí)世界的理解.

4.3.2 節(jié)點(diǎn)排序算法驗(yàn)證

在該部分實(shí)驗(yàn)中，用PageRank算法、LeaderRank算法和本文提出的SAIN算法對(duì)DBLP數(shù)據(jù)集中的會(huì)議/期刊類節(jié)點(diǎn)進(jìn)行排序，取排序結(jié)果前10的節(jié)點(diǎn)，排序結(jié)果如表3所示.為了對(duì)排序算法的結(jié)果進(jìn)行初步評(píng)估，我們?cè)谟?jì)算機(jī)科學(xué)知識(shí)發(fā)現(xiàn)網(wǎng)上(AMine)根據(jù)CCF Level對(duì)DBLP數(shù)據(jù)集中的會(huì)議/期刊進(jìn)行分類，A類會(huì)議的檔次高于B類會(huì)議.發(fā)現(xiàn)3種算法給出的排名靠前的會(huì)議基本為A類會(huì)議，靠后的是B類會(huì)議.但是數(shù)據(jù)集中的CVPR和WWW這兩個(gè)A類會(huì)議并沒有排在前10，而一些B類會(huì)議卻排在了前10.這是因?yàn)榕琶惴ǜ嗫紤]的是網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)(節(jié)點(diǎn)的連邊情況)而忽略了會(huì)議的影響因子，即排序算法更多關(guān)注的是在會(huì)議上所發(fā)表的論文數(shù)目，而并非是論文被引數(shù)所占論文的比例.

表3 DBLP數(shù)據(jù)集會(huì)議/期刊類節(jié)點(diǎn)排序Table 3 DBLP data set meeting/journal node sorting

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

圖3 SAIN與LeaderRank、PageRank算法對(duì)比驗(yàn)證Fig.3 Comparison and verification of SAIN，LeaderRank and PageRank algorithms

4.3.3 社區(qū)發(fā)現(xiàn)準(zhǔn)確性驗(yàn)證

為了驗(yàn)證NELPA算法的準(zhǔn)確性，本文選擇原始SLPA算法以及近幾年效果較好的一些異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法作為對(duì)比算法.表4所示為不同算法在數(shù)據(jù)集DBLP和LastFM上得到的社區(qū)聚類效果，用EQ進(jìn)行評(píng)價(jià).

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

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

由表4可知，本文提出的NELPA算法的EQ值高于其它算法.這是因?yàn)镹ELPA算法不僅在標(biāo)簽傳播算法中通過融合多條具有不同權(quán)重的元路徑來體現(xiàn)網(wǎng)絡(luò)的異質(zhì)性，而且以節(jié)點(diǎn)相似性和標(biāo)簽數(shù)同時(shí)作為標(biāo)簽傳播的依據(jù)提升了算法的準(zhǔn)確性.因此，本文提出的NELPA算法對(duì)不同類型的異質(zhì)網(wǎng)絡(luò)具有良好的表征學(xué)習(xí)能力，可有效的提高異質(zhì)網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)的模塊度，得到的社區(qū)聚類效果更好.

5 總結(jié)與展望

本文研究了異質(zhì)信息網(wǎng)絡(luò)中的重疊社區(qū)發(fā)現(xiàn)問題，提出了一種基于網(wǎng)絡(luò)嵌入的標(biāo)簽傳播算法NELPA.首先，考慮了不同的元路徑的權(quán)重，通過構(gòu)建網(wǎng)絡(luò)嵌入模型學(xué)習(xí)并完成了單條元路徑下節(jié)點(diǎn)相似性度量并進(jìn)行了多路徑加權(quán)融合，提升了節(jié)點(diǎn)相似性準(zhǔn)確度，并用該相似性來指導(dǎo)標(biāo)簽傳播過程.其次，提出一種新的節(jié)點(diǎn)排序方法SAIN，并用于節(jié)點(diǎn)更新順序策略，加速了標(biāo)簽傳播速率且提高了傳播的穩(wěn)定性，提升了社區(qū)發(fā)現(xiàn)的準(zhǔn)確性.實(shí)驗(yàn)結(jié)果表明，本算法對(duì)不同的網(wǎng)絡(luò)具有良好的表征學(xué)習(xí)能力，可有效的應(yīng)用于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)領(lǐng)域.但是，NELPA只是基于靜態(tài)網(wǎng)絡(luò)的，現(xiàn)實(shí)中的網(wǎng)絡(luò)是動(dòng)態(tài)變化的，所以，未來可以進(jìn)一步考慮時(shí)間因素，用于動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn).