康駐關(guān),金福生,王國仁

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

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

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

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

綜上所述,本文主要貢獻(xiàn)總結(jié)如下:

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

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

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

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

1 相關(guān)研究

近年來,鏈接預(yù)測方法主要應(yīng)用在社交網(wǎng)絡(luò)和其他復(fù)雜網(wǎng)絡(luò)等領(lǐng)域.針對現(xiàn)有的鏈接預(yù)測算法的研究,本文將其預(yù)測模型大致分為基于局部結(jié)構(gòu)相似性的鏈接預(yù)測方法、基于概率模型的鏈接預(yù)測方法和基于機器學(xué)習(xí)的鏈接預(yù)測方法這三大類.

(1)基于局部結(jié)構(gòu)相似性的鏈接預(yù)測方法

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

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

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

(3)基于機器學(xué)習(xí)的鏈接預(yù)測方法

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

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

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

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

(2)當(dāng)前,一些算法使用LSTM 模型解決網(wǎng)絡(luò)結(jié)構(gòu)演化過程中的時間依賴性問題,但是無法區(qū)分網(wǎng)絡(luò)中哪些表示網(wǎng)絡(luò)結(jié)構(gòu)演變的特征在預(yù)測任務(wù)中起到?jīng)Q定性作用,缺乏對網(wǎng)絡(luò)結(jié)構(gòu)演化規(guī)律的有效分析;本文重點在于分析網(wǎng)絡(luò)中存在的可表示性特征,因此本文通過對動態(tài)網(wǎng)絡(luò)進(jìn)行分析,發(fā)現(xiàn)節(jié)點間的鏈接頻率和鏈接趨勢等表示網(wǎng)絡(luò)結(jié)構(gòu)演變的重要特征,可以更加細(xì)致地解釋網(wǎng)絡(luò)結(jié)構(gòu)變化信息.

2 問題定義

本文研究的重點是預(yù)測多個節(jié)點間產(chǎn)生鏈接形成高階結(jié)構(gòu),因此我們通過研究三角形結(jié)構(gòu)來確定高階鏈接預(yù)測的模式.為了使讀者更容易理解本文的研究內(nèi)容,本節(jié)先介紹幾個相關(guān)概念,針對高階鏈接預(yù)測任務(wù)進(jìn)行形式化定義.

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

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

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

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

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

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

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

3.1 MTLP模型的基本思想

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

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

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

(2)鏈接預(yù)測的相關(guān)方法,本質(zhì)上都是利用網(wǎng)絡(luò)歷史信息并將其壓縮為一個網(wǎng)絡(luò),以預(yù)測下一時刻的網(wǎng)絡(luò).可以說,目前大多數(shù)的鏈接預(yù)測都是基于網(wǎng)絡(luò)快照的方法,例如在給定的時間內(nèi)分析給定的網(wǎng)絡(luò)快照,用于下次鏈接預(yù)測.但是這些方法僅考慮了前一時刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息,而與前一時刻網(wǎng)絡(luò)的動態(tài)發(fā)展無關(guān).因此,通過對動態(tài)網(wǎng)絡(luò)進(jìn)行分析并捕獲網(wǎng)絡(luò)結(jié)構(gòu)演變信息,是提取網(wǎng)絡(luò)結(jié)構(gòu)演化特征模塊主要解決的問題;

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

3.2 提取Motif聚集系數(shù)特征

聚集系數(shù)[22,23,24]是用來量化網(wǎng)絡(luò)中節(jié)點聚集程度的度量標(biāo)準(zhǔn).本文擴展了傳統(tǒng)的局部聚集系數(shù),將單個節(jié)點的聚集系數(shù)擴展為高階結(jié)構(gòu)的聚集系數(shù),用來衡量網(wǎng)絡(luò)中高階結(jié)構(gòu)的聚集程度,即Motif 聚集系數(shù).

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

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

算法1.計算Motif 聚集系數(shù).

Input:高階結(jié)構(gòu)g,鄰居節(jié)點集合N;

Output:Cmotif(g)(高階結(jié)構(gòu)g的Motif 聚集系數(shù)).

1 算法CalculateMotifCluf(g,N)

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

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

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

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

6triNum++

7 end if

8 end for

9 forg中的任意一個節(jié)點ido

10tempNum+=

11 end for

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

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

15conns++

16 end if

17 end for

19 returnCmotif(g)

3.3 提取網(wǎng)絡(luò)結(jié)構(gòu)演變特征

網(wǎng)絡(luò)演化的歷史為理論上的預(yù)測提供了更多信息,同時也為網(wǎng)絡(luò)分析增加了一個全新的維度.我們采用圖序列來描述網(wǎng)絡(luò)的動態(tài)變化,并分析隨著時間的推移,節(jié)點結(jié)構(gòu)之間關(guān)聯(lián)性的演變過程.

首先在數(shù)據(jù)預(yù)處理部分,我們將網(wǎng)絡(luò)切分成表示一系列圖序列的時間片集合G=(G1,G2,…,Gt?1,Gt),其中,Gt=(Vt,Et)表示第t個時間序列的網(wǎng)絡(luò)圖,每個網(wǎng)絡(luò)圖對應(yīng)一個鄰接矩陣Wt.動態(tài)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)會隨著時間t的變化而不同,主要是隨著時間的變化,節(jié)點間的鏈接產(chǎn)生了不同的變化,有的節(jié)點間添加新的鏈接,有的節(jié)點間刪除原有的鏈接,在不同的時間序列中,節(jié)點對之間的鏈接關(guān)系也會不同.每個時間片中節(jié)點間的鏈接變化如圖2所示,其中,虛線表示圖中節(jié)點從G1時刻演變到G2時刻的映射.

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

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

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

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

節(jié)點間的鏈接頻次和鏈接趨勢可以有效地捕捉到動態(tài)網(wǎng)絡(luò)演化規(guī)律,同時,這些特征也可以通過簡單的計算將其表示出來.因此,本文將在后續(xù)的鏈接預(yù)測模型中使用這些可表示網(wǎng)絡(luò)結(jié)構(gòu)演變的特征,從而有效捕獲網(wǎng)絡(luò)演變信息.

3.4 構(gòu)建基于MLP的鏈接預(yù)測算法

本節(jié)主要介紹構(gòu)建基于MLP 的鏈接預(yù)測算法,用于完成高階鏈接預(yù)測任務(wù),算法流程圖如圖3 所示.

Fig.3 Flow chart of constructing MLP-based link prediction algorithm圖3 構(gòu)建基于MLP 的鏈接預(yù)測算法流程圖

3.4.1 構(gòu)建特征向量

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

算法2.構(gòu)建特征向量.

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

Output:特征向量LS.

這些特征主要分為3 類:第1 類為大多數(shù)鏈接預(yù)測算法所考慮的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相似性特征,例如節(jié)點的度以及節(jié)點的鄰居等;第2 類為高階結(jié)構(gòu)特征,例如高階Motif 聚集系數(shù),該特征有效捕獲了高階結(jié)構(gòu)的聚集特性;第3 類為網(wǎng)絡(luò)演變過程中可表示結(jié)構(gòu)變化的特征,例如節(jié)點間的鏈接頻次和鏈接趨勢等.這些特征都存在于現(xiàn)實網(wǎng)絡(luò)中,可以有效地表示網(wǎng)絡(luò)結(jié)構(gòu)間的關(guān)系.

3.4.2 構(gòu)建鏈接預(yù)測模型

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

圖4 列舉了一個具有標(biāo)量輸出的單隱藏層MLP 模型:模型最左邊一組代表輸入特征的神經(jīng)元構(gòu)成輸入層;模型中間多個有向?qū)又蟹植嫉纳窠?jīng)元構(gòu)成整個隱藏層,每個隱藏層中的神經(jīng)元將前一層的值進(jìn)行加權(quán)線性求和轉(zhuǎn)換,再使用非線性激活函數(shù)進(jìn)行計算得到該神經(jīng)元的輸入數(shù)據(jù);模型最右邊為輸出層,主要用于接收由最后一個隱藏層經(jīng)過變換計算輸出的值.

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

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

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

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

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

本文使用MLP 模型的輸入?yún)?shù)為算法2 構(gòu)建的特征向量,同時采用3 個全連接的隱藏層進(jìn)行計算,模型的輸出為當(dāng)前開放三角形是否會經(jīng)歷簡單閉合事件的狀態(tài).MLP 模型最終輸出結(jié)果為0 和1,其中,1 表示該開放三角形會經(jīng)歷簡單閉合事件,而0 表示該開放三角形不會經(jīng)歷簡單閉合事件.

4 實驗結(jié)果與分析

本節(jié)詳細(xì)介紹了數(shù)據(jù)集、實驗環(huán)境、評價指標(biāo)等內(nèi)容.首先,對Motif 聚集系數(shù)特征和網(wǎng)絡(luò)結(jié)構(gòu)演變等特征進(jìn)行了有效性驗證;接著,通過與不同鏈接預(yù)測算法進(jìn)行對比,對本文提出的MTLP 模型進(jìn)行綜合評價.

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

本文采用來自5 個領(lǐng)域的14 個數(shù)據(jù)集[27],分別是合著網(wǎng)絡(luò)(coauth)、在線標(biāo)記網(wǎng)絡(luò)(tags)、在線參與網(wǎng)絡(luò)(threads)、電子郵件網(wǎng)絡(luò)(email)和近距離接觸網(wǎng)絡(luò)(contact).

每個數(shù)據(jù)集是一組帶有時間戳的節(jié)點集.這些數(shù)據(jù)集分布在不同的領(lǐng)域,因此包含了豐富多樣的結(jié)構(gòu),非常適合多種實驗測試,每個數(shù)據(jù)集的詳細(xì)信息見表1.

Table 1 Data set information表1 數(shù)據(jù)集信息

4.2 評價指標(biāo)

本文使用ROC 曲線和AUC-PR 值[28]作為評價指標(biāo)對實驗結(jié)果進(jìn)行度量.

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

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

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

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

4.3 驗證特征有效性

本節(jié)主要驗證Motif 聚集系數(shù)特征和網(wǎng)絡(luò)結(jié)構(gòu)演變相關(guān)特征的有效性,主要是從Motif 聚集系數(shù)特征和網(wǎng)絡(luò)結(jié)構(gòu)演變特征兩個維度對數(shù)據(jù)進(jìn)行系統(tǒng)域劃分,通過訓(xùn)練一個多項式邏輯回歸模型來確定不同數(shù)據(jù)集的系統(tǒng)域.

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

Fig.5 System domain division diagram圖5 系統(tǒng)域劃分圖

為了更精準(zhǔn)地驗證本文提出的特征有效性,我們采用消融實驗,分別控制平均Motif 聚集系數(shù)特征和網(wǎng)絡(luò)結(jié)構(gòu)演變特征這兩個變量進(jìn)行實驗,用于驗證系統(tǒng)域劃分的準(zhǔn)確性,實驗結(jié)果見表2.

Table 2 Comparison of accuracy of different features表2 不同特征準(zhǔn)確率對比

從表2 可以看出,任意添加一項平均Motif 聚集系數(shù)特征或者網(wǎng)絡(luò)結(jié)構(gòu)演變特征都可以提高數(shù)據(jù)域劃分的準(zhǔn)確性.盡管最終劃分?jǐn)?shù)據(jù)域的結(jié)果并不完美,但是已經(jīng)可以說明本文提出的Motif 聚集系數(shù)與網(wǎng)絡(luò)結(jié)構(gòu)演變相關(guān)特征的有效性.

4.4 不同鏈接預(yù)測算法性能對比

4.4.1 對比方法

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

? Harm.Mean[27]是基于啟發(fā)式的結(jié)合邊強度指示的相似性模型,主要是通過計算三角形中3 條邊對應(yīng)的權(quán)值相加和的倒數(shù),作為一項相似性指標(biāo)用于鏈接預(yù)測;

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

? Arith.mean[27]是基于啟發(fā)式的結(jié)合邊強度指示的相似性模型,主要是通過計算三角形中3 條邊對應(yīng)的權(quán)值相加的均值,作為一項相似性指標(biāo)用于鏈接預(yù)測;

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

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

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

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

? Benson 等人[27]發(fā)現(xiàn),連接強度和邊緣密度是高階組織鏈接的積極指標(biāo),并使用這些指標(biāo)進(jìn)行鏈接預(yù)測;

? Yaghi 等人[19]通過構(gòu)造節(jié)點的中心性度量指標(biāo)來提高預(yù)測的準(zhǔn)確性;

? Chiu 等人[18]提出了網(wǎng)絡(luò)鏈接中弱估計指標(biāo)用于鏈接預(yù)測,從而提高預(yù)測性能.

4.4.2 對比實驗

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

Fig.6 ROC comparison results圖6 ROC 對比結(jié)果

從實驗結(jié)果可以看出:本文提出的MTLP 模型在不同數(shù)據(jù)集上都表現(xiàn)出了較優(yōu)的性能,主要表現(xiàn)為ROC 曲線下的面積越大,性能越優(yōu).

除了與經(jīng)典的鏈接預(yù)測模型進(jìn)行對比,我們也與近兩年最新的基于深度學(xué)習(xí)的鏈接預(yù)測算法進(jìn)行對比.為了更加詳細(xì)地對比每一個模型的性能,本文同時考慮以上10 個鏈接預(yù)測模型,并使用隨機模型分?jǐn)?shù)作為基準(zhǔn),使用AUC-PR指標(biāo)來評價每個模型的預(yù)測性能.實驗結(jié)果見表3,圖表中黑色加粗的數(shù)字表示在該數(shù)據(jù)集上鏈接預(yù)測性能最優(yōu)的模型得分.

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

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

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

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

雖然本文提出的算法無論與經(jīng)典的鏈接預(yù)測算法比較還是與最新的基于機器學(xué)習(xí)的鏈接預(yù)測算法比較,性能上都表現(xiàn)的不錯,但是這并不能說明本文提出的算法性能已經(jīng)非常完美,因為高階鏈接預(yù)測任務(wù)還具有挑戰(zhàn)性.但是我們的目標(biāo)是確定高階鏈接預(yù)測中一些重要結(jié)構(gòu)特征,而不是精確地進(jìn)行預(yù)測.因此,我們將探索網(wǎng)絡(luò)中更多潛在的可表示性特征作為未來的工作進(jìn)行繼續(xù)研究.

5 總結(jié)與展望

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