陳東明， 袁澤枝， 黃新宇， 王冬琦

(東北大學 軟件學院， 遼寧 沈陽 110169)

網(wǎng)絡科學的研究不僅是在宏觀上挖掘不同復雜網(wǎng)絡之間的共性以及它們所遵循的普適性規(guī)律，從中觀層面對網(wǎng)絡群組結構和層次結構進行研究，而且在微觀層面也提出節(jié)點的度及其度分布、最短距離等來表示網(wǎng)絡的測度.然而根據(jù)已有的信息構建網(wǎng)絡模型時，所得到的觀測數(shù)據(jù)并不一定真實有效，或部分缺失、或摻雜錯誤數(shù)據(jù)等，有時還會因時間因素導致不能夠獲得潛在的網(wǎng)絡信息，在仿真實驗時得不到準確的數(shù)據(jù)和理想的研究結論.因此，鏈路預測成為網(wǎng)絡信息挖掘的一個研究熱點[1].

鏈路預測(link prediction)是通過對已知的網(wǎng)絡拓撲結構進行分析，構建預測算法以發(fā)現(xiàn)網(wǎng)絡中尚未存在連邊的節(jié)點對之間產(chǎn)生連邊的概率[2]，本質上是從網(wǎng)絡鏈路的微觀層面解釋網(wǎng)絡結構形成的原因.鏈路預測解決的是網(wǎng)絡中缺失信息的還原與預測問題.所謂還原，指的是對網(wǎng)絡中實際存在的但尚未被探測到的鏈路的發(fā)現(xiàn)，這種鏈路也被稱為未知鏈接(unknown links)；所謂預測，指的是對網(wǎng)絡中目前不存在但是未來很可能存在的鏈路的預測，這種鏈路也被稱為未來鏈接(future links).

復雜網(wǎng)絡中的鏈路預測算法主要是基于網(wǎng)絡靜態(tài)圖，即網(wǎng)絡規(guī)模以及節(jié)點間相互作用不變，然后分析其拓撲結構，推斷網(wǎng)絡的真實情況.然而現(xiàn)實網(wǎng)絡是動態(tài)變化的，網(wǎng)絡結構隨時間推移不斷變化，時態(tài)網(wǎng)絡(temporal networks)[3]中節(jié)點間產(chǎn)生連邊的時間信息對預測將來產(chǎn)生新鏈接的概率有重要的意義.Tang[4]將時態(tài)網(wǎng)絡切片，提出了時態(tài)距離、可達性等概念研究時態(tài)網(wǎng)絡.Paranjape等[5]定義δ-motif小子圖作為分析時態(tài)網(wǎng)絡的工具，大大提高了算法的時間效率.Lei等[6]提出了一種非線性模型(GCN-GAN)來解決加權的時態(tài)網(wǎng)絡鏈路預測問題.該模型利用GCN計算各個時間切片的局部特征，然后將計算結果輸入到LSTM模型，刻畫網(wǎng)絡的動態(tài)變化情況，再利用GAN生成預測結果.由于該方法的訓練過程較為復雜，因此還需要進一步優(yōu)化以實現(xiàn)大規(guī)模網(wǎng)絡上的鏈路預測.Yasami等[7]利用隨機多層網(wǎng)絡模型解決網(wǎng)絡中的鏈路缺失和未來鏈路的預測問題，并在仿真數(shù)據(jù)集和真實的DBLP數(shù)據(jù)集中表現(xiàn)出眾.然而，算法僅限于有向網(wǎng)絡，其他類型的網(wǎng)絡中缺少通用性.此外，一些統(tǒng)計學方法，如整合移動自回歸模型，即ARIMA[8]也可以用于時態(tài)網(wǎng)絡鏈路預測研究，但受限于網(wǎng)絡數(shù)據(jù)的平穩(wěn)性檢驗，因此對于網(wǎng)絡結構隨時間變化較大的預測效果并不是十分理想.因此，時態(tài)網(wǎng)絡鏈路預測問題還有很大的研究空間.

1 問題描述

G={Gt|t=1,2,,m}.

(1)

其中，Gt表示網(wǎng)絡在t時刻的拓撲結構.

時態(tài)網(wǎng)絡中的鏈路預測問題可以描述為：已知0～T時刻的網(wǎng)絡拓撲結構變化情況，預測第T+1時刻的網(wǎng)絡中節(jié)點的連邊情況，簡單來說，就是根據(jù)網(wǎng)絡歷史信息預測下一時刻網(wǎng)絡中的連邊情況.以數(shù)學形式表示為

G={Gt|t=0,1,2,,T}?GT+1.

(2)

2 算法設計與分析

2.1 算法提出

鏈路的存在與當前網(wǎng)絡的拓撲結構有著密不可分的關系，如果在每一層的網(wǎng)絡時間快照中計算節(jié)點對的相似性值，則會得到對應的一系列按時間順序排列的節(jié)點對之間的相似性值，記為

S={St(vx,vy)|t=1,2,,m}.

(3)

其中，St(vx,vy)表示在第t時刻的網(wǎng)絡結構中節(jié)點對(vx,vy)的相似性值.在第t時刻，網(wǎng)絡可以視為靜態(tài)網(wǎng)絡，則可以利用靜態(tài)網(wǎng)絡中的相似性指標計算相似性.

基于共同鄰居的JC指標[9]、AA指標[10]等在實驗中都有很好的表現(xiàn)，而且算法復雜度低且適用于大型網(wǎng)絡.盡管表現(xiàn)良好，但是由于所使用的網(wǎng)絡信息有限，因此預測準確度不夠理想.該方法的另一個劣勢在于，鏈路預測指標對于連邊的刻畫粒度比較粗糙.當網(wǎng)絡中子圖結構相似時，只利用共同鄰居這一信息會忽略鄰居節(jié)點間的連邊關系這一重要信息，具有不同結構的節(jié)點對之間的相似性指標值區(qū)分度不大.圖1所示為具有相同共同鄰居信息的網(wǎng)絡A和B，有兩對未連接的種子節(jié)點(A,a) 和(B,b)都只有3個共同鄰居節(jié)點.

分別計算圖1所示網(wǎng)絡中兩個種子節(jié)點的連接概率，如果以Jaccard指標值表示Score分數(shù)值，那么在網(wǎng)絡A中S(vA,va)=3/7，在網(wǎng)絡B中S(vB,vb)=3/7.顯然，JC指標賦予了它們相同的值，然而網(wǎng)絡B中的兩個種子節(jié)點顯然比網(wǎng)絡A中的兩個種子節(jié)點有更緊密的關系，局部相似性更高.因此可知，所利用的局部信息不能輕易地區(qū)分這兩對節(jié)點，也不足以完整地表示節(jié)點之間的相似性.

為了更加完備地利用網(wǎng)絡的結構信息，本文利用鄰居節(jié)點的局部聚類信息來表達鏈路的結構信息，這樣的優(yōu)勢在于可以表達與目標鏈路具有相同結構的一些其他重要鏈路的結構信息.如何利用節(jié)點的聚集特性來描述種子節(jié)點之間產(chǎn)生連邊的可能性，提出以下兩種假設思路：

1)假設種子節(jié)點間產(chǎn)生鏈接的概率(或分值)等于節(jié)點間的相似性值，而相似性可以用種子節(jié)點的共同鄰居節(jié)點的聚類性表示.

2)如果種子節(jié)點間產(chǎn)生鏈接的概率(或分值)等于節(jié)點間的相似性值，假設鄰居節(jié)點的聚類性可以增強種子節(jié)點間原有的相似性.

在網(wǎng)絡中，連邊關系的局部聚集特性表現(xiàn)形式為所有的連邊都比較緊密，聚集成一個簇，也可以稱之為社區(qū)結構，而節(jié)點的局部聚集特性可以由聚類系數(shù)(clustering coefficient)[11]來表示.用數(shù)學公式表達，其定義如下：

(4)

其中:Ci為節(jié)點的聚類系數(shù)；Ti是{ejk:vj,vk∈L(i),ejk∈E}中邊的數(shù)目，節(jié)點vj,vk是節(jié)點vi的鄰居節(jié)點，L(i)是節(jié)點vi的鄰居節(jié)點集合，ejk是節(jié)點vi的鄰居節(jié)點之間的連邊；ki表示節(jié)點vi的度.節(jié)點的聚類系數(shù)反映了節(jié)點的鄰居節(jié)點之間相互連接的概率.Ci取值在0與1之間，Ci越接近1，說明節(jié)點vi的鄰居們抱成一團，節(jié)點vi的局部越緊密；Ci越接近0，說明節(jié)點vi的鄰居比較稀疏，整個結構接近樹狀.

(5)

(6)

其中，|Θcn|表示對CN指標歸一化處理，保證每個相似值平等對待，避免相似值過大，與事實相悖.由CN指標計算公式Sxy=|Γ(x)∩Γ(y)|，其中Γ(x)是節(jié)點vx的鄰居節(jié)點的集合，z∈Γ(x)∩Γ(y).由此可知，CN指標的相似性分值S∈[0,)，需要采用函數(shù)將S∈R(R為實數(shù))映射到[0, 1]，本文采用具有較好歸一化效果的Logistic函數(shù).結合式(5)和式(6)，可以得到適用于時態(tài)網(wǎng)絡的節(jié)點相似性計算公式：

(7)

(8)

本文將網(wǎng)絡時間快照計算得到的相似性值序列S={St(vx,vy)|t=1,2,,m}看作是一組動態(tài)數(shù)列，為了使模型簡單易于計算，降低算法的計算復雜度，采用線性回歸(linear regression，LR)預測模型[12]作為基本的回歸預測模型，該模型計算效率高、性能良好，且模型的預測范圍較小，預測值在[0,1]之間.在文獻[13]中作者將科學家合作網(wǎng)絡劃分成網(wǎng)絡時間序列，然后利用有監(jiān)督和無監(jiān)督兩種方法進行鏈路預測實驗，結果表明在同等指標下，無監(jiān)督預測的線性回歸模型(LR)表現(xiàn)較好.

(9)

結合式(7)和式(8)，利用一元線性回歸分析法可以計算最佳參數(shù)a和b的值，最終得到在第t時刻的相似性計算公式為

(10)

(11)

2.2 算法過程描述

本算法的核心思想是：將網(wǎng)絡劃分為多個時間快照，然后利用所有快照的歷史信息來預測未來時刻的網(wǎng)絡狀態(tài).時態(tài)網(wǎng)絡鏈路預測算法過程為

輸入：時態(tài)網(wǎng)絡G(V,E,T)

輸出：算法評價指標值

1)讀取網(wǎng)絡G(V,E,T)，獲取網(wǎng)絡中所有可能出現(xiàn)的邊.

2)將時態(tài)網(wǎng)絡劃分為m個單層網(wǎng)絡，構建一系列網(wǎng)絡時間快照{Gt|t=1,2,,m}.

3)根據(jù)式(7)、式(8)分別計算前m-1個時刻的節(jié)點對之間的相似性值，構建相似性值時間序列.

4)選擇對比度量指標[NCC, NCCP, CN, JC, AA, RA]，計算在其他相似性指標下的節(jié)點對的相似性值.

5)根據(jù)得到的前m-1個時刻的分數(shù)值序列訓練得到預測模型，采用式(10)、式(11)計算第m時刻節(jié)點間的相似性值.

6)計算衡量算法的多個評價指標，如AUC(接受者操作特性曲線下方的面積)、精確度P、召回率R和F1指標等.

2.3 復雜度分析

CN指標[14]的時間復雜度與節(jié)點的度有關，假設網(wǎng)絡節(jié)點數(shù)為N,整個網(wǎng)絡的平均度為k，則計算共同鄰居的時間復雜度為O(k)，則CN算法的時間復雜度為O(N2k).基于共同鄰居的JC，AA，RA算法[15]與CN算法有類似的計算過程，因此它們有相同的時間復雜度.基于隨機游走的SimRank算法[16]的時間復雜度為O(Nkl)，其中l(wèi)是隨機游走的步數(shù).本文所提出的兩種相似性度量方法NCC和NCCP需要計算節(jié)點的聚類系數(shù)，進行鏈路預測過程的時間復雜度為O(N2k).以上算法的時間復雜度比較如表1所示.

表1 經(jīng)典算法的時間復雜度比較

由表1可以看出，SR算法時間復雜度最低，是O(Nk)，因此效率最高.但由于其屬于全局迭代算法，包含隨機游走過程，因此實驗結果并不穩(wěn)定.本文提出算法的時間復雜度與其他同類算法相同，都是O(N2k)，雖然略高于SR算法，但因為其不存在隨機過程，保證了結果的穩(wěn)定性，因此具有更好的適用性.

3 實驗分析

3.1 相似性度量方法對比實驗

本文選取不同領域的6個真實網(wǎng)絡數(shù)據(jù)集:空手道俱樂部網(wǎng)絡(Karate)、海豚社會關系網(wǎng)絡(Dolphins)、911恐怖襲擊網(wǎng)絡(911data)、美國政治書籍網(wǎng)絡(Polbooks)、美國大學生足球俱樂部(Footballs)和科學家合作網(wǎng)絡(Scientists).6個真實網(wǎng)絡數(shù)據(jù)集的統(tǒng)計特征見表2.

本文采用隨機抽樣法劃分網(wǎng)絡數(shù)據(jù)集，測試集的比例默認設定為10%.選擇傳統(tǒng)的4個鏈路預測方法作為對比算法，分別是基于共同鄰居的CN指標、Jaccard指標(JC)、AA指標、RA指標.循環(huán)重復實驗多次，采用評價指標AUC的平均值作為算法的評估結果，如表3所示.

表2 網(wǎng)絡的統(tǒng)計特征

注：|V|表示網(wǎng)絡的節(jié)點數(shù)；|E|表示網(wǎng)絡中的連邊數(shù)；k表示網(wǎng)絡的平均度；|C|為網(wǎng)絡的平均聚類系數(shù)；表示網(wǎng)絡的平均連通程度；|D|表示網(wǎng)絡的平均最短路徑的距離.

表3 不同網(wǎng)絡數(shù)據(jù)集的AUC值

注：表中黑體加下劃線標注的是最大值，黑體標注的是次大值.

由表3可知，對于Karate，Dolphins和911data這3個較小規(guī)模的網(wǎng)絡，AA和RA指標具有較高的預測精確度，所提出的NCC和NCCP指標表現(xiàn)也比較優(yōu)異.在Polbooks網(wǎng)絡數(shù)據(jù)集中，NCCP和RA指標表現(xiàn)顯著，且平均AUC值達到了0.873.在Scientists網(wǎng)絡中AUC值達到了0.931，預測精確度高，NCCP指標預測效果最好.實驗結果表明，網(wǎng)絡鄰居節(jié)點的聚類系數(shù)可以提高預測精確度.

為了更加清晰地展現(xiàn)NCC和NCCP指標的性能，做了以下顯著性檢驗：本文采用皮爾遜相關系數(shù)進行檢驗，首先將NCC和NCCP指標與CN，JC，AA，RA指標進行對比計算，分別得到相應指標的假設機率(p)，然后把分別得到的p加和取平均得到NCC指標的p為0.000 6, NCCP指標的p為0.000 8，均遠小于0.05.所以本實驗效果較顯著.

為了驗證NCCP相似性指標對CN指標的增強效果，本文利用AUC值的對比情況來刻畫，實驗得到如表4所示數(shù)據(jù).由后兩列計算結果可以看出，在添加鄰居節(jié)點的聚類系數(shù)后構建的NCCP指標比CN指標預測效果有了普遍的提高，說明NCCP有一定的增強效果.

表4 NCCP指標的增強效果

注：α表示NCCP比CN增強的部分與CN的百分比；β表示NCCP比NCC增強的部分與NCC的百分比.

根據(jù)表4結果可知，NCC指標與NCCP指標在整體上優(yōu)于CN指標.

3.2 時態(tài)網(wǎng)絡鏈路預測實驗

為了驗證時態(tài)網(wǎng)絡的鏈路預測算法的效果，本文使用Email-Eu-core temporal network時態(tài)網(wǎng)絡數(shù)據(jù)集[5].該網(wǎng)絡是根據(jù)歐洲某大型研究機構內(nèi)部成員的電子郵件往來關系所構建的，對所有接收和發(fā)出的郵件信息內(nèi)容作匿名處理.數(shù)據(jù)集不包含成員和其他地方地區(qū)的通信郵件，僅限于機構內(nèi)部核心成員之間的通信，完整的數(shù)據(jù)集包含了來自4個部門成員之間的所有電子郵件，時間跨度為802天.本文所使用的網(wǎng)絡數(shù)據(jù)集來自第三個部門(Dept3)，該數(shù)據(jù)集有89個節(jié)點、12 216條時態(tài)邊，轉化為靜態(tài)網(wǎng)絡則有1 506條邊，時間跨度為802天.節(jié)點代表機構內(nèi)部的部門成員，每條連邊代表他們之間有一次郵件往來，數(shù)據(jù)集中每條數(shù)據(jù)(u,v,t)表示在時間t從用戶u向用戶v發(fā)送了電子郵件.

利用精確度P、召回率R和F1指標對預測結果進行評價，如果按天劃分時態(tài)網(wǎng)絡，那么每日的郵件數(shù)量即代表每層網(wǎng)絡的連邊數(shù)目，得到如表5所示結果.

表5 按日劃分時態(tài)網(wǎng)絡預測結果的評價指標值

由表5可知，NCC指標的預測結果明顯優(yōu)于其他指標，說明基于鄰居節(jié)點聚類的度量指標可以提高鏈路預測精確度.表5中的P值都普遍偏低，究其原因，一方面時態(tài)網(wǎng)絡數(shù)據(jù)集本身較小，另一方面網(wǎng)絡劃分的層數(shù)過多.按天劃分時態(tài)網(wǎng)絡導致每層的連邊都特別稀疏，信息很零散，使所有指標的預測效果都偏低.

如果按月劃分時態(tài)網(wǎng)絡, 得到如表6所示結果，NCC指標預測結果仍然優(yōu)于其他指標，顯示其有效性；且3個評價指標值比按天劃分的網(wǎng)絡的評價指標值都有所提高，說明時態(tài)網(wǎng)絡鏈路預測的精確度還與網(wǎng)絡劃分的層數(shù)有關系，當網(wǎng)絡劃分過細時，網(wǎng)絡分辨率很高，則預測效果不理想.

表6 按月劃分時態(tài)網(wǎng)絡預測結果的評價指標值

選取目前公認的比較好的RA指標結合ARIMA模型作為基線算法，與本文提出的NCC指標結合線性回歸模型進行比較，使用按月劃分的網(wǎng)絡數(shù)據(jù)集，隨著層數(shù)的增加得到的AUC結果如圖2所示.

由圖2可看出，除了層數(shù)為4和13的時候本文提出的方法低于ARIMA_RA方法，其他情況均好于ARIMA_RA方法.

綜合以上實驗結果，本文所提出的NCC指標在對時態(tài)網(wǎng)絡的鏈路進行預測時優(yōu)于其他相似性指標，說明在考慮鄰居節(jié)點的聚集情況后，更貼近真實網(wǎng)絡中人們交流協(xié)作的過程，因此預測效果更好.并且，從以上兩種劃分形式可以看出，時態(tài)網(wǎng)絡的預測效率還與時間的劃分和時態(tài)網(wǎng)絡模型有密切關系.

將網(wǎng)絡劃分為m個時間快照，然后利用所有快照的歷史信息來預測未來時刻的網(wǎng)絡狀態(tài)是本文方法的研究思路.然而，在現(xiàn)實網(wǎng)絡中，不同時刻網(wǎng)絡狀態(tài)對預測未來時刻網(wǎng)絡狀態(tài)所貢獻的重要性是不同的，例如信息傳播過程中，最近時間節(jié)點的信息最重要，歷史時間中的過時信息的影響力不大.為了在本次時態(tài)網(wǎng)絡鏈路預測中驗證該思想，選擇預測時刻(即第m層)的前n層網(wǎng)絡信息進行預測.實驗中n取1,2,4,7,9,10，得到如表7，表8所示的預測結果.

表7 預測結果精確度評價指標值

由表7和表8中數(shù)據(jù)可知，n=1時所有預測算法的精確度都相同；當n=2時，兩個評價指標在所有算法中的值都開始減小，此時AA指標預測效果最好；當n逐漸增大時，兩個評價指標都普遍呈減小的趨勢，這說明越貼近預測時間的網(wǎng)絡結構對最終結果的影響越大.而且，在n增大的過程中，本文所提出的NCC和NCCP指標對時態(tài)網(wǎng)絡的鏈路預測效果逐漸開始顯示其優(yōu)越性.

表8 預測結果F1值評價指標值

4 結 語

本文將時態(tài)網(wǎng)絡劃分為一系列時間快照序列，利用所提出的度量指標計算每一層網(wǎng)絡中的節(jié)點對相似性，構建節(jié)點對相似性時間序列，然后，結合時間序列回歸模型預測節(jié)點對未來的相似性.實驗結果表明，利用鄰居節(jié)點的聚類信息可以提高預測精度，利用真實郵件網(wǎng)絡數(shù)據(jù)集驗證了所提出的指標的預測效果優(yōu)越性，并且實驗結果證明越接近預測時間的網(wǎng)絡結構對預測結果影響越大.