宋振寰,胡 軍

(1.重慶郵電大學 計算智能重慶市重點實驗室 重慶 400065;2.重慶郵電大學 計算機科學與技術學院 重慶 400065)

0 引 言

網(wǎng)絡在現(xiàn)實生活中無處不在,常見的如生物蛋白質(zhì)系統(tǒng)、社交系統(tǒng)、交通系統(tǒng)等都可以抽象為網(wǎng)絡的形式。通過分析這些網(wǎng)絡結(jié)構(gòu),可從中提取有價值的信息,比如用戶間的好友關系,蛋白質(zhì)網(wǎng)絡中單獨蛋白的相互作用關系等[1]。傳統(tǒng)的網(wǎng)絡表示方法?；诰W(wǎng)絡的拓撲結(jié)構(gòu),通過圖的鄰接矩陣或相似矩陣進行表示,但是這些表示方法在面對大規(guī)模網(wǎng)絡時存在高維稀疏的問題,且可能包含噪聲和冗余信息[2]。針對這一問題,近年來學者們提出了網(wǎng)絡嵌入方法,其通過將原始網(wǎng)絡映射到向量空間得到節(jié)點嵌入表示,從而有利于結(jié)合機器學習模型高效處理網(wǎng)絡分析的下游任務,如節(jié)點分類[3-4],推薦[5-6],鏈接預測[7-9]等。現(xiàn)有的網(wǎng)絡嵌入方法主要分為基于隨機游走的方法[10-12]、基于深度神經(jīng)網(wǎng)絡的方法[13]和基于矩陣分解的方法[14-15]。這些方法大多僅考慮了節(jié)點的局部結(jié)構(gòu)信息,忽略了網(wǎng)絡中的社區(qū)信息。

為解決網(wǎng)絡嵌入中社區(qū)信息缺失的問題,S.Cavallari等[16]基于高斯混合分布提出了融合社區(qū)信息(community embedding,ComE)的算法。M.M.Keikha等[17]對隨機游走進行擴展,提出了融合社區(qū)信息的隨機游走(community aware random walk for embedding,CARE)算法,主要依據(jù)閾值選擇社區(qū)節(jié)點進行游走。B.Rozemberczki等[18]提出了一種在學習節(jié)點嵌入的同時進行節(jié)點聚類(graph embedding with self clustering,GEMSEC)算法,主要通過在學習節(jié)點嵌入過程中考慮節(jié)點聚類損失融合社區(qū)信息。Zhou等[19]提出一種考慮社區(qū)節(jié)點游走的同時結(jié)合注意力機制增強語義信息的(community aware and relational attention,CARA)算法。然而這些融合社區(qū)信息的方法僅對社區(qū)內(nèi)的節(jié)點信息進行了加強,沒有考慮網(wǎng)絡中的社區(qū)間信息。

在現(xiàn)實生活中,社區(qū)信息和社區(qū)間的關系都至關重要,因為不僅同一社區(qū)的節(jié)點有大概率產(chǎn)生聯(lián)系,不同社區(qū)的成員也可能產(chǎn)生聯(lián)系,如圖1所示。在實驗室社交網(wǎng)絡中,每個節(jié)點代表一個學生或老師,每條邊表示相連的2個節(jié)點間存在聯(lián)系,不同顏色代表不同的實驗室社區(qū)。其中,學生x和y在社交網(wǎng)絡中雖然沒有連邊,但由于它們屬于同一實驗室社區(qū),它們之間大概率會存在連邊關系[20]。而A,B兩實驗室社區(qū)因為存在多個共有的老師作為團隊指導,則x節(jié)點有更大的概率和z節(jié)點存在鏈接。因此,融合社區(qū)信息的過程中有必要考慮社區(qū)間的關系,在保留節(jié)點間的連接信息和社區(qū)信息的同時,保留社區(qū)間的連接信息。

圖1 社區(qū)之間關系Fig.1 Relationship between communities

基于上述分析,本文提出一種融合社區(qū)連接信息的網(wǎng)絡嵌入方法(network embedding based on community connection information,ECCI)。該方法首先結(jié)合社區(qū)發(fā)現(xiàn)算法獲得網(wǎng)絡的社區(qū)結(jié)構(gòu),然后基于不同社區(qū)的親密度,捕捉網(wǎng)絡中社區(qū)間關系,接著采用有偏游走的方式保留網(wǎng)絡局部信息,并采用社區(qū)游走的方式保留網(wǎng)絡社區(qū)內(nèi)信息和社區(qū)間信息,最后通過負采樣優(yōu)化的Skip-Gram模型得到與之對應的網(wǎng)絡表示結(jié)果。在3個公開數(shù)據(jù)集上的實驗結(jié)果表明,該方法相比基準方法在鏈接預測實驗的效果有一定程度的提升。

1 相關工作

網(wǎng)絡嵌入旨在提取網(wǎng)絡中節(jié)點、邊的低維信息表示。一個網(wǎng)絡可以表示為一個圖G=(V,E),其中,V表示圖中的節(jié)點集合,E是邊的集合,網(wǎng)絡嵌入的目標是通過一個映射函數(shù)為每個節(jié)點v學習低維稠密的實數(shù)向量f：V→Rd,d是嵌入向量的維數(shù),并在低維空間中保存網(wǎng)絡的拓撲結(jié)構(gòu)信息,如點和邊的鄰近關系,以及社區(qū)信息等。

近年來興起的網(wǎng)絡嵌入研究起源于自然語言處理領域的表示學習,受詞向量嵌入方法的啟發(fā),DeepWalk[10]方法提出,其基于隨機游走的策略,每個節(jié)點隨機從鄰居集合中選擇一個節(jié)點加入節(jié)點序列,對該序列使用Skip-Gram模型進行學習,得到嵌入結(jié)果。Node2vec[11]在隨機游走的過程中加入了超參數(shù)p,q改變游走概率,可選擇深度優(yōu)先遍歷或廣度優(yōu)先遍歷,從而保存網(wǎng)絡的同質(zhì)性和同構(gòu)性。大規(guī)模信息網(wǎng)絡嵌入方法(large-scale information network embedding,LINE)[12]則是利用豐富的二階鄰域來彌補一階鄰居的稀疏性。并且,隨著深度學習的發(fā)展,深層神經(jīng)網(wǎng)絡模型也逐步應用于網(wǎng)絡嵌入技術中,主要用于提取網(wǎng)絡中的非線性信息。基于深層神經(jīng)網(wǎng)絡模型的嵌入方法(structural deep network embedding,SDNE)[13]基于深層神經(jīng)網(wǎng)絡模型,使用深度自動編碼器來保持節(jié)點的一階鄰居相似度和二階鄰居相似度,然后聯(lián)合優(yōu)化這兩個近似值,再通過非線性的函數(shù)獲得節(jié)點的表示。此外,基于矩陣分解的網(wǎng)絡嵌入方法(graph representations,GraRep)[14],其通過對節(jié)點不同k步距離內(nèi)的網(wǎng)絡拓撲信息進行奇異值分解,并將每一步的結(jié)果相連得到節(jié)點嵌入結(jié)果。ProNE[15]首先通過將任務定義為稀疏矩陣分解有效地初始化網(wǎng)絡嵌入,然后通過在頻譜調(diào)制空間中傳播來增強嵌入。但是這些方法都沒有考慮網(wǎng)絡中的社區(qū)信息。

為在網(wǎng)絡嵌入中融合社區(qū)信息,ComE定義了節(jié)點嵌入、社區(qū)檢測、社區(qū)嵌入的方法流程。但是其假設嵌入空間中社區(qū)是擬合高斯分布的,并通過高斯混合模型進行建模。CARE使用Louvain[21]算法檢測出社區(qū)網(wǎng)絡結(jié)構(gòu),利用社區(qū)信息指導隨機游走,在生成節(jié)點序列時,根據(jù)閾值α從社區(qū)中隨機選擇一個節(jié)點加入序列,進而融合社區(qū)信息到最后的嵌入結(jié)果中。GEMSEC通過在學習節(jié)點嵌入的過程中添加節(jié)點到聚類中心的聚類損失以融合網(wǎng)絡中的社區(qū)信息。CARA在獲取節(jié)點周圍的局部結(jié)構(gòu)時還捕捉了節(jié)點的社區(qū)信息,并且通過注意力機制對節(jié)點之間的語義信息進行了加強。M-NMF[22]通過模塊化非負矩陣分解來保存網(wǎng)絡的微觀和宏觀結(jié)構(gòu),從而在最終的節(jié)點嵌入結(jié)果保留社區(qū)信息。融合k步社區(qū)的網(wǎng)絡嵌入方法(network embedding guided by partial community,PCGNE[23]定義了k步社區(qū)的概念,通過部分社區(qū)結(jié)構(gòu)對隨機游走進行指導,以保存更高質(zhì)量的社區(qū)信息。

從上述方法來看,現(xiàn)有的嵌入方法多僅采用不同的方式在嵌入結(jié)果中融合社區(qū)信息,但只強調(diào)了社區(qū)內(nèi)節(jié)點的關系,忽略了社區(qū)間的信息。為此,研究一種融合網(wǎng)絡社區(qū)間信息的網(wǎng)絡嵌入方法具有十分重要的意義。

2 融合社區(qū)連接信息的網(wǎng)絡嵌入

融合社區(qū)連接信息的網(wǎng)絡嵌入方法ECCI主要思想：首先對輸入的網(wǎng)絡使用Louvain算法進行社區(qū)發(fā)現(xiàn),得到輸入網(wǎng)絡的所有社區(qū);然后根據(jù)發(fā)現(xiàn)的社區(qū)得到社區(qū)間的親密度(community relevance jaccard,CR-JC)[24],并結(jié)合CR-JC對網(wǎng)絡中的每一個節(jié)點V生成融合局部結(jié)構(gòu)、社區(qū)信息和社區(qū)間信息的節(jié)點序列捕捉網(wǎng)絡的局部信息和全局信息;最后使用Skip-Gram模型最大化節(jié)點在定義的窗口中出現(xiàn)的條件概率,從節(jié)點序列中學習出節(jié)點的嵌入結(jié)果,方法的主要思想如圖2所示。

圖2 融合社區(qū)連接信息網(wǎng)絡嵌入Fig.2 Network embedding based on community connection information

2.1 社區(qū)生成

由于Louvain算法可快速有效地發(fā)現(xiàn)網(wǎng)絡中的社區(qū)結(jié)構(gòu),因此本文使用該算法來生成社區(qū)信息。該算法首先將每一個節(jié)點單獨劃分為一個社區(qū),然后嘗試把每個節(jié)點分配到鄰居節(jié)點所在的社區(qū)并計算模塊度的變化,最后選擇模塊度最大的社區(qū)進行加入。模塊度計算公式為[25]

(1)

(1)式中：m表示圖中邊的權重之和;ki表示所有與節(jié)點i相連的邊的權重之和;ci表示節(jié)點i所屬的社區(qū);δ是一個增量函數(shù),當社區(qū)相等時返回1。

模塊度優(yōu)化完成后,該算法另一階段是聚集已發(fā)現(xiàn)的社區(qū),建立一個新的社區(qū)網(wǎng)絡。然后不斷重復上述過程,直至模塊度不再增加。

2.2 有偏游走序列生成

本文采用Node2vec獲取節(jié)點鄰居結(jié)構(gòu),具體步驟如算法1所示,該方法對初始節(jié)點v,通過有偏游走的方式生成長度為l的游走序列,以更好地保留網(wǎng)絡中的結(jié)構(gòu)信息。具體地,通過控制p,q兩個超參數(shù)可以實現(xiàn)深度優(yōu)先遍歷和廣度優(yōu)先遍歷,其中p用于控制是否重復游走,即是否返回已經(jīng)走過的節(jié)點。q用于控制游走的方向,是傾向深度優(yōu)先遍歷還是廣度優(yōu)先遍歷。

算法1Node2vec有偏游走

輸入：網(wǎng)絡G(V,E);參數(shù)p,q;節(jié)點游走的路徑長度l;節(jié)點的游走路徑數(shù)量u;

輸出：有偏游走序列Sn。

1：有偏游走序列Sn←?,網(wǎng)絡節(jié)點V←G.nodes()

2：通過p,q值計算每個節(jié)點的別名采樣概率α

3：for iter=1 toudo

4：for eachv∈Vdo

5：Initialize walk_list to [v]

6：for walk_iter=1 toldo

7：curr_v=walk_list[-1]//從最新加入的節(jié)點出發(fā)

8：next_v=AliasSample(curr_v,α)//通過別名采樣獲取下一節(jié)點

9：append next_vto walk_list//加入節(jié)點到游走序列中,作為下一個初始節(jié)點

10：end for

11：Sn=Sn∪walk_list//所有游走序列

12：end for

13：end for

14：Return Sn

2.3 社區(qū)游走序列生成

本文使用CR-JC相似度作為2個社區(qū)之間親密度的關系度量,其物理意義是不同社區(qū)以及其鄰居節(jié)點中產(chǎn)生交集的部分越多,則2個社區(qū)之間的聯(lián)系越緊密,定義為

CR(ci,cj)CR-JC=

(2)

(2)式中：Γ(ci)表示社區(qū)ci的鄰居節(jié)點集合;V(ci)表示社區(qū)ci中的節(jié)點集合。

社區(qū)親密度計算示意圖如圖3所示。給定一個無向無權圖G(V,E),其中,Γ(c1)={7,8,11,12,13,14},V(c1)={1,2,3,4,5,6},Γ(c2)={2,3,4,5,13,14},V(c2)={7,8,9,10,11,12},由公式(2)可得社區(qū)1和社區(qū)2之間的CR-JC親密度為5/7。同理可得,社區(qū)1和社區(qū)3之間CR-JC親密度為3/7,社區(qū)2和社區(qū)3之間親密度為3/7。

圖3 社區(qū)親密度計算示意圖Fig.3 Community Intimacy Calculation

社區(qū)游走序列生成步驟如算法2第4-10行所示,首先以v為初始節(jié)點,根據(jù)發(fā)現(xiàn)的社區(qū)信息確定當前節(jié)點的所屬社區(qū)。接著,將社區(qū)抽象為節(jié)點,計算CR-JC親密度作為網(wǎng)絡中社區(qū)節(jié)點之間的跳躍概率,結(jié)合別名采樣法確定下一跳社區(qū),并從下一跳社區(qū)中隨機選擇節(jié)點加入游走序列,直至游走序列長度達到l。特別地,ci=cj的時候CR-JC值為1,因此初始節(jié)點選擇同一社區(qū)的節(jié)點進行游走的概率更高,其次才是其他相似度高的社區(qū)中的節(jié)點?？梢钥闯?社區(qū)游走序列中既保存了網(wǎng)絡中節(jié)點的社區(qū)內(nèi)信息,也基于社區(qū)相似度捕捉了網(wǎng)絡中社區(qū)間的關系,彌補了有偏游走序列中全局信息的缺失,可更好地對網(wǎng)絡結(jié)構(gòu)進行表示。

算法2社區(qū)游走

輸入：網(wǎng)絡G(V,E);社區(qū)信息com;社區(qū)游走路徑數(shù)量c;社區(qū)游走的路徑長度l;

輸出：社區(qū)游走序列Sc。

1：社區(qū)游走序列Sc←?,網(wǎng)絡中節(jié)點V←G.nodes()

2：通過CR-JC計算每個社區(qū)的別名采樣概率α

3：for iter=1 tocdo

4：for eachv∈Vdo

5：Initialize walk_list to [v]//將節(jié)點V作為初始節(jié)點

6：for walk_iter=1 toldo

7：curr_v=walk_list[-1]

8：curr_com=com(curr_v)//當前節(jié)點所屬社區(qū)

9：next_com=AliasSample(curr_com,α)//別名采樣法獲取下一跳社區(qū)

10：next_v=RandomChoice(next_com)

11：append next_vto walk_list

12：end for

13：Sc=Sc∪walk_list

14：end for

15：end for

16：Return Sc

2.4 SkipGram模型

SkipGram模型如圖4所示,對每個節(jié)點得到有偏游走和社區(qū)游走的序列l(wèi)={v1,v2,…vn}后,ECCI使用Skip-Gram模型來學習網(wǎng)絡的節(jié)點嵌入。具體地,從得到的序列中任選一個節(jié)點vi,根據(jù)窗口大小w獲得vi的上下文節(jié)點,將節(jié)點的獨熱編碼輸入神經(jīng)網(wǎng)絡模型,通過正向運算和反向傳播更新權重矩陣,最大化序列vi-w,…,vi,…,vi+w中節(jié)點共現(xiàn)的概率為

圖4 SkipGram模型Fig.4 SkipGram model

(3)

為降低(3)式的計算復雜度,這里采用負采樣進行優(yōu)化,表達式為

(4)

(4)式中：K為負采樣個數(shù);X(v)為負采樣概率分布。

3 實驗分析

對于本文提出的網(wǎng)絡嵌入方法,將得到的表示向量運用于鏈接預測任務以驗證其有效性,并通過參數(shù)敏感性實驗進行參數(shù)分析。

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

實驗選用了3個真實數(shù)據(jù)集來進行測試,數(shù)據(jù)集的具體信息如表1所示。

表1 數(shù)據(jù)集Tab.1 Dataset

Cora[26]：每個節(jié)點代表1篇機器學習論文,一共可分為7個類別。網(wǎng)絡中存在2 708個節(jié)點以及5 429個鏈接。

Facebook[27]：每個節(jié)點代表1個用戶,每1條邊則代表2個用戶之間的友情。該網(wǎng)絡一共存在4 039個節(jié)點和88 234條邊。

表2 鏈接預測結(jié)果Tab.2 Link prediction results

Wiki[28]：每個節(jié)點代表維基百科中的文章,每條邊的連接表示2篇文章之間的引用,該網(wǎng)絡一共存在2 405個節(jié)點以及17 981條邊,共17個種類。

3.2 對比方法和評價指標

實驗對比的方法包括以下5種網(wǎng)絡嵌入方法。

1)DeepWalk：利用隨機游走生成節(jié)點序列獲得局部信息,并通過Skip-Gram模型學習節(jié)點的表示。

2)Node2vec：1種在隨機游走過程中通過2個超參數(shù)p,q考慮深度優(yōu)先搜索和廣度優(yōu)先搜索的網(wǎng)絡嵌入表示方法。

3)ComE：采用混合高斯分布作為社區(qū)表示的模型,并假設節(jié)點表示是由這樣的社區(qū)分布生成的。

4)CARE：1種基于已知社區(qū)進行隨機游走的網(wǎng)絡嵌入方法,能在嵌入結(jié)果中考慮網(wǎng)絡中的社區(qū)信息。

5)LouvainNE[29]：1種基于層次聚類的網(wǎng)絡嵌入方法,能在嵌入結(jié)果中考慮不同層級的社區(qū)信息。

其中,ComE、CARE和LouvainNE是融合了社區(qū)信息的方法,DeepWalk和Node2vec是沒有融合社區(qū)信息的方法。

實驗使用的評價指標有AUC(Area Under Curve,ROC曲線下面積)和F1-Score值,其中F1-Score計算方式為

(5)

(6)

(7)

(5)—(7)式中：TP、FN、FP分別為預測結(jié)果中真陽性、假陰性和假陽性樣本;precision為真陽樣本和預測為陽的樣本占比;recall為真陽樣本和真實為陽的樣本占比。

3.3 實驗設置

所有方法在游走的過程中進行統(tǒng)一的參數(shù)設置。具體地,設置滑動窗口大小為5,嵌入維度為128,游走路徑數(shù)量為10,游走長度為80。對比方法的參數(shù)均按照相應論文中描述進行設置。特別地,本文提出的方法負采樣個數(shù)為5,ComE的聚類數(shù)根據(jù)網(wǎng)絡中的真實類別數(shù)進行設置,無類別信息的Facebook數(shù)據(jù)集則使用社區(qū)發(fā)現(xiàn)算法發(fā)現(xiàn)的社區(qū)個數(shù)作為聚類數(shù)。LouvainNE方法a值設置為0.01。

網(wǎng)絡嵌入方法僅僅為每個節(jié)點生成嵌入向量,因此本文參照Node2vec使用多種操作運算符計算邊的嵌入g(u,v),具體定義如下

Hadamard：

[f(u)*f(v)]i=fi(u)*fi(v)

(8)

Average：

(9)

Weighted-L1：

‖f(u)·f(v)‖1i=|f(u)i-f(v)i|

(10)

Weighted-L2：

‖f(u)·f(v)‖2i=|f(u)i-f(v)i|2

(11)

3.4 鏈接預測分析

3.4.1 全局鏈接預測

在全局鏈接預測任務中,首先將網(wǎng)絡中的一些邊隨機刪除,然后通過各種方法預測這些缺失的邊。具體實驗采用了生成帶標簽的數(shù)據(jù)集方式,在不影響網(wǎng)絡連通性的情況下從網(wǎng)絡存在的邊中隨機移除10%、20%、30%、40%、50%的邊作為正樣本,從節(jié)點間無連接的節(jié)點對當中采集負樣本,最后利用剩余的網(wǎng)絡進行網(wǎng)絡嵌入得到嵌入結(jié)果。AUC和F1-Score指標用于評估該任務的準確性,取5次實驗的平均值作為最終結(jié)果,更高的AUC值和F1-Score值意味著更好的模型性能。

3個數(shù)據(jù)集上Hadamard運算符實驗結(jié)果AUC(百分制)如表2所示。

從實驗結(jié)果可以看出,本文提出的方法ECCI在大多數(shù)情況下比只考慮局部結(jié)構(gòu)信息的方法在AUC有較大提升,且對于只考慮社區(qū)信息的方法也有一定的提升。具體地,在Facebook和Wiki數(shù)據(jù)集中優(yōu)于所有方法,并且在Cora數(shù)據(jù)集上比僅考慮局部結(jié)構(gòu)信息的方法(DeepWalk、Node2vec)的效果提升了4%～7%,與融合社區(qū)信息的方法(ComE、CARE、LouvainNE)相比效果有一定優(yōu)勢,但在邊刪除過多時,社區(qū)劃分不準確對實驗結(jié)果有一定影響。對于F1-Score,ECCI在絕大部分情況下都優(yōu)于其他對比方法,具有良好的模型性能。

另外,實驗將各個方法通過不同運算符得到的邊嵌入運用在Facebook數(shù)據(jù)集的鏈接預測實驗中,以驗證方法得到的節(jié)點嵌入是否具有適用性。實驗結(jié)果如圖5所示。從圖5可以看出,ECCI在Hadamard、Weighted-l1和Weighted-l2運算符下獲得的邊嵌入向量在鏈接預測實驗中效果較好,其中,Hadamard運算符的效果優(yōu)于其他所有方法,說明ECCI獲得的節(jié)點嵌入在大多數(shù)運算符下都具有適用性。

圖5 Facebook數(shù)據(jù)集各運算方法結(jié)果Fig.5 Results of various algorithms in the Facebook dataset

綜上所述,本文提出的方法相對Node2vec和DeepWalk,在嵌入結(jié)果中保留了社區(qū)信息和社區(qū)間信息,同時與融合了社區(qū)信息的方法ComE、CARE以及LouvainNE相比,在嵌入結(jié)果中保留了網(wǎng)絡中的社區(qū)間信息,從而預測性能有一定的優(yōu)勢。

3.4.2 社區(qū)間的鏈接預測

實驗在社區(qū)間鏈接預測中選擇網(wǎng)絡10%的邊進行刪除,原因在于刪除過多的邊會使網(wǎng)絡結(jié)構(gòu)發(fā)生巨大變化,導致社區(qū)發(fā)現(xiàn)效果不佳。具體地,隨機遍歷網(wǎng)絡中的邊,通過判斷邊的社區(qū)屬性以及刪除后網(wǎng)絡的連通性進行篩選,使得刪除的邊中社區(qū)內(nèi)的邊(邊的兩端節(jié)點屬于同一社區(qū))分別占總刪除邊數(shù)的10%～90%,從而判斷嵌入方法是否對網(wǎng)絡社區(qū)間的關系進行保留。

在3個數(shù)據(jù)集上進行實驗,實驗結(jié)果AUC和F1-Score(百分制)如表3—5所示。

表3 Cora數(shù)據(jù)集上社區(qū)間鏈接預測結(jié)果Tab.3 Intercommunity link prediction results on Cora datasets

表5 Wiki數(shù)據(jù)集上社區(qū)間鏈接預測結(jié)果Tab.5 Intercommunity link prediction results on Wiki datasets

從實驗結(jié)果可以看出,本文提出的方法在社區(qū)間邊多的情況下AUC和F1-Score相比其他對比方法有一定的提升。產(chǎn)生以上實驗效果的原因主要是DeepWalk和Node2vec隨機生成游走序列,沒有融合社區(qū)信息。雖然Node2vec考慮了深度優(yōu)先搜索和廣度優(yōu)先搜索,但是p,q參數(shù)并不能提取網(wǎng)絡中的社區(qū)信息。ComE和CARE雖然都考慮了社區(qū)信息,但它們更關注于社區(qū)內(nèi)部的信息提取,而忽略了社區(qū)之間的信息保留。LouvainNE方法雖然考慮了不同層次的社區(qū)信息,但是一些社區(qū)可能聯(lián)系不大但也被歸屬到同一層級進行強化,從而導致錯誤判別節(jié)點間是否存在鏈接。本文提出的方法在游走序列中加入了融合社區(qū)信息和社區(qū)間信息的社區(qū)游走,且由超參數(shù)c控制迭代次數(shù),社區(qū)間親密關系控制社區(qū)游走概率。

只考慮社區(qū)信息的方法ComE在部分結(jié)果中依然表現(xiàn)出良好性能的原因在于,它在形成嵌入信息的過程中形成了一個閉環(huán),不斷地優(yōu)化節(jié)點嵌入信息和社區(qū)嵌入信息,對它們進行一個平衡,因此彌補了只考慮社區(qū)信息的不足,但是本文提出的方法從社區(qū)間關系的角度對只考慮社區(qū)信息的方法進行優(yōu)化,提升了鏈接預測實驗的AUC分數(shù)。同時,通過各方法在不同數(shù)據(jù)集上的F1-Score對比,可以發(fā)現(xiàn)ECCI在大多數(shù)情況下都優(yōu)于其他對比方法,在社區(qū)內(nèi)的邊少且社區(qū)間的邊多的情況下,ECCI相比其他方法有著更好的性能,并且,隨著社區(qū)內(nèi)的邊不斷增加,ECCI的效果與基準方法相比也有一定優(yōu)勢。這說明ECCI在保留網(wǎng)絡中的社區(qū)信息時考慮比其余方法更加充分,同時保留了社區(qū)內(nèi)信息和社區(qū)間信息。

3.5 參數(shù)敏感性分析

為了評估ECCI中不同的參數(shù)值是如何影響不同數(shù)據(jù)集上的結(jié)果,實驗在刪除10%邊的情況下的鏈接預測任務上進行,實驗結(jié)果如圖6所示。

圖6 參數(shù)敏感性實驗結(jié)果示意圖Fig.6 Schematic diagram of parameter sensitivity experimental results

從實驗結(jié)果可以發(fā)現(xiàn),在Cora數(shù)據(jù)集中,隨著c值的改變,實驗結(jié)果的精度有先上升再下降的趨勢,在c=2時獲得最好的結(jié)果,Facebook數(shù)據(jù)集中,最好的結(jié)果在c=1時得到,且隨著c值的增加鏈接預測的效果呈下降趨勢,而wiki數(shù)據(jù)集的表現(xiàn)與Cora數(shù)據(jù)集類似,在c=2的情況下效果最佳。產(chǎn)生上述實驗結(jié)果的原因可能在于,Facebook數(shù)據(jù)集中每個社區(qū)平均5 300條邊,此時對社區(qū)中的節(jié)點進行游走有很大概率無法走出社區(qū),即節(jié)點游走在刻畫網(wǎng)絡結(jié)構(gòu)的過程中已保留了部分社區(qū)信息。而c作為社區(qū)游走的迭代次數(shù),每次迭代都可強化網(wǎng)絡社區(qū)信息及社區(qū)間關系,但迭代次數(shù)過多可能會導致同一社區(qū)的節(jié)點嵌入趨于一致,從而將原本沒有邊連接的節(jié)點預測為有邊相連,所以在Facebook數(shù)據(jù)集一次迭代效果最佳。對于Cora和Wiki數(shù)據(jù)集,它們社區(qū)中平均連邊分別為151條和498條。節(jié)點游走出社區(qū)對網(wǎng)絡結(jié)構(gòu)進行刻畫的概率更大,從而導致社區(qū)信息保留較少,故可增大c值強化社區(qū)信息。總的來說,在大規(guī)模稠密網(wǎng)絡(網(wǎng)絡中邊集遠大于點集,社區(qū)中邊集遠大于游走序列長度)中,c值設置偏小,稀疏網(wǎng)絡(網(wǎng)絡中邊集與點集相差不大,社區(qū)中邊集不多)中c值可適當增大。

然后實驗分析了網(wǎng)絡表示結(jié)果的嵌入維度和游走路徑數(shù)量對鏈接預測結(jié)果的影響。在Cora和Wiki數(shù)據(jù)集中,隨著dimensions的改變,實驗結(jié)果有先上升后下降的趨勢,在dimensions=64時獲得最好的結(jié)果。Facebook數(shù)據(jù)集則是在dimensions=128時獲得最好的結(jié)果。產(chǎn)生上述實驗結(jié)果的原因可能是不同的數(shù)據(jù)集適合的嵌入維度各不相同但是過低或者過高的維度會導致模型欠擬合或過擬合。此外,通過實驗分析可以發(fā)現(xiàn),對于稠密數(shù)據(jù)集Facebook,實驗效果隨著numwalks的增加而增加,在達到一定規(guī)模后產(chǎn)生輕微波動,原因可能在于該數(shù)據(jù)集規(guī)模較大,因此需要多次游走才能更好地學習網(wǎng)絡的結(jié)構(gòu),而對于Cora和Wiki數(shù)據(jù)集,由于網(wǎng)絡規(guī)模較小,不需要多次numwalks就可以完成網(wǎng)絡結(jié)構(gòu)的學習,實驗效果隨著numwalks的改變產(chǎn)生輕微波動,但過多的游走次數(shù)會產(chǎn)生一定噪聲使實驗效果降低。

最后,從滑動窗口的實驗結(jié)果可以看出,網(wǎng)絡中的一階鄰居和二階鄰居的重要性通常大于高階鄰居的重要性,但是在Cora這類有明顯節(jié)點標簽信息的網(wǎng)絡中高階信息對嵌入結(jié)果有一定提升。

4 結(jié)束語

為融合社區(qū)信息和社區(qū)間信息更好地對網(wǎng)絡進行嵌入表示,本文提出了一種融合社區(qū)連接信息的網(wǎng)絡嵌入方法。該方法通過Louvain算法得到網(wǎng)絡中的社區(qū)劃分,然后通過不同社區(qū)之間的親密關系,對節(jié)點生成融合局部結(jié)構(gòu)、社區(qū)信息和社區(qū)間信息的特定節(jié)點序列作為上下文信息,以捕捉網(wǎng)絡中的局部拓撲信息和全局信息,該方法豐富了嵌入結(jié)果的社區(qū)信息和社區(qū)間信息。在3個真實數(shù)據(jù)集的實驗結(jié)果驗證了模型的有效性和優(yōu)越性,在全局鏈接預測以及社區(qū)間的鏈接預測任務中AUC和F1-Score相比基準方法都有一定提升。

本文中所提出的算法主要基于網(wǎng)絡的拓撲結(jié)構(gòu),無法處理網(wǎng)絡中的其他輔助信息,因此得到的網(wǎng)絡嵌入不適用于網(wǎng)絡中的邊或點含有多種屬性的復雜網(wǎng)絡,未來將考慮融合各種輔助信息的網(wǎng)絡嵌入方法。