基于Motif 聚集系數與時序劃分的高階鏈接預測方法?

康駐關,金福生,王國仁

(北京理工大學 計算機學院,北京 100081)

網絡中的鏈接預測[1]指通過已知的網絡結構信息,預測網絡中尚未產生鏈接的節點間產生新鏈接的可能性.如果給定網絡的當前狀態,則鏈接預測將重點放在評估未來狀態中存在邊的可能性.可以理解為預測社交網絡中兩個人未來相互認識,計算機網絡中的通信或生物網絡中的生物分子相互作用的可能性.一個好的鏈接預測算法不僅可以用來挖掘網絡中節點與結構間的關系,而且可以進一步幫助研究者探索網絡結構的演化規律.目前,鏈接預測不僅在理論研究上取得了較好的成果,而且在一些特定的場景下也具有廣泛的應用價值,例如預測社交網絡中的友誼發現、推斷基因與疾病之間的新關系、發現學術界的合作關系等[2,3,4]具體應用.常見的鏈接預測算法一次只需要預測一條邊,然而在分析復雜網絡結構演化時往往需要考慮所有的邊,這些算法則不能進行很好的擴展.本文提出的高階鏈接預測任務將探測更大的特征集,這也要求算法能夠捕獲數據集中更多潛在的可表示性特征.原則上,好的鏈接預測模型可以適用于網絡中任意結構的預測,具體表示為預測網絡中任意高階的交互.毋庸置疑,鏈接預測是復雜的網絡分析中一個有重要實用價值的研究問題,在交互事件發生之前對其進行預測,是深入探索網絡結構演化的一項重要能力.

目前,絕大多數的鏈接預測算法都是基于網絡低階結構的研究[1,5],這些方法通常只分析了網絡中成對節點間的關系,無法有效捕獲高階結構中的潛在聯系,從而在高階結構中的預測效果表現較差.本文使用網絡高階結構來進行鏈接預測,充分挖掘網絡中高階結構的演變信息,從而獲得對復雜網絡結構的新見解.為了簡化研究和便捷可表示性,本文重點以高階結構中的基礎結構(無向三角形結構)為主要的研究對象.

為了解決上述提出的高階特征表示問題,本文從高階網絡結構特性和網絡結構演化兩個維度進行深入分析,提出了計算高階結構聚集性特征和網絡結構演變特征的兩個方法:首先,通過對高階結構的聚集行為研究,將其進行量化用來表示高階結構的聚集程度,從而有效捕獲高階結構的聚集性特征;其次,通過將數據集進行切割分片,分析隨著時間演變網絡結構的變化規律,提出節點間鏈接頻次和鏈接趨勢等具有網絡結構演變特性的特征,有效利用了動態網絡演化的歷史信息.基于上述兩個方法,提出了基于Motif 聚集系數與時序劃分的高階鏈接預測模型用于完成預測任務.

綜上所述,本文主要貢獻總結如下:

(1)通過分析網絡高階結構,提出Motif 聚集系數特征,將傳統對單節點的聚集系數定義擴展到高階結構的聚集系數定義.經過實驗驗證,Motif 聚集系數可以有效捕獲網絡中高階結構的聚類信息,并且驗證了使用Motif 聚集系數表示高階結構聚集程度的有效性;

(2)通過分析網絡結構演變的特性,提出節點間鏈接頻率和鏈接趨勢等表示網絡結構演變的重要特征,可以挖掘網絡結構演變過程中節點之間的鏈接變化規律;

(3)提出了基于Motif 聚集系數與時序劃分的高階鏈接預測模型(high-order link prediction model based on Motif aggregation coefficient and time series division,簡稱MTLP),有效融合傳統鏈接預測提出的相似性度量特征與本文提出的Motif 聚集系數特征和表示網絡結構演變的特征,通過使用多層感知器網絡(multi-layer perceptron,簡稱MLP)算法完成高階鏈接預測任務.

本文在第1 節介紹相關研究工作.第2 節給出本文的問題定義.第3 節重點介紹本文提出的高階鏈接預測模型.第4 節為實驗分析.第5 節總結全文.

1 相關研究

近年來,鏈接預測方法主要應用在社交網絡和其他復雜網絡等領域.針對現有的鏈接預測算法的研究,本文將其預測模型大致分為基于局部結構相似性的鏈接預測方法、基于概率模型的鏈接預測方法和基于機器學習的鏈接預測方法這三大類.

(1)基于局部結構相似性的鏈接預測方法

常見的相似性指標有基于調和平均數、幾何平均數和算術平均數相似性指標[3]、基于共同鄰居(common neighbors,簡稱CN)相似性指標[1,6]、基于Jaccard 相似性指標[1]、基于Adamic/Adar(Adamic-Adar,簡稱AA)相似性指標[1,7]、基于優先鏈接(preferential attachment,簡稱PA)相似性指標[1,6,8]、基于Katz 相似性指標[1,9,10]、基于PageRank 相似性指標[1,11,12]和基于層次化混合特征指標[13]等.基于局部結構相似性的方法主要是用于捕獲局部網絡的特征,從而根據相似性的特征進行鏈接預測.但是這些方法無法有效地捕獲高階結構的特征,僅適用于低階的鏈接預測.如果將其擴展到高階鏈接預測,其預測效果并不理想.

(2)基于概率模型的鏈接預測方法

Clauset 等人[14]最初提出基于最大似然估計的鏈接預測方法,將其應用到有明顯層次的網絡結構中,發現有比較高的精確度;Tian 等人[15]提出了一種基于最大似然估計的鏈接預測模型,將腦網絡的數據建立了層次隨機圖,再結合馬爾可夫算法計算腦網絡邊的鏈接概率,顯示出了良好的預測性能.Das 等人[16]提出一種基于隨機馬爾科夫鏈預測模型,其以時序圖作為社交網絡鏈接預測的基礎.Liu 等人[17]提出一種基于動態博弈的雙向選擇機制來預測未來的網絡拓撲結構.該類方法適合于在靜態網絡下進行預測,但是動態網絡的結構是頻繁變化的網絡,因此該類方法往往難以滿足要求.

(3)基于機器學習的鏈接預測方法

Chiu 等人[18]提出了弱估計器的特征指標,該特征重點考慮了隨著時間推移而發展的網絡中鏈接預測的相關趨勢,并將該指標作為構建深度神經網絡的有效特征向量進行學習.Yaghi 等人[19]通過提取網絡中節點度中心性(DC)和緊密度中心性(CC)兩個特征來增強給定邊的重要性,并使用機器學習模型進行鏈接預測.Abuoda 等人[20]進一步對網絡拓撲結構進行分析,并提出網絡模式(Motif)結構應用于鏈接預測.Chen 等人[21]提出了一種基于圖卷積網絡(GCN)的嵌入式長短期記憶網絡(LSTM),用于端到端動態鏈接預測.該類方法在結構相似性鏈接預測方法的基礎之上進一步獲取網絡特征,使用機器學習模型進行訓練學習完成鏈接預測任務.但是多數的研究僅僅是更改已有的機器學習模型,缺乏對高階網絡結構中存在的特性和網絡結構演變信息進一步的分析,以至于達不到預期的預測效果.

雖然當前的鏈接預測算法有很多,但面對上述各種鏈接預測的研究仍存在不足.一方面,現有的大多數鏈接預測算法只考慮了網絡中很少一部分的局部結構特征,這些算法基本上都是從節點相似性角度進行度量.例如計算共同鄰居、余弦相似性等局部結構特征,這些特征往往僅適用于節點對之間的相似性度量,但是在一些復雜的網絡中,高階結構間的特性遠不止如此.另一方面,現有的鏈接預測算法很少考慮網絡中的時序信息,以及隨著時間推移網絡不斷變化的信息.盡管一些學者嘗試使用長短期記憶網絡(LSTM)解決網絡結構演化過程中的時間依賴性問題,但是無法具體地分析網絡演化規律,缺乏對表示時序信息的特征做出進一步解釋.

本文提出的鏈接預測算法與上述算法不同之處如下.

(1)傳統的鏈接預測算法主要提取網絡低階結構之間的相似性特征,而忽略高階結構中存在的特征;本文通過研究高階結構的特征來獲得對網絡高階結構的新見解.本文提出了Motif 聚集系數的方法,通過計算網絡高階結構的Motif 聚集系數來捕獲高階結構中存在的聚類信息,從而豐富網絡結構的特征;

(2)當前,一些算法使用LSTM 模型解決網絡結構演化過程中的時間依賴性問題,但是無法區分網絡中哪些表示網絡結構演變的特征在預測任務中起到決定性作用,缺乏對網絡結構演化規律的有效分析;本文重點在于分析網絡中存在的可表示性特征,因此本文通過對動態網絡進行分析,發現節點間的鏈接頻率和鏈接趨勢等表示網絡結構演變的重要特征,可以更加細致地解釋網絡結構變化信息.

2 問題定義

本文研究的重點是預測多個節點間產生鏈接形成高階結構,因此我們通過研究三角形結構來確定高階鏈接預測的模式.為了使讀者更容易理解本文的研究內容,本節先介紹幾個相關概念,針對高階鏈接預測任務進行形式化定義.

定義1(單形).單形表示一個包含k個節點的集合,每個單形對應一個時間戳,具體表示為,|Si|=k,我們稱Si為單形,ti為該單形對應的時間戳.

定義2(閉合三角形).如果有3 個節點存在于同一個單形,例如{u,v,w}?Si,則這3 個節點形成一個閉合三角形,具體可表示為組成閉合三角形的3 個節點至少同時出現在一個單形中的情況.

定義3(開放三角形).如果3 個節點中的任意一對節點至少同時出現在一個單形中,但不存在某個單形同時包含這3 個節點,我們稱這3 個節點形成一個開放三角形.

定義4(簡單閉合事件).在t時刻之前,節點間可以任意的產生鏈接,但是沒有任何一個單形同時包含{u,v,w}這3 個節點,如果在t時刻之后存在一個單形同時包含了這3 個節點,則該過程稱為簡單閉合事件.

定義5(高階鏈接預測).為了簡化表示,本文將高階鏈接預測定義為預測節點三元組上的簡單閉合事件.簡單來說,我們研究的高階鏈接預測問題是預測哪些尚未同時出現在同一個單形中的3 個節點將來會同時出現在某一個單形中,具體表示為預測哪些開放三角形在未來會經歷簡單閉合事件.

3 基于Motif 聚集系數與時序劃分的高階鏈接預測模型

為了充分利用并整合動態網絡中高階結構特征與結構演變特征,以提高鏈接預測模型的性能,本文提出一種基于Motif 聚集系數與時序劃分的高階鏈接預測模型(MTLP).本節首先介紹該模型的基本思想,然后分別介紹Motif 聚集系數與網絡結構演變特征的計算方法,最后給出基于多層感知器網絡的鏈接預測算法實現.

3.1 MTLP模型的基本思想

本文通過構建MTLP 模型來完成預測任務,該模型主要由3 部分組成,分別是提取網絡高階結構Motif 聚集系數特征、提取網絡結構演化特征和構建基于MLP 的鏈接預測算法,模型的整體框架如圖1 所示.

Fig.1 MTLP model framework圖1 MTLP 模型框架圖

(1)聚集系數是網絡科學中數據建模的重要統計數據[22,23,24],也是機器學習中非常有用的特征,例如在角色發現[25]和異常檢測[26]中的應用.但是傳統聚集系數本身具有限制條件,因為它僅限于測量一個簡單楔形結構的閉合概率,本質上表示網絡中單個節點的聚集程度,無法表示網絡中高階結構的聚集特性.本文重點研究基于高階結構的鏈接預測任務,而傳統的局部聚集系數并不適用于表示高階結構的聚集行為.因此,將測量單個節點的局部聚集系數擴展至測量高階結構的聚集系數,是提取Motif 聚集系數特征模塊主要解決的問題;

(2)鏈接預測的相關方法,本質上都是利用網絡歷史信息并將其壓縮為一個網絡,以預測下一時刻的網絡.可以說,目前大多數的鏈接預測都是基于網絡快照的方法,例如在給定的時間內分析給定的網絡快照,用于下次鏈接預測.但是這些方法僅考慮了前一時刻的網絡拓撲結構信息,而與前一時刻網絡的動態發展無關.因此,通過對動態網絡進行分析并捕獲網絡結構演變信息,是提取網絡結構演化特征模塊主要解決的問題;

(3)本文研究的問題是預測一個三角形是否會經歷簡單閉合事件,該問題實際上是二分類問題.因此,本文使用MLP 算法來完成鏈接預測任務.

3.2 提取Motif聚集系數特征

聚集系數[22,23,24]是用來量化網絡中節點聚集程度的度量標準.本文擴展了傳統的局部聚集系數,將單個節點的聚集系數擴展為高階結構的聚集系數,用來衡量網絡中高階結構的聚集程度,即Motif 聚集系數.

本文主要研究的是無向圖網絡,定義G=(V,E)表示無向圖,n=|V|表示無向圖中的總節點數,m=|E|表示無向圖中的總邊數,任意節點u的鄰居節點集合為N(u).定義Cmotif(g)為Motif 聚集系數,g表示任意高階結構,Gtotal(g)表示g的全局聚集系數,N(g)表示g中所有節點的共同鄰居節點,|Wi,j|表示節點i與節點j之間是否存在鏈接:如果存在,則|Wi,j|=1;否則|Wi,j|=0.Motif 聚集系數的公式定義如下:

通過上述的定義已經了解到如何計算Motif 聚集系數,計算Motif 聚集系數首先需要計算每個子圖的全局聚集系數,再計算子圖中每個高階結構的共同鄰居,從而得到最終結果.從公式上來看,直接進行計算的代價非常昂貴,因此,我們對算法進行了優化,通過維護一個集合用來存儲每個節點的鄰居節點,使時間復雜度降為o(n),極大地縮短了計算Motif 聚集系數的時間,計算高階結構的Motif 聚集系數算法詳見算法1.

算法1.計算Motif 聚集系數.

Input:高階結構g,鄰居節點集合N;

Output:Cmotif(g)(高階結構g的Motif 聚集系數).

1 算法CalculateMotifCluf(g,N)

2 定義triNum記錄g中閉合三角形的個數,Gtotal(g)記錄全局聚集系數

3 定義tempNum用于臨時計數,定義conns用于記錄共同鄰居中相互鏈接的邊數

4 forg中的任意3 個節點(i,j,k)do

5 if (i,j,k)任意兩個節點間存在鏈接 then

6triNum++

7 end if

8 end for

9 forg中的任意一個節點ido

10tempNum+=

11 end for

13 forN(g)中的任意兩個節點(i,j)do

14 if (i,j)兩個節點間存在鏈接 do

15conns++

16 end if

17 end for

19 returnCmotif(g)

3.3 提取網絡結構演變特征

網絡演化的歷史為理論上的預測提供了更多信息,同時也為網絡分析增加了一個全新的維度.我們采用圖序列來描述網絡的動態變化,并分析隨著時間的推移,節點結構之間關聯性的演變過程.

首先在數據預處理部分,我們將網絡切分成表示一系列圖序列的時間片集合G=(G1,G2,…,Gt?1,Gt),其中,Gt=(Vt,Et)表示第t個時間序列的網絡圖,每個網絡圖對應一個鄰接矩陣Wt.動態網絡的拓撲結構會隨著時間t的變化而不同,主要是隨著時間的變化,節點間的鏈接產生了不同的變化,有的節點間添加新的鏈接,有的節點間刪除原有的鏈接,在不同的時間序列中,節點對之間的鏈接關系也會不同.每個時間片中節點間的鏈接變化如圖2所示,其中,虛線表示圖中節點從G1時刻演變到G2時刻的映射.

Fig.2 Representation of node link changes in different time slices圖2 不同時間片中節點鏈接變化表示

由圖2 可知:網絡中的結構會隨著時間推移產生不同的變化,這些變化會在每個時間片中留下一系列的痕跡.本文主要從簡單閉合事件的生命周期轉換進行分析,通過考慮一系列時間序列的轉換來分析節點間的結構轉換關系是否能夠對未來形成閉合三角形有重要的影響.通過分析發現:在大多數的數據集中,許多新形成的單形由k個節點組成,這些節點出現在同一個單形中之前也分布在不同的單形中,與其他節點產生交互.因此,本文認為,網絡中產生開放三角形的一個可能假設是鏈接創建中的時間異步性.例如,開放三角形中的節點不能同時出現在同一個單形中,這些節點只能在不同時間段進行交互形成鏈接.不管開放三角形是如何創建的,隨著網絡的發展,這3 個相關的節點在未來都可能在同一個單形中同時出現.通過對三角形經歷簡單閉合事件過程分析,每一種結構的變化對未來是否能夠形成閉合三角形有著重要影響.因此,本文將整個結構演變過程進行時間上的劃分,分別統計每個時間片中的局部結構關系,從而在時序維度提取重要的特征信息,主要提取了節點間鏈接頻次和鏈接趨勢兩項特征用來表示網絡結構變化規律.

在網絡演化的進程中,不同節點間的鏈接頻次各有不同.統計鏈接頻次可以表示節點間的動態聯系,因此,本文將鏈接頻次作為動態網絡中的一個重要特征.定義fsn(i,j,k)為n個時間片中三角形的eij,eik,ejk這3 條邊的鏈接頻次算數和,其中,表示第t個時間片中節點i與節點j之間是否存在鏈接:如果存在,;否則,.節點間的鏈接頻次公式定義如下:

網絡結構在演化時呈現不同的鏈接規律,這些規律既具有確定性又具有不確定性,因此,可以將每條邊的鏈接趨勢作為一項重要的鏈接指示特征進行歸納.定義表示第t個時間片與相鄰時間片中三角形邊數的鏈接趨勢,鏈接趨勢減少為?1,鏈接趨勢不變為0,鏈接趨勢增長為1.本文將數據切割成n個時間片,通過計算n個時間片中三角形3 條邊的鏈接趨勢的算數平均值,作為節點間鏈接變化的最終鏈接趨勢,節點間的鏈接趨勢公式定義如下:

節點間的鏈接頻次和鏈接趨勢可以有效地捕捉到動態網絡演化規律,同時,這些特征也可以通過簡單的計算將其表示出來.因此,本文將在后續的鏈接預測模型中使用這些可表示網絡結構演變的特征,從而有效捕獲網絡演變信息.

3.4 構建基于MLP的鏈接預測算法

本節主要介紹構建基于MLP 的鏈接預測算法,用于完成高階鏈接預測任務,算法流程圖如圖3 所示.

Fig.3 Flow chart of constructing MLP-based link prediction algorithm圖3 構建基于MLP 的鏈接預測算法流程圖

3.4.1 構建特征向量

在機器學習領域,只有數據和特征才能決定機器學習的上限,一個優秀的模型和算法只能不斷地逼近這個上限.因此,選擇具有代表性的特征也是一項非常重要的工作.通過前文的分析,本文已經提取出動態網絡中Motif 聚集系數特征和網絡結構演變相關特征.除此之外,我們也加入了一些傳統鏈接預測經常使用的特征,例如節點的鄰居和節點的度等相似性特征,通過融合這些特征構,建成可供機器學習模型訓練的特征向量.特征向量構建算法詳見算法2.

算法2.構建特征向量.

Input:單形Si列表,時間列表ti,切割次數n;

Output:特征向量LS.

這些特征主要分為3 類:第1 類為大多數鏈接預測算法所考慮的網絡拓撲結構相似性特征,例如節點的度以及節點的鄰居等;第2 類為高階結構特征,例如高階Motif 聚集系數,該特征有效捕獲了高階結構的聚集特性;第3 類為網絡演變過程中可表示結構變化的特征,例如節點間的鏈接頻次和鏈接趨勢等.這些特征都存在于現實網絡中,可以有效地表示網絡結構間的關系.

3.4.2 構建鏈接預測模型

針對鏈接預測問題,本文選用多層感知器(MLP)網絡完成預測任務,MLP 算法自從被提出以來,主要被應用于節點分類等有監督學習任務.該算法的核心是訓練學習函數f(X):Rm→Rn,其中,m是輸入的維數,n是輸出的維數.具體表示為:給定一組特征向量特征x和標簽y,它可以學習用于回歸或分類的非線性函數.

圖4 列舉了一個具有標量輸出的單隱藏層MLP 模型:模型最左邊一組代表輸入特征的神經元構成輸入層;模型中間多個有向層中分布的神經元構成整個隱藏層,每個隱藏層中的神經元將前一層的值進行加權線性求和轉換,再使用非線性激活函數進行計算得到該神經元的輸入數據;模型最右邊為輸出層,主要用于接收由最后一個隱藏層經過變換計算輸出的值.

Fig.4 Single hidden layer MLP圖4 單隱藏層MLP

MLP 模型具體用法是:給定一組訓練樣本(x1,y1),(x2,y2),…,(xn,yn),其中,xi∈Rn,yi∈{0,1},則單隱藏層 MLP模型學習到的函數為f(x):

其中,W1∈Rm和W2,b1,b2∈R是模型參數.W1,W2分別是輸入層與隱藏層之間和隱藏層與輸出層之間的權重,b1,b2分別是隱藏層和輸出層的偏置值,g(x)是激活函數.本文使用的激活函數為雙曲正切函數,計算公式如下:

對于二分類問題,f(x)通過logistic 函數能夠得到0～1 之間的輸出值.若將閾值設置為0.5,則輸出大于等于0.5 的樣本分到正類(positive class),其他情況分為負類(negative class).同時,一般情況下,MLP

算法會根據不同問題使用不同的損失函數.本文的高階鏈接預測為二分類問題,因此采用交叉熵損失函數,計算公式如下:

本文使用MLP 模型的輸入參數為算法2 構建的特征向量,同時采用3 個全連接的隱藏層進行計算,模型的輸出為當前開放三角形是否會經歷簡單閉合事件的狀態.MLP 模型最終輸出結果為0 和1,其中,1 表示該開放三角形會經歷簡單閉合事件,而0 表示該開放三角形不會經歷簡單閉合事件.

4 實驗結果與分析

本節詳細介紹了數據集、實驗環境、評價指標等內容.首先,對Motif 聚集系數特征和網絡結構演變等特征進行了有效性驗證;接著,通過與不同鏈接預測算法進行對比,對本文提出的MTLP 模型進行綜合評價.

4.1 實驗數據集

本文采用來自5 個領域的14 個數據集[27],分別是合著網絡(coauth)、在線標記網絡(tags)、在線參與網絡(threads)、電子郵件網絡(email)和近距離接觸網絡(contact).

每個數據集是一組帶有時間戳的節點集.這些數據集分布在不同的領域,因此包含了豐富多樣的結構,非常適合多種實驗測試,每個數據集的詳細信息見表1.

Table 1 Data set information表1 數據集信息

4.2 評價指標

本文使用ROC 曲線和AUC-PR 值[28]作為評價指標對實驗結果進行度量.

ROC 是由True Postive Rate(TPR)和False Postive Rate(FPR)組成的曲線,其中,TPR 代表分類器預測的正類中實際經歷簡單閉合事件的正實例占所有正實例的比例,也可表示為正確預測的覆蓋程度;FPR 代表分類器預測的正類中實際未經歷簡單閉合事件的負實例占所有負實例的比例,也可表示為預測虛報的程度.兩項指標的計算公式如下:

對于鏈接預測模型而言,根據預測時設定的閾值,在測試樣本集上會得到TPR 和FPR 的點對.如果遍歷全部閾值,就可以得到多個點對,將點對連接便得到一條經過(0,0),(1,1)的曲線,這就是此鏈接預測模型的ROC 曲線.同時,我們當然希望虛報的越少越好,覆蓋的越多越好.因此,FPR 越低,TPR 越高,ROC 曲線越接近左上角,意味著預測模型的性能越好.

由于很多時候ROC 曲線并不能明確地指出哪個分類器的效果更好,而AUC-PR 指標具有明確的數值,對應AUC-PR 值越大的分類器效果越好,因此本文也使用AUC-PR 值作為評價模型性能的標準.同時,AUC-PR 適用于類不平衡的預測問題,我們的數據集就是這種情況,因此該指標可以充分地對比不同模型的性能.

同時,本文使用隨機分數作為基準,該分數為測試集中經歷簡單閉合事件的三角形個數與訓練集中開放三角形個數的比例.隨機分數以絕對值列出,通過比較每個模型的AUC-PR 與基準的相對值來衡量不同模型的性能,分值越大,則表示模型的性能越好.

4.3 驗證特征有效性

本節主要驗證Motif 聚集系數特征和網絡結構演變相關特征的有效性,主要是從Motif 聚集系數特征和網絡結構演變特征兩個維度對數據進行系統域劃分,通過訓練一個多項式邏輯回歸模型來確定不同數據集的系統域.

本文采用scikit-learn 庫中的多項式邏輯回歸模型進行訓練學習,訓練的特征向量包含開放三角形的比例、開放三角形的平均Motif 聚集系數和開放三角形的網絡結構演變這3 項特征和一個截距項.為了防止模型過擬合,采用l2正則化進行約束,最終訓練出一個多項式邏輯回歸分類器來預測劃分的系統域.為了直觀地表示出系統域的劃分,在這里給出一個使用開放三角形比例和開放三角形的平均Motif 聚集系數作為協變量訓練出的系統域劃分圖.從圖5 上可以觀察到:本文提出的Motif 聚集系數可以很好地將不同的數據集劃分到各自的領域,從而體現出Motif 聚集系數可以作為網絡中高階結構的一項重要的特征.

Fig.5 System domain division diagram圖5 系統域劃分圖

為了更精準地驗證本文提出的特征有效性,我們采用消融實驗,分別控制平均Motif 聚集系數特征和網絡結構演變特征這兩個變量進行實驗,用于驗證系統域劃分的準確性,實驗結果見表2.

Table 2 Comparison of accuracy of different features表2 不同特征準確率對比

從表2 可以看出,任意添加一項平均Motif 聚集系數特征或者網絡結構演變特征都可以提高數據域劃分的準確性.盡管最終劃分數據域的結果并不完美,但是已經可以說明本文提出的Motif 聚集系數與網絡結構演變相關特征的有效性.

4.4 不同鏈接預測算法性能對比

4.4.1 對比方法

本文選取了10 個鏈接預測模型用于對比實驗,其中前7 個為經典的鏈接預測模型,后3 個為近兩年最新的基于機器學習的鏈接模型,分別如下.

? Harm.Mean[27]是基于啟發式的結合邊強度指示的相似性模型,主要是通過計算三角形中3 條邊對應的權值相加和的倒數,作為一項相似性指標用于鏈接預測;

? Geom.mean[27]是基于啟發式的結合邊強度指示的相似性模型,主要是通過計算三角形中3 條邊對應的權值連乘積的三次方根,作為一項相似性指標用于鏈接預測;

? Arith.mean[27]是基于啟發式的結合邊強度指示的相似性模型,主要是通過計算三角形中3 條邊對應的權值相加的均值,作為一項相似性指標用于鏈接預測;

? Adamic-Adar[1]是基于鄰居節點的相似性模型,主要通過計算三角形中3 條邊鄰居的對數倒數和,作為一項相似性指標用于鏈接預測;

? Pref.Attach[1]是基于鄰居節點的相似性模型,主要通過計算三角形中3 條邊鄰居的乘積,作為一項相似性指標用于鏈接預測;

? Katz similarity[1]是基于路徑的相似性模型,主要通過計算三角形中3 條邊的路徑和,作為一項相似性指標用于鏈接預測;

? PPR[1]是基于路徑的相似性模型,主要通過計算三角形中3 條邊對應的隨機游走的概率,作為一項相似性指標用于鏈接預測;

? Benson 等人[27]發現,連接強度和邊緣密度是高階組織鏈接的積極指標,并使用這些指標進行鏈接預測;

? Yaghi 等人[19]通過構造節點的中心性度量指標來提高預測的準確性;

? Chiu 等人[18]提出了網絡鏈接中弱估計指標用于鏈接預測,從而提高預測性能.

4.4.2 對比實驗

本文首先選取對比方法中前7 個經典的鏈接預測模型與本文提出的MTLP 模型進行對比實驗,并且使用ROC 曲線來評價每個模型的性能.這些模型都是已知的模型,可在鏈接預測任務中提供良好的預測效果.為了驗證不同模型的性能,我們選取幾個典型的數據集進行對比實驗,ROC 對比結果如圖6 所示.

Fig.6 ROC comparison results圖6 ROC 對比結果

從實驗結果可以看出:本文提出的MTLP 模型在不同數據集上都表現出了較優的性能,主要表現為ROC 曲線下的面積越大,性能越優.

除了與經典的鏈接預測模型進行對比,我們也與近兩年最新的基于深度學習的鏈接預測算法進行對比.為了更加詳細地對比每一個模型的性能,本文同時考慮以上10 個鏈接預測模型,并使用隨機模型分數作為基準,使用AUC-PR指標來評價每個模型的預測性能.實驗結果見表3,圖表中黑色加粗的數字表示在該數據集上鏈接預測性能最優的模型得分.

Table 3 Experimental results AUC-PR value表3 實驗結果AUC-PR 值

Table 3 Experimental results AUC-PR value (Continued)表3 實驗結果AUC-PR 值(續)

從上面的實驗結果可以清楚地看到:雖然沒有任何一個模型在所有數據集上都能表現最佳,但本文提出的算法可以在大多數的數據集上表現出更好的預測性能,例如coauth-MAG-History,coauth-MAG-Geology,tagsmath-sx 和tags-ask-ubuntu 數據集.這說明本文提出的算法有效捕獲了網絡的聚集特性和結構演變特性,從而得到較好的實驗結果.但是在一些數據集上表現的結果較差,例如threads-ask-ubuntu 數據集,我們通過對該數據集分析發現:該數據集聚集程度較低,同時開放三角形的比例也較低,如果開放三角形比例較低,會出現數據分布不均勻的現象,這是導致預測結果較差的主要原因.值得注意的是:從不同的實驗結果可以看出,使用不同相似性指標的模型也可以在部分數據集上表現出了較好的結果.例如基于啟發式的結合邊強度指示的相似性模型在threads-ask-ubuntu,NDC-classes 和contact-high-school 數據集上表現出了較好的預測性能,這說明網絡中節點之間的鏈接強度也可以精準地捕獲網絡結構信息.但是在一般情況下,單個特征指標僅僅在特定的網絡中起到作用,并不能完全捕獲整個網絡結構的特性.而且這些特征無法有效表示高階結構的特征,因此在大多數的數據集上表現不出較為優異的結果.

為了進一步分析本文提出的算法在部分數據集上表現較差的原因,我們從數據集本身進行分析,通過分析每個網絡的聚集分布發現,一些預測結果較好的數據集的網絡聚集程度較低,例如coauth-MAG-History,coauth-MAG-Geology 和NDC-substances 數據集.同時,一些預測結果較差的數據集的網絡聚集程度較高,例如NDCclasses 和DAWN 數據集.這表明:如果節點間的聚集程度太高,整個網絡趨向于完全圖,則網絡結構的聚集系數僅有較弱的參考價值.但是也存在例外,例如contact-primary-school 數據集聚集程度較高,但是實驗結果也表現出了較好的性能.通過對該數據集分析,我們發現該數據集有較長的時間跨度,從而產生了豐富多樣的結構.本文提出的時序特征主要通過將數據集進行切片劃分從而捕獲網絡結構演變的關系,因此較長的時間跨度可以使得數據切分更加充分,進而促進劃分后的網絡結構演變特征充分發揮了作用.因此,數據集自身存在的特性也會直接導致本文提出的模型在部分的數據集上沒有表現出較好的預測性能,這也是我們今后需要繼續關注的問題.

雖然本文提出的算法無論與經典的鏈接預測算法比較還是與最新的基于機器學習的鏈接預測算法比較,性能上都表現的不錯,但是這并不能說明本文提出的算法性能已經非常完美,因為高階鏈接預測任務還具有挑戰性.但是我們的目標是確定高階鏈接預測中一些重要結構特征,而不是精確地進行預測.因此,我們將探索網絡中更多潛在的可表示性特征作為未來的工作進行繼續研究.

5 總結與展望

本文重點分析了鏈接預測的特點以及目前面臨的難點問題,分析了網絡中高階結構的基本結構和特性,說明了在動態網絡中進行鏈接預測的目的和意義.首先,從網絡結構方面進行分析,提出了Motif 聚集系數,用于衡量高階結構的聚集程度;其次,從時序維度分析,提出了可表示網絡演變規律的節點間的鏈接頻率和鏈接趨勢等特征;最后,得益于神經網絡對數據的建模能力,本文將高階鏈接預測問題轉換為二分類問題,從而采用多層感知器網絡完成預測任務.為了進一步探索網絡中更多潛在的可表示性特征,本文未來工作將會重點分析網絡中的其他高階結構特征,例如高階結構中的結構中心性和結構相似性等特性,從而進一步挖掘網絡中潛在的信息.