王 曦，許 爽，許小可

(大連民族大學信息與通信工程學院 遼寧 大連 116600)

真實世界存在各種復雜系統(tǒng)，如果將復雜系統(tǒng)的主要元素抽象為節(jié)點和連邊，就可將其抽象為復雜網絡，如科學家合作網絡[1]、萬維網絡[2]、社交網絡[3]和交通網絡[4]等。當網絡的某些結構信息缺失時，可應用鏈路預測[5]方法來分析節(jié)點之間不確定的或潛在的鏈接關系[6]。如在線社交服務中，鏈路預測可以挖掘社交用戶的興趣并挖掘用戶之間的潛在關系，為用戶推薦感興趣的朋友[7]。在蛋白質新陳代謝網絡中，鏈路預測可推斷蛋白質之間的交互作用，從而有針對性地進行實驗來節(jié)約成本[8]。在科學家合作網絡中，可以預測科學家的合作模式和強度，對理解科研合作的組織方式具有重要的作用[9]。

鏈路預測研究中，最經典的方法是節(jié)點局部結構的相似性，如共同鄰居(common neighbors, CN)、Adamic-Adar 指標[10]、資源分配指標(resource allocation, RA)[11]、局部路徑相似性指標[12]及局部隨機游走的相似性指標[13]等，但通常不考慮節(jié)點之間鏈接的權重大小。真實復雜系統(tǒng)中元素之間的交互強度往往也蘊含著關鍵信息，可將其抽象為加權網絡進行分析，因此鏈路預測研究開始重視如何充分利用網絡連邊的權重信息。文獻[14]提出了基于加權共同鄰居指標(weighted common neighbors,WCN)、加權Adamic-Adar 指數(weighted Adamic-Adar, WAA)及加權資源分配指標(weighted resource allocation, WRA)等鏈路預測方法，通過對多個實證網絡的研究發(fā)現了加權鏈路預測中“弱鏈接的強作用”。文獻[15]提出了一種基于可靠線路的鏈路預測方法(rWCN, rWAA, rWRA)，通過對可靠路線賦予更高權重來達到更魯棒的預測性能。文獻[16]提出了一種局部加權路徑指標，精細利用路徑的權重特征來實現準確預測。文獻[17]改進了結構算法使其更適用于有向加權網絡的鏈路預測，如改進的共同鄰居算法(modified common neighbors,MCN)、改進的Jaccard 系數(MJC)、改進的Adamic Adar 算法(modified Adamic Adar, MAA)和改進的優(yōu)先鏈接算法(modified preferentialattach, MPA)。文獻[18]設計了一種高效共同鄰居指標，該指標通過分析共同鄰居節(jié)點的拓撲有效性對連邊端點兩側資源分配過程的影響來刻畫節(jié)點間相似性，在15 個實際網絡數據實驗中表明，該方法具有較高的預測精度。文獻[19]提出了一種鏈路權重預測的無監(jiān)督混合方法，結合網絡的權重一致性和節(jié)點的鏈路權重潛在特征可有效解決鏈路權重預測問題。文獻[20]通過對網絡中真實存在的連邊進行異常度排名，將鏈路預測應用在大規(guī)模癱瘓狀態(tài)下的電力系統(tǒng)的恢復，該方法不僅可以快速連通電源發(fā)電機，也能及時恢復重要線路。文獻[21]提出了基于鏈路線形的危險鏈路預測模型，對新加入交通網絡的鏈路進行預測，從而在碰撞發(fā)生之前進行相應的整治，該模型可有效準確地對危險鏈路進行預測。

雖然上述研究相對于無權鏈路預測方法都取得了更好的性能，但是這些方法僅僅是使用連邊的權重信息，沒有考慮挖掘該連邊權重形成的時序信息。在很多加權網絡尤其是社會網絡中，連邊的權重是由該連邊連接的兩個節(jié)點多次互動形成的，這種互動行為具有一定的時間特性，也是人類動力學研究的重要內容[22]。經過研究發(fā)現，兩個節(jié)點行為的時間同步性往往是由于兩個節(jié)點存在鏈接造成的[23]，因此可利用兩個節(jié)點的行為同步性來反推它們之間是否存在鏈接關系。目前該類方法已經廣泛應用于網絡結構的重構研究中[24]。文獻[25]提出檢測嘈雜實驗數據中相位同步的方法，實驗發(fā)現該方法可有效衡量網絡群體中個體的同步程度，并探究了同步性如何影響個體之間的關系。文獻[26]利用鴿子飛行軌跡的時序相關性，在成員之間重構了完整明確的網絡層次結構。文獻[27]分析了時間滯后衰減作用對于網絡重構的潛在影響，取得了較好的網絡重構效果。文獻[28]通過對具有同步和異步動態(tài)特性的網絡進行研究，揭示了機器學習方法可以重構交互網絡并識別網絡內在的動力學特征。文獻[29]根據由個人狀態(tài)的時間序列組成的傳播數據，重建了人與人之間牢固關系的主干，并成功地將該方法整合到了有針對性的免疫策略中。上述研究都是將節(jié)點行為同步信息應用在網絡重構中，目前將此類信息應用于鏈路預測的研究還很少見。

網絡重構和鏈路預測通常采用不同的研究范式和算法，本文嘗試將節(jié)點同步性信息這一經典網絡重構的方法引入到鏈路預測領域，提出一種網絡拓撲結構上融合節(jié)點行為同步指數的鏈路預測方法。該方法將節(jié)點局域結構相似性(共同鄰居指標)和節(jié)點行為在時間上的相似性(行為同步指數)相融合，充分利用節(jié)點之間的拓撲結構域和行為時間域特征。相對于僅使用網絡域基于結構和權重的主流方法，其鏈路預測效果更顯著。同時，為了探究局域結構和同步指數對鏈路預測的共同關系，嘗試使用一個可變參數調整兩者的融合比率，實驗表明可變參數在較大范圍內都不會影響鏈路預測的結果，說明了本文所提方法具有較好的魯棒性。

1 問題描述與評價指標

1.1 問題描述

定義加權網絡G=(V,E,W)，其中 V是所有節(jié)點的集合， E是網絡中連邊的集合， W是網絡中連邊權重的集合。定義 T為網絡中最大與最小時間戳的差值，將時間進行相對時間處理后基于[0,T]將整個數據劃分為兩段時間間隔[0,Tn]和[Tn+1,T]。將[0,Tn]時間上數據的連邊集合作為訓練集 ET，將[Tn+1,T]時間上的連邊集合作為測試集 EP。這兩個邊集之間的關系為：ET∪EP=E ，ET∩EP=φ，且訓練集 ET與測試集 EP的樣本為9∶1。在科學家合作網絡中，時效信息按年計。在短信網絡中時效信息按秒計。在本研究中，待分析的所有節(jié)點既在一個周期內存在，也在第二個周期內存在，即[Tn+1,T]中出現的所有節(jié)點都是[0,Tn]上已經存在的節(jié)點。對于僅在[0,Tn]和[Tn+1,T]中出現的節(jié)點本文做了刪除處理。

1.2 評價指標

Precision 只關注前L 條高分連邊的性能，根據出現連邊可能性的分數值從大到小排序，如果有m 條邊是屬于存在邊集合，那么Precision 定義為：

由該式可知，m 越大則Precision 值越高，預測越準確。

2 鏈路預測方法

2.1 基于共同鄰居的相似性指標

1) CN 指標

共同鄰居(CN)指標是通過計算兩個節(jié)點共同鄰居的數量來判斷節(jié)點相似性。定義節(jié)點x的鄰居集合Γ(x)，節(jié)點y的鄰居集合為Γ(y)，共同鄰居指標定義為：

一般來說，節(jié)點x和節(jié)點y之間的共同鄰居越多，連邊的分數值越大，節(jié)點的相似性越大。

2) AA 指標

在共同鄰居的基礎上，考慮兩端節(jié)點度的影響，則演變?yōu)锳A 指標。AA 指標的思想是度小的共同鄰居節(jié)點貢獻大于度大的共同鄰居節(jié)點。該方法通過共同鄰居的度，為每個節(jié)點附上一個權重值。這個值為該節(jié)點度的對數的倒數，定義為：

式中， kz表示x和 y的共同鄰居節(jié)點z的度。

3) RA 指標

RA 與AA 相似，都對節(jié)點度大的共同鄰居的貢獻進行抑制，即節(jié)點度越小，對網絡連接產生的貢獻就越大，RA 指標的抑制程度相對更大。因此，當網絡的節(jié)點的度都較小時，兩者區(qū)別不大。而當網絡節(jié)點中存在較大度時，因為對度大節(jié)點有更高的抑制性，所以RA 展現出相對較好的預測性能[11]。RA 指標定義如下：

2.2 基于共同鄰居的加權相似性指標

加權網絡進行鏈路預測時，不僅要考慮網絡的拓撲結構，也要考慮連邊的權重，才能取得較好的預測效果。將CN、AA、RA 擴展到加權的形式，就可以將連邊權重的信息應用到加權網絡的鏈路預測中。常用的3 種加權指標WCN、WAA 和WRA的定義為如下形式：

1) WCN 指標：

式中，W(x,z)為兩節(jié)點x 和z的連邊權重；W(z,y)為兩節(jié)點z和y 的連邊權重。

2) WAA 指標：

式中， s(z)表示鄰居節(jié)點z的強度；WAA 根據每個共同鄰居的強度值進行了加權。

3) WRA 指標：

式中，WRA 是WCN 的另一種權重賦予方式，分母不再采用強度的對數，而直接采用節(jié)點強度進行了加權。

2.3 基于可靠路線的加權相似性指標

在加權網絡鏈路預測中，如何利用權重信息是研究重點。在通信網絡中，信息的傳輸往往需要依賴最可靠的線路將數據包從源節(jié)點傳輸到目標節(jié)點，以保證數據傳輸過程中不被損壞。受通信網絡的啟發(fā)，文獻[15]提出了可靠路線加權指標的鏈路預測方法，假設所有連邊的權重都是獨立的，通過連邊權重的乘積計算兩個節(jié)點連邊的相似性得分，定義如下：

1) 加權可靠路線CN 指標(rWCN)：

2) 加權可靠路線AA 指標(rWAA)：

3) 加權可靠路線RA 指標(rWRA)：

上述3 種指標利用了可靠路徑的計算思路，改進了WCN、WAA、WRA 指標，并且在沒有提高計算復雜度的前提下，對可靠路線賦予了更高的權重，從而提高了鏈路預測的準確性。

2.4 基于行為同步指數的相似性指標

在很多真實社會網絡中，通過兩個節(jié)點多次互動形成的權重是普遍存在的，并且這種互動行為往往具有一定的時間特性，該時間特性會通過兩個節(jié)點的鏈接而產生[22]，因此可利用這兩個節(jié)點時間上的同步性來推斷它們之間的潛在鏈接關系。

從鏈路預測的角度分析，網絡中節(jié)點之間的互動存在時間上的延遲，這種時間特性可以作為一種同步現象來衡量節(jié)點的行為同步性。如果節(jié)點之間存在鏈接，它們之間的交互時間間隔越短，則這兩個節(jié)點的行為將越趨于同步，以此可推斷他們未來存在鏈接的概率就越大。如節(jié)點x給節(jié)點y 發(fā)消息，節(jié)點y每次都立即回復，說明兩個節(jié)點產生鏈接的可能性極大。如果節(jié)點x給節(jié)點z 發(fā)消息，節(jié)點z經常不回復或是時間間隔很長才回復，那么這兩個節(jié)點產生鏈接的可能性就較小。因此，在不知道兩個節(jié)點之間是否存在鏈接的情況下，觀察兩個節(jié)點之間的行為同步性可以推斷他們之間是否存在聯系。

圖1 用戶同步指數的計算過程圖

式中， Θxy是時間序列 Sx和 Sy的平均距離； Dxy是節(jié)點x到節(jié)點y的時間距離； Dyx是節(jié)點y到節(jié)點x的時間距離； Ox是節(jié)點x鄰居節(jié)點的集合； Oy是節(jié)點y鄰居節(jié)點的集合； Nx是節(jié)點x與其他節(jié)點信息交互的次數； Ny是節(jié)點y與其他節(jié)點信息交互的次數。本文將平均距離作為衡量兩個節(jié)點時間序列相似性的標準并應用于鏈路預測，平均距離越短則時間序列相似性越強，產生連邊的可能性越大[30]。式中的Dxy和 Dyx不僅可以取所有距離的平均值，也可以取所有距離的最小值，此時距離定義為：

2.5 融合結構和行為同步指數的相似性指標

本文提出的融合結構和行為同步指數指標是同時計算兩個節(jié)點之間的共同鄰居信息和行為同步指數。事件交互對應消息的發(fā)送或接收，因此定義節(jié)點發(fā)送消息的融合行為同步指數指標STCN，其中S 表示發(fā)送，T 表示時間序列，CN 為共同鄰居數量。定義接受消息的融合行為同步指數指標RTCN，其中R 表示接收，則STCN 和RTCN 的具體公式為：

式中，CN 為兩節(jié)點的共同鄰居數；由于事件交互對應消息的發(fā)送或接收，所以STCN 中， Θs是時間序列 Sx與時間序列 Sy發(fā)送消息的時間序列相似性；RTCN 中， Θr是時間序列 Sx與時間序列Sy接收消息的時間序列相似性。融合行為同步指數的相似性指標包含兩部分，一部分是以CN 為主的結構信息，一部分是以行為時效信息為主的同步指數。

為了探究局域結構和同步指數對鏈路預測的共同關系，本文使用一個可變參數 α來調整兩者的融合比率，并分析本文所提方法的魯棒性和兩類指標的相關關系，具體公式為：

式中， α取值范圍為[0,1]。當 α=0 時，此時公式中只有結構信息的存在； α=1 時，公式中只有用戶同步性存在；在兩者之間時，公式中既有結構信息的存在，也有行為同步性存在，并且在0～1之間可變參數的取值可以改變兩部分信息在預測中的比例。

3 實證分析

3.1 數據說明

本文使用了兩類實證數據，一類是3 種科學家合作網絡數據[31]，其中節(jié)點表示從事研究的科學家，連邊代表兩個科學家有合作研究的關系，連邊的權重代表科學家合作的次數，連邊時間代表科學家之間的合作時間。另一類是由運營商提供的某城市某月的3 種短信數據，其中節(jié)點代表用戶，連邊代表用戶之間的短信往來，連邊的權重代表用戶之間短信網絡的次數，連邊的時間代表用戶之間短信往來的時間。為了保護隱私，所有的電話號碼被隱藏，沒有任何信息能表明用戶身份。

1) JIS 數據網絡是以兩本期刊Journal of Informetrics、Scientometrics 作為研究對象，從Web of Science 數據庫下載了2013-2017 年的文章記錄。包括Article、Review、和Proceeding paper 這3 種類型。該網絡包含3 540 個節(jié)點，6 413 條連邊。

2) BMJ 網絡是以期刊《英國醫(yī)學期刊》(BMJ)作為研究對象，從Web of Science 數據庫下載了2013-2018 年的所有論文。該網絡包含4 389 個節(jié)點，4 335 條連邊。

3) Nature 網絡是以期刊《自然》(Nature)作為研究對象，從Web of Science 數據庫下載了2010-2018 年的所有論文。該網絡包含21 060 個節(jié)點，21 259 條連邊。

4) SD01 網絡：包含某運營商一個月內44 430個用戶節(jié)點，和68 834 條短信記錄。

5) SD02 網絡：包含某運營商一個月內72 146 個用戶節(jié)點，100 974 條短信記錄。

6) SD03 短信網絡：包含某運營商一個月內14 433個用戶節(jié)點，23 285 條短信記錄。

3.2 預測結果分析

本文使用上述兩類實證網絡，每一類有3 種真實數據集。每個網絡按時間截點劃分數據集，訓練集與測試集比例為9∶1。從不存在的邊中抽取負樣本，讓測試集中正負樣本的比例為1∶1。

表1 為6 種網絡中，融合行為同步指數指標與基于局部信息相似性指標、加權局部信息相似性指標、可靠路線相似性指標的Precision 結果比較。

表1 6 種實證網絡鏈路預測Precision 值比較

可以看出，本文提出的融合行為同步指數的鏈路預測方法的預測精度最好，其預測準確率比共同鄰居、加權共同鄰居、可靠路線策Precision 指標提高了15.3%～68.2%。

計算融合行為同步指數指標時分別給出了行為同步指數取最小值及平均值的實驗結果。每種數據中最高的預測性能加粗表示。表1 中可發(fā)現行為同步指數總是取得最佳的性能，雖然取最小值及平均值在不同網絡中預測結果有些不同，在BMJ 網絡中，行為同步指數取最小值預測更準確。而在SD01、SD02、SD03、Nature 和JIS 網絡中，取平均值預測性能更好。

除了行為同步指數的取值影響算法精度外，時間序列的方向(如發(fā)送和接收)同樣也影響著預測精度。有些網絡利用發(fā)送消息計算同步指數能取得更好的預測結果，有些網絡中用接收消息計算同步指數能取得更好的預測結果。表1 中，SD01、SD02、SD03 網絡在行為同步指數取平均值的情況下，接受消息的RTCN (mean)的預測結果更高。而在Nature、JIS 和BMJ 科學家合作網絡的預測中，發(fā)送消息的STCN (mean)預測效果更好。在短信網絡中接收消息更能有效挖掘網絡節(jié)點之間的預測關系。而在科學家合作網絡中，發(fā)送消息更能有效挖掘網絡節(jié)點之間的預測關系。

基于局部結構共同鄰居數量演化出來的一系列相似性指標，預測結構沒有明顯變化，因此它們相互之間的性能波動較小。而當局部結構信息加入了行為同步指數之后，預測結果得到了大幅提升，這說明這兩類信息具有很強的互補性。如在SD03 網絡中，基于局部結構特征的Precision值最高為0.498，加入行為同步指數之后，Precision值為0.811，相對提高了62.8%。因此，節(jié)點的行為同步指數不僅能用于網絡重構中，還可以應用在鏈路預測上。無論是在科學家合作網還是在短信交互網中，生成網絡連邊權重的時效信息都是不能忽略的重要特征，由時效信息演變的同步效果都是普遍存在的，融合同步指數的鏈路預測方法性能更具有優(yōu)勢。

3.3 融合比例變化對預測結果的影響

實驗中利用可變參數 α改變網絡結構信息和時效信息的融合 α值，同時觀察該值對預測性能的影響。兩類網絡中各選一種，以科學家合作網Nature 和短信網絡SD03 為例進行分析，每一類中其他網絡的結果與本文呈現的該類網絡結果是相似的。

圖2a 是Nature 網絡特征融合比例變化的性能曲線圖?？v軸是預測結果的Precision 值，橫軸是以0.1 為跨度的α值。預測結果顯示，不管是STCN方法還是RTCN 方法， α取0 是單一結構信息的預測結果，此時并不能達到一個較好的預測性能。α=1時是單一同步指數的預測結果，而預測效果卻是最不理想的，甚至要低于單一結構特征預測。尤其是接收消息的RTCN 特征，比單一結構信息的Precision 值下降了48.9%。當0<α<1時，無論 α取何值都能取得較高的預測性能，說明本文的方法具有很好的魯棒性。綜上所述，對于Nature 等科學家合作網絡來說，科學家的共同鄰居數量與行為同步性共同影響著合作網絡中鏈路的出現和動態(tài)演化。

圖2b 是SD03 短信交互網絡特征融合比例變化的性能曲線圖?？v軸是預測結果的Precision值，橫軸是以0.1 為跨度的 α值。在4 種特征的預測下，預測精度最低時對應的 α等于0，此時是結構信息的單一預測結果，說明短信交互網絡中只用結構信息不足以挖掘網絡的潛在鏈接信息。預測精度最高時對應0<α<1，此時為結構信息和行為同步指數共同的預測結果。 α在一定范圍內取值，預測性能都沒有顯著變化，說明了本文所提方法具有很好的魯棒性。當α=1時，圖2b 中沒有出現預測值明顯下跌的情況，結果與0<α<1時的Precision 值相差無幾，此時是行為同步指數單一預測結果。綜上所述，SD03 網絡用單一同步指數預測也會出現很好的精度，用戶之間的行為同步性可以在不依賴結構信息的情況下，實現單一特征預測并且達到較好的預測精度。

圖2 特征融合比例對預測性能的影響

考慮到科學家合作網絡和短信網絡的形成機制不同，科學家合作網絡因為n 個合作者連成完全圖，所以共同鄰居指數很重要。這里假設同步性在合作網絡中起的作用實際上只能在CN 值相同的時候提高區(qū)分度，因此將科學家合作網和短信網絡的預測參數 α值調節(jié)到一個非常小的值( α=0.001)，再調節(jié)到一個非常接近1 的值( α=0.999)，實驗結果如圖3 所示。

圖3 是Nature 期刊科學家合作網絡在 α=0.001和 α=0.999 的預測結果，并將該結果與 α取0 和1的預測結果做對比。在科學家合作網絡之中， α=0.001 就可以達到一個提升預測性能的作用，并且與α=0.999 并無差別。說明此時同步性指標的作用類似于局域性指標里面的高階項，因此預測的過程中以CN 為主，同步性可以輔助CN 達到提高預測分辨率的效果。

圖4 是短信交互網絡SD03 在α=0.001 和α=0.999的預測結果，并將該結果與α取0 和1 的預測結果做對比。短信網絡的實驗結果中可以看出CN 指標作用很小，而同步性無論在 α=0.001 還是 α=0.999都可以達到良好的預測精度。本文統(tǒng)計了6 種網絡的平均聚類系數，結果如表2 所示。

圖3 Nature 網絡預測結果

圖4 SD03 網絡預測結果

從表2 中可以看出，3 個短信網絡的平均聚類系數都很小，說明短信網絡的結構都十分松散，因此預測過程中鄰域結構信息的價值很小，這也導致了 α=1 時圖2b 中SD03 網絡沒有出現預測值明顯下跌的情況。而合作網絡的平均聚類系數相對較大，也說明了科學家合作網絡的共同朋友結構信息明顯，對CN 的依賴性較大，同步信息僅起到提高更好分辨率的作用。

表2 6 種實證網絡平均聚類系數

4 結 束 語

本文將用戶行為同步性信息這一網絡重構的方法引入到鏈路預測領域，提出一種網絡拓撲相似性上融合節(jié)點行為同步指數的鏈路預測方法。通過對該方法在真實社會時效網絡上與局部結構相似性指標、加權局部結構相似性指標、可靠路線相似性指標進行對比分析，發(fā)現該方法可有效提高網絡的鏈路預測性能。相對于經典方法，本文方法在Precision指標上提高了15.3%～68.2%。

本文方法不僅可提高鏈路預測的性能，也可揭示加權網絡的內在結構特征和行為同步指數對鏈路預測的相互作用與共同影響。研究發(fā)現，在科學家合作網絡中，需要結構信息和同步指數共同作用，才會得到良好的預測效果。而在短消息交互網絡中，結構相似性指標的預測性能較差，而僅僅使用行為同步指數就可以接近最優(yōu)的預測性能。在以后的工作中，將采取更優(yōu)的方式將節(jié)點行為同步指標融合與網絡結構相似特性進行融合，并且對結構信息的時效性展開更深入研究，以達到更優(yōu)的鏈路預測性能。同時，也將對短信網絡和科學家合作網絡的細節(jié)機制做更深入分析，包括發(fā)送短信的模式、群發(fā)和短時間頻繁發(fā)送等，以根據其結構特點來設計鏈路預測方法。本文所提方法可以拓展到社團檢測、信息傳播等其他網絡科學領域的實際應用中。