楊曉翠，宋甲秀，張曦煌

江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122

1 引言

從20世紀90年代開始，以互聯(lián)網(wǎng)為代表的網(wǎng)絡信息技術的迅速發(fā)展將人類推進了復雜網(wǎng)絡時代?，F(xiàn)實世界的許多社會，生物和信息系統(tǒng)，從神經(jīng)系統(tǒng)到生態(tài)系統(tǒng)，從道路交通到互聯(lián)網(wǎng)，從蟻群結(jié)構到人類的社會關系，都可以自然地被描述為網(wǎng)絡，其中節(jié)點代表實體，鏈接表示節(jié)點之間的關系或交互[1-2]。不可否認，在這個“大數(shù)據(jù)”時代，社會的數(shù)據(jù)越來越多地被各種信息系統(tǒng)所收集，快速增長的數(shù)據(jù)集包含大量潛在有用的信息，但有價值的信息越來越難以提取[3]。人類的生活與生產(chǎn)活動日漸依賴于各種復雜網(wǎng)絡系統(tǒng)安全可靠地運行。因此，復雜網(wǎng)絡的結(jié)構性質(zhì)和內(nèi)部關系、大型復雜系統(tǒng)中有用的潛在信息的表達和挖掘成為與日常生活和社會結(jié)構密切相關的研究重點,引起了社會各界的廣泛關注。

鏈路預測作為將復雜網(wǎng)絡和信息科學聯(lián)系起來的重要橋梁，重在處理信息科學中最基本的問題——缺失信息的還原和預測。網(wǎng)絡中的鏈路預測是指如何通過已知的網(wǎng)絡節(jié)點和網(wǎng)絡結(jié)構等信息，預測網(wǎng)絡中尚未連接的兩個節(jié)點之間產(chǎn)生鏈接的可能性[4]。這種預測既包含對未知鏈接的預測，也包含對未來鏈接的預測。鏈路預測是一大類普適問題的抽象，其相關研究不僅能推動網(wǎng)絡科學和信息科學理論上的發(fā)展，而且具有巨大的實際應用價值。理論上，由于刻畫復雜網(wǎng)絡結(jié)構內(nèi)部特征的統(tǒng)計量非常多，難以比較不同機制的優(yōu)缺點，而鏈路預測可以提供一個簡單統(tǒng)一的平臺，用于公平比較網(wǎng)絡演進機制，促進復雜網(wǎng)絡演進模型的理論研究，有助于復雜網(wǎng)絡演進機制的了解[5]。實際中，鏈路預測研究可以用于指導蛋白質(zhì)相互實驗，進行在線社交推薦，找出交通傳輸網(wǎng)絡中的重要連邊，監(jiān)控金融交易網(wǎng)絡的欺詐活動，預測美國聯(lián)邦最高法院法官的投票等，在未來的科學和工程中將扮演越來越重要的角色。

本文剩余結(jié)構組織如下：第2章討論領域內(nèi)相關的理論和研究成果，概述本文算法；第3章介紹問題、基準算法及評價指標；第4章詳細介紹本文預測算法CELP及CELP*；第5章給出實驗結(jié)果和分析；第6章進行總結(jié)與展望。

2 相關工作

近年來已經(jīng)提出了不同背景的許多鏈路預測方法，廣泛使用了包括實體或節(jié)點的屬性和網(wǎng)絡的拓撲兩種類型的信息。一些基于機器學習的方法通過使用屬性信息獲得了非常好的預測結(jié)果。然而，鑒于在許多情況下，由于隱私保護或數(shù)據(jù)質(zhì)量問題，屬性信息難以訪問。本文只關注使用單獨拓撲結(jié)構信息的基于相似度的方法。根據(jù)研究網(wǎng)絡范圍 的差異，基于節(jié)點相似性的鏈路預測方法大致分為3類[5]：基于網(wǎng)絡局部結(jié)構的預測算法、基于網(wǎng)絡全局結(jié)構的預測算法、基于準局部結(jié)構的預測算法。

基于網(wǎng)絡局部結(jié)構的預測算法只利用節(jié)點的鄰居信息，以 PA(preferential attachment)[6]、CN(common neighbors)[6]、AA(Adamic-Adar)[6]、JC(Jaccard)[6]、RA(resource allocation)[6]、Salton[6]、Sorenson[6]、CAR(Cannistrai-Alanis-Ravai)[6]等最為典型。此后，Jia等人針對引用網(wǎng)絡提出了用H指標[7]代替度，以加權方式有效衡量引文重要性的同時，增強了Salton、Sorenson和AA這三種經(jīng)典鏈路預測算法，實驗結(jié)果表明該方法在引文網(wǎng)絡表現(xiàn)良好。高等人[8]提出了一種基于三元閉包的節(jié)點相似性鏈路預測算法，通過計算出每個節(jié)點在網(wǎng)絡中所占三元閉包的權重，并將該權重用于節(jié)點相似性指標中，提高了預測精度，但卻是以O(N3)的時間復雜度為代價。

相對于局部結(jié)構的預測算法,全局結(jié)構相似性算法則考慮了整個網(wǎng)絡的結(jié)構，包括Katz[6]、LHN2(Leicht Holme-Newman)[6]、ACT(average commute time)[6]、RWR(random walk with restart)[6]、SimRank[6]、MFI(matrix-forest theory)[6]等?；跍示植拷Y(jié)構的預測算法，無需全局網(wǎng)絡拓撲信息，而是利用比局部指標更多的信息，如 LP(local path)[6]、LRW(local random walk)和 SRW(superposed random walk)[6]。近期基于準局部結(jié)構的研究成果有，孫等人將節(jié)點的度和鄰居信息相結(jié)合，提出了LAS(local affinity structure)[9]算法，來顯示節(jié)點對和其共同鄰居間的親密關系,并通過實驗說明了該算法的可行性，但該方法依舊只是停留在節(jié)點信息的利用上，并未考慮鏈路對于相似性的貢獻。武等人直接根據(jù)節(jié)點聚類系數(shù)設計了一個新的方法，稱為基于聚類系數(shù)的鏈路預測算法（clustering coefficient for link prediction，CCLP）[10]。實驗表明，具有節(jié)點聚類系數(shù)的簡單的基于共同鄰居的方法在預測缺失鏈接方面具有很好的有效性，但其仍然采用通用估計，同樣沒有考慮特定預測節(jié)點對的局部網(wǎng)絡環(huán)境。

一些結(jié)果表明社區(qū)/群集結(jié)構可以提高鏈路預測精度的性能[11-12]。因此，幾種方法直接或間接地將各種社區(qū)檢測算法檢測到的社區(qū)與現(xiàn)有的相似性指標相結(jié)合[13-15]。還有一些更為復雜的模型和方法的研究，如Gao等人[16]提出了一種利用網(wǎng)絡中多個信息源獲取鏈路發(fā)生概率的模型。Barbieri等人[17]提出了一種用于定向和節(jié)點歸屬圖的鏈路預測的隨機主題模型。該模型不僅預測鏈接，而且還為每個預測的鏈接生成不同類型的解釋。Hu等人[18]提出了一種在社會網(wǎng)絡中檢測人體運動的概率模型，并提出了一種使用基于約束的遺傳算法對人體運動進行標記的方法來優(yōu)化模型。然而，這樣的概率模型需要鏈接外觀的預定義分布，這對于給定的網(wǎng)絡是很難知道的。

最近，Lv等人提出了結(jié)構一致性的概念，用于反映網(wǎng)絡的固有鏈路可預測性，并提出了一種比現(xiàn)有技術方法更為準確和魯棒的鏈路預測的結(jié)構擾動方法[19]。Zhang等人[20]通過結(jié)合機器學習和神經(jīng)網(wǎng)絡技術，提出Weisfeiler-Lehman神經(jīng)機器（Weisfeiler-Lehman neural machine，WLNM）模型，以圖形形式學習拓撲特征，預測鏈接的形成，取得了比大多數(shù)基于節(jié)點鄰居的方法更好的結(jié)果。

到目前為止，有效的鏈路預測仍然是一個很大的挑戰(zhàn)。局部相似性方法仍然是解決復雜網(wǎng)絡鏈路預測問題的良好選擇。因此，本文繼續(xù)對局部網(wǎng)絡拓撲信息的鏈路預測進行深入研究。在基于共同鄰居節(jié)點是影響預測節(jié)點對的相似性的重要因素之一這一事實之上，考慮到局部網(wǎng)絡環(huán)境，即鏈路聚類信息在預測缺失鏈接中的功能，提出了基于集體影響和邊聚類信息的鏈路預測算法CELP，并將其進行擴展，利用貝葉斯網(wǎng)絡參數(shù)學習，設計出適用于標簽網(wǎng)絡的預測算法CELP*。本文算法主要有以下幾個優(yōu)點：首先是容易理解和實現(xiàn)；其次，預測效果好且性能穩(wěn)定，多個規(guī)模和領域的數(shù)據(jù)集的實驗結(jié)果表明，所提出的鏈路預測算法在達到與經(jīng)典算法相似的AUC的同時，提高了0到96%不等的預測精確度；再次，無參數(shù)，這使得它更容易應用于不同類型的網(wǎng)絡，因為為特定網(wǎng)絡選擇適當?shù)膮?shù)總是需要更多的信息，這通常不容易獲得；最后，貝葉斯網(wǎng)絡架構設計靈活，可根據(jù)自身需要添加屬性節(jié)點。

3 基本算法

3.1 問題描述及基準算法介紹

定義一個無向無權網(wǎng)絡G(V,E)，其中V和E分別表示節(jié)點集合和鏈路集合。N為網(wǎng)絡節(jié)點總數(shù)，總邊數(shù)為M。令U為N(N?1)/2個節(jié)點對組成的全集。U-E則是網(wǎng)絡中所有不存在/缺少的鏈接的集合。鏈接預測的目的就是從集合U-E中找出缺失的鏈接。給定一種鏈路預測方法，該方法為每對沒有連邊的節(jié)點對(x,y)賦予一個分數(shù)值Sxy。這個分數(shù)值可以理解為一種接近性，它與兩節(jié)點的鏈接概率正相關。即所有不存在的鏈接根據(jù)其分數(shù)按降序排序，分數(shù)越高的節(jié)點對表明該鏈接存在的可能性越大。

以下簡要介紹基于結(jié)構信息的典型及現(xiàn)有鏈路預測算法，包括CN[6]、JC[6]、AA[6]、Katz[6]、LP[6]和 CCLP[10]的節(jié)點相似性指標定義，它們也將用作后續(xù)實驗研究中的基準。

（1）CN指標，對于網(wǎng)絡中的節(jié)點x，定義其鄰居集合為Γ(x)，則兩個節(jié)點x和y的相似性就定義為它們共同的鄰居數(shù)。

（2）JC指標，用兩節(jié)點共同鄰居占兩節(jié)點鄰居總和的比例表示節(jié)點x和y的相似性。

（3）AA指標，被視為優(yōu)化的CN指標，將不同的權重分配給該公共鄰居集合中的不同節(jié)點，每個節(jié)點的權重等于該節(jié)點的度的對數(shù)分之一。

（4）Katz指標，基于網(wǎng)絡全局結(jié)構的預測方法之一，考慮了網(wǎng)絡的所有路徑，其定義為：

其中，β>0為控制權重的可調(diào)參數(shù)；表示連接節(jié)點x和y的路徑中長度為l的路徑數(shù)。

（5）LP指標，該指標通過利用節(jié)點x和y之間具有長度為2和3的不同路徑的數(shù)量的信息，來表征節(jié)點之間的相似性。

其中，A為鄰接矩陣；ε為自由參數(shù)。

（6）CCLP指標，將共同鄰居及其鄰居形成的三角形這一信息，以共同鄰居節(jié)點的聚類系數(shù)表現(xiàn)出來，定義節(jié)點x和y的相似性為共同鄰居節(jié)點的聚類系數(shù)之和，即：

式中，tz是通過節(jié)點z的三角形的數(shù)量，kz是z的度。

3.2 社區(qū)發(fā)現(xiàn)算法

本文采用NIBLPA（a node influence based label propagation algorithm）算法[21]進行社區(qū)發(fā)現(xiàn)，該算法是對LPA（label propagation algorithm）算法[22]的改進，通過在多個標簽被最大節(jié)點數(shù)所包含時，改進標簽更新的節(jié)點順序和標簽選擇機制，提高了LPA的性能，描述如算法1。

算法1NIBLPA算法

輸入：數(shù)據(jù)集網(wǎng)絡G(V,E)。

輸出：社區(qū)劃分的結(jié)果。

（1）初始化：為網(wǎng)絡各節(jié)點分配唯一的標簽，Ci(0)=i。

（2）計算每個節(jié)點的節(jié)點影響值，并按節(jié)點重要性的降序排列節(jié)點，將結(jié)果存儲在向量X中。

（3）迭代標簽傳播：

①設置t=1。

②對任意屬于X的節(jié)點vi,令Ci(t)=f(Ci1(t),…,Cim(t),Ci(m+1)(t-1),...,Cik(t-1))，其中vi1,vi2,...,vim為vi此次迭代中已更新的鄰居節(jié)點，vi(m+1),...,vik為尚未更新的鄰居節(jié)點。函數(shù)f返回其鄰居節(jié)點擁有最多的標簽，當出現(xiàn)次數(shù)最多的標簽不止一個時，重新計算標簽重要度，選擇最大值標簽分配給vi。

③若每個節(jié)點的標簽不再改變，則停止算法，否則，設置t=t+1，返回步驟②。

（4）社區(qū)劃分：將所有擁有共同標簽的節(jié)點分配到同一社區(qū)中，標簽的類型表示社區(qū)的數(shù)量。

該算法的優(yōu)勢在于：首先，保持了原有LPA[22]算法的效率；其次，避免了LPA[22]算法標簽傳播的完全隨機性，社區(qū)檢測結(jié)果更為穩(wěn)定；最后，較之于其他代表性算法，其性能較好。

3.3 貝葉斯網(wǎng)絡及期望最大化算法

貝葉斯網(wǎng)絡（Bayesian network，BN）又稱信度網(wǎng)絡，是Bayes方法的擴展，適用于表達和分析不確定性和概率性的事件。一個貝葉斯網(wǎng)絡由代表變量節(jié)點及連接這些節(jié)點有向邊構成，是一個有向無環(huán)圖（directed acyclic graph，DAG）。節(jié)點代表隨機變量，節(jié)點間的有向邊代表了節(jié)點間的互相關系（由父節(jié)點指向其子節(jié)點），用條件概率表達關系強度，沒有父節(jié)點的用先驗概率進行信息表達。由于貝葉斯網(wǎng)絡是概率預測的良好選擇，且是一個用于捕獲變量之間的依賴關系的強大且易于理解的模型，因此選擇它來預測潛在鏈接的概率。

期望最大化（expectation-maximization，EM）算法包括期望化步驟（E步驟）和最大化步驟（M步驟）兩個步驟，是一個在已知部分相關變量的情況下，估計未知變量的迭代技術，可用于貝葉斯網(wǎng)絡的參數(shù)學習。給定數(shù)據(jù)集D，定義θ的似然為給定模型參數(shù)θ時數(shù)據(jù)集D的條件概率，表示為P(D|θ)。由于n個點xj中的每一個都與X獨立同分布，θ的似然為式（8），其對數(shù)似然函數(shù)如式（9）。

EM算法即用來找針對參數(shù)θ的最大似然估計。由于每一個類都建模為一個多元正態(tài)分布，因此給定xj時，在E步驟利用貝葉斯定理計算類后驗概率P(Ci|xj)如式（10），其中fi(xj)是屬性xj屬于類Ci的概率密度，P(Ci|xj)可看作點xj在類Ci中的權值或貢獻。接下來，在M步驟中，EM使用P(Ci|xj)重新估計θ。M步上找到的參數(shù)估計值被用于下一個E步計算中，交替進行此過程直到收斂。

3.4 評價指標

本文采用兩種廣泛使用的鏈路預測評價指標AUC[23]（area under the receiver operating characteristic curve）和精確度[24]（precision）來評估預測算法的有效性。

AUC是指ROC曲線下的面積，其基本思想是，在測試集中可以觀察到的鏈接的分數(shù)高于不存在的鏈接。每次隨機從測試集和不存在的邊中各選一條，若測試集中的邊的分數(shù)值大于不存在的邊的分數(shù)，則加1分；若相等，加0.5分，這樣獨立比較n次，如果有n′次測試集中的邊的分數(shù)值大于不存在的邊的分數(shù)值，有n″次兩分數(shù)值相等，則AUC定義為：

精確度定義為在前L個預測邊中被預測準確的比例。如果有m個預測準確，即根據(jù)出現(xiàn)連接的可能性從大到小排列，排在前L的邊中有m個在測試集中，則Precision為：

對于給定的L，Precision越大預測越準確。若兩算法的AUC差不多，Precision越大的算法，效果越好。

4 基于集體影響和邊聚類信息的鏈路預測算法

4.1 集體影響

集體影響（collective influence，CI）算法[25]最初是為了解決滲透模型中的最優(yōu)影響問題而提出來的一種優(yōu)化算法。

考慮N個節(jié)點，M條邊的網(wǎng)絡，用向量n=(N1,N2,…,Nn)來表示網(wǎng)絡中去除（Ni=0，影響者）或保留(Ni=1)哪個節(jié)點，q=1-sum(Ni=1)/N表示去除的節(jié)點占總節(jié)點的比例。參數(shù)vi→j表示節(jié)點i屬于不包含節(jié)點j的修正網(wǎng)絡中的最大連通分量的概率，其中i→j代表從i到j的鏈接。那么給定q的最優(yōu)影響問題可以表達為找到最小化線性算子W的最大特征值λ(n;q),這里W是在2M×2M有限邊上的定義，表示為：

雖然極端優(yōu)化（extremal optimization，EO）方法可以通過最小化多體系統(tǒng)的能量來解決此問題，但EO在大型網(wǎng)絡中無法實現(xiàn)最佳，因此提出了可擴展的CI算法。定義Ball(i,l)為圍繞節(jié)點i,且屬于半徑（最短路徑）為l的球內(nèi)的節(jié)點集合，?Ball(i,l)為該球的邊界，那么節(jié)點i在l層所獲得的集體影響強度，即CI值為：

其中，ki是節(jié)點i的度；l是預定義的不超過有限網(wǎng)絡的網(wǎng)絡直徑的非負整數(shù)。

CI算法通過最大限度地提高網(wǎng)絡中多個傳播者的集體影響力來最小化節(jié)點集，從而實現(xiàn)在最佳滲透中對網(wǎng)絡的分段,其性能隨著l的增加而提高。關于CI算法的有效性和可擴展性，文獻[25-26]也給出了實驗證明?？紤]到最佳滲透問題的主要任務就是找出破壞網(wǎng)絡最大連通分量的最小的節(jié)點集，即對網(wǎng)絡全局連接至關重要的最小節(jié)點集。因此，集體影響算法也可被視為衡量節(jié)點影響力或者重要性的一個有效指標。因此本文選擇以節(jié)點的CI值，作為鏈路相似性計算的因素之一。這里主要利用了CI算法的兩點優(yōu)勢：首先，對于l≥1，CI算法考慮了l層的鄰域節(jié)點和種子節(jié)點間的相互作用；其次，它也是一種易于實現(xiàn)的算法，因為它只需要半徑為l的球內(nèi)的局部拓撲結(jié)構，而不是整個網(wǎng)絡結(jié)構，與本文基于網(wǎng)絡局部信息預測的研究一致。因為本文只考慮種子節(jié)點的共同鄰居節(jié)點及其鄰域信息，所以計算節(jié)點的CI值時，l統(tǒng)一設為1。

4.2 邊聚類信息

在大多數(shù)情況下，當提到聚類信息時，通?？紤]節(jié)點聚類系數(shù)。LNBCN（local na?ve Bayes common neighbor）[27]指標是局部貝葉斯模型的擴展，其最終表達式表明節(jié)點聚類系數(shù)在估計共同鄰居的貢獻方面起著重要作用。CCLP[10]指標簡單地描述了共同鄰居節(jié)點的聚類系數(shù)在CN指標的框架下對相似性的貢獻。雖然這些方法是有效的，但節(jié)點聚類系數(shù)對于每個預測節(jié)點對來說不是局部的。從整個網(wǎng)絡的角度來看，這是一個局部的措施，但是對于不同的預測節(jié)點對，它是相同的。這個因素可能會限制預測器的性能，因為一個共同鄰居節(jié)點應該在不同的局部網(wǎng)絡環(huán)境中攜帶著對應的局部聚類信息。

因此，考慮到邊能夠帶來更多的局部或功能信息，本文將焦點從節(jié)點轉(zhuǎn)移到邊上，利用與預測節(jié)點對的局部網(wǎng)絡密切相關的邊聚類信息（edge clustering information），通過將其融合到相似性度量指標中，來驗證邊聚類信息在預測缺失鏈路方面的作用。邊聚類系數(shù)[3]的定義如下：

其中，CN(x,z)表示穿過鏈路(x,z)的三角形的數(shù)量或節(jié)點x和z之間的共同鄰居數(shù)；kx表示節(jié)點x的度。該比率也可解釋為節(jié)點x對節(jié)點z的聚類系數(shù)的接受程度。

由于三元閉包作為網(wǎng)絡最基本的局部結(jié)構和重要的鏈接生成機制，具有結(jié)構平衡和穩(wěn)定的特征。因此這里只考慮預測節(jié)點對的端節(jié)點與共同鄰居節(jié)點所組成的邊的聚類能力，實現(xiàn)隱式地挖掘閉包結(jié)構所攜帶的局部信息，則上述公式可簡化如式（16）：

融合節(jié)點的集體影響和邊的聚類系數(shù)，本文定義新的鏈路相似性算法CELP，具體描述如算法2。其相似性計算指標為式（17），進一步化簡得到式（18）。

在式（17）中，相乘因子的第一個分量定義為由公共鄰居節(jié)點z與端節(jié)點x（或y）的集體影響形成的節(jié)點集體影響占比，該值和邊聚類系數(shù)的乘法可以理解為一條預測鏈路的端節(jié)點的共同鄰居節(jié)點的局部信息貢獻量。因此，CELP指標，可以認為是公共鄰居節(jié)點z在當前局部網(wǎng)絡中對節(jié)點x和節(jié)點y之間形成鏈路的信息貢獻之和。從以往的研究可知，節(jié)點和鏈接是研究復雜網(wǎng)絡的兩個重要角度。本文CELP算法融合節(jié)點的集體影響以及邊聚類信息，充分挖掘了公共節(jié)點本身及其連邊形成的局部網(wǎng)絡結(jié)構對預測鏈路形成的價值，具有明顯的優(yōu)勢。

算法2CELP算法

輸入：數(shù)據(jù)集Dataset,訓練集比例ratioTrain。

輸出：算法的AUC和precision結(jié)果。

（1）讀入數(shù)據(jù)Dataset，生成鄰接矩陣Net。

（2）劃分數(shù)據(jù)集：根據(jù)輸入的訓練集比例ratioTrain，將Net劃分為訓練集train和測試集test。

（3）記錄節(jié)點信息：統(tǒng)計train中節(jié)點i的鄰居節(jié)點和其度，分別表示為N(i)和D(i)。

（4）CI計算：根據(jù)式（14）計算當l=1時，每個節(jié)點i的CIl(i)。

（5）邊聚類系數(shù)計算：根據(jù)式（16）計算任意點對(x,y)間的邊聚類系數(shù)ECCx,y。

（6）鏈路相似性計算：利用步驟（3）到步驟（5）的實驗結(jié)果，根據(jù)式（18）計算未知鏈路(x,y)相似性Sxy。

（7）結(jié)果輸出：對相似性Sxy從大到小排序，再計算該算法的AUC和Precision。

用一個簡單的例子來說明本文算法的思想如圖1。首先根據(jù)式（14）計算種子節(jié)點（預測邊的端節(jié)點）l=1時的CI值以及公共鄰居節(jié)點對種子節(jié)點影響力的占比，然后重點關注種子節(jié)點和共同鄰居節(jié)點之間的鏈接的聚類系數(shù)。例如，對于共同鄰居節(jié)點z，分別考慮鏈路(x,z)和(y,z)。鏈路(x,z)具有通過共同鄰居節(jié)點z將節(jié)點y聚類到節(jié)點x和z所在三角形中的概率，反之亦然。

Fig.1 Simple network to illustrate CELP algorithm圖1 CELP算法思想的簡單示例圖

為了進一步肯定集體影響和邊聚類信息在鏈路預測中的作用以及增強CELP算法的適應性，對CELP進行改進，設計出標簽網(wǎng)絡的鏈路相似性算法CELP*，如算法3。該算法的理論依據(jù)為：第一，相比于社區(qū)間節(jié)點，社區(qū)內(nèi)的節(jié)點更傾向于建立鏈接。第二，兩節(jié)點的共同社區(qū)越多，二者的相似性越高，對鏈接建立的貢獻越大。第三，社區(qū)/群集結(jié)構可以提高鏈路預測精度的性能[11-12]。首先通過社區(qū)劃分算法NIBLPA[21]，將網(wǎng)絡節(jié)點劃分若干個社區(qū)，統(tǒng)計每個節(jié)點x的社區(qū)集，記為C(x)；其次，計算任意兩個節(jié)點x和y的社區(qū)相關性CRxy，定義為節(jié)點x和節(jié)點y的屬于同一社區(qū)的概率，如式（19），并將相關性矩陣記為CR；最后，設計貝葉斯網(wǎng)絡如圖2，包含CELP算法計算的任意鏈路(x,y)相似性S，其社區(qū)相關性CR，最終決策R三個因子，其中R=1，表示連接對應于R1，否則R=0，表示不連接定義為R0。由貝葉斯定理計算CR和S共同作用下的鏈路存在概率如式（20），并按照條件獨立性假設進一步將其改寫為式（21）。

Fig.2 Bayesian network diagram of link prediction圖2 鏈路預測的貝葉斯網(wǎng)絡圖

算法3CELP*算法

輸入：數(shù)據(jù)集Dataset,訓練集比例ratioTrain。

輸出：算法的AUC和Precision結(jié)果。

（1）讀入數(shù)據(jù)Dataset，生成鄰接矩陣Net。

（2）劃分數(shù)據(jù)集：根據(jù)輸入的訓練集比例ratioTrain，將Net劃分為訓練集train和測試集test。

（3）劃分社區(qū)：利用NIBLPA算法對train進行社區(qū)劃分，記錄每個節(jié)點x的社區(qū)集為C(x)。

（4）社區(qū)相關性計算：根據(jù)式（19）計算社區(qū)關聯(lián)性矩陣CR。

（5）記錄節(jié)點信息：統(tǒng)計train中節(jié)點i的鄰居節(jié)點和其度，分別表示為N(i)和D(i)。

（6）CI計算：根據(jù)式（14）計算當l=1時，每個節(jié)點i的CIl(i)。

（7）邊聚類系數(shù)計算：根據(jù)式（16）計算任意點對(x,y)間的邊聚類系數(shù)ECCx,y。

（8）鏈路相似性計算：利用步驟（3）到步驟（7）的實驗結(jié)果，根據(jù)式（18）得未知鏈路(x,y)端節(jié)點相似概率Sxy。

（9）參數(shù)學習：利用train以及步驟（4）和步驟（8）的結(jié)果學習貝葉斯網(wǎng)絡的參數(shù)概率。

（10）鏈路存在概率計算：根據(jù)式（21）計算各潛在鏈路的存在概率。

（11）結(jié)果輸出：將所有潛在鏈接i的鏈路相似性Pi從大到小排序，計算該算法的AUC和Precision。

貝葉斯網(wǎng)絡概率計算的關鍵是學習因子S,CR及R的分布。這一過程，需要根據(jù)式（18）和式（19）計算當前訓練集中潛在鏈接i的Si及CRi,分別表示該i的端節(jié)點的相似概率及同屬一個社區(qū)的概率；同時根據(jù)訓練集ET可以得到R1和R0的先驗概率如式（22）和式（23）。然后，利用EM算法解決參數(shù)P(CRi|R1)和P(Si|R1)的學習。最后，根據(jù)計算的各個子概率，完成鏈路存在概率Pi(R1|CRi，Si)的計算。算法CELP*的架構圖如圖3。

5 實驗和分析

為了不破壞原始網(wǎng)絡的結(jié)構，設置10%的鏈接作為測試鏈接，即采用十字交叉驗證法。AUC中的采樣次數(shù)n=10 000，Precision排列表的長度選擇L=20、40、60、80、100和50、100、150、200、250，分別對應網(wǎng)絡鏈路數(shù)小于1 000和大于1 000的數(shù)據(jù)集，實驗的最終結(jié)果是各網(wǎng)絡的100次獨立運行的平均值。

5.1 實驗平臺

硬件環(huán)境為2.80 GHz Intel?CoreTMi7-7700HQ CPU，8 GB RAM，操作系統(tǒng)為Windows,開發(fā)環(huán)境為Matlab 2016a。

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

本文選擇對不同規(guī)模不同領域的六個真實數(shù)據(jù)集進行了測試，包括美式足球比賽的網(wǎng)絡Football[28]、線蟲的神經(jīng)網(wǎng)絡Celegans[29]、蛋白質(zhì)相互作用網(wǎng)絡Yeast[30]、美國政治博客之間的超鏈接網(wǎng)絡political blogs(PB)[31]、機場之間的定向航班網(wǎng)絡USA airports(USAir)[32]和社交網(wǎng)絡 Facebook[33]。

詳細信息如表1所示（其中N表示節(jié)點數(shù)，M表示邊數(shù)，

Table 1 Basic topological features of datasets表1 數(shù)據(jù)集的基本拓撲特征

5.3 結(jié)果分析

本文CELP及CELP*算法與對比的鏈路預測相似性算法包括CN、JC、AA、Katz、LP和CCLP在表1各數(shù)據(jù)集上的AUC實驗結(jié)果如表2，對應于圖4。不同L取值對應的Precision實驗結(jié)果如圖5。

Fig.3 Algorithm architecture diagram of CELP*圖3 CELP*的算法架構圖

Table 2 AUC comparison of CELP and CELP*with other link prediction algorithms表2 CELP及CELP*與其他鏈路預測算法的AUC比較

Fig.4 AUCvalues of CELP and CELP*and other comparison methods圖4 CELP及CELP*和其他比較方法的AUC值

根據(jù)六個網(wǎng)絡數(shù)據(jù)集的實驗結(jié)果，可以看出：首先，由于各網(wǎng)絡的拓撲結(jié)構不同，各算法在不同數(shù)據(jù)集上的預測性能有所差異。如Katz算法在Celegans數(shù)據(jù)集上取得了和其他算法相近的AUC值，而在USAir數(shù)據(jù)集的AUC值僅為14.45%，相比其他算法的結(jié)果差了將近8倍。其次，根據(jù)表2和圖4，可以看出本文CELP算法以及加入了社區(qū)屬性的CELP*算法在各數(shù)據(jù)集上能夠取得和其他算法同水平甚至更高水平的AUC值，在一定程度上肯定了本文算法的可行性和有效性。再次，圖5的精確度結(jié)果顯示，CELP及CELP*在六個網(wǎng)絡上的總體表現(xiàn)優(yōu)于其他算法，隨著L的變化，Precision值均處于領先位置，一方面說明了二者預測的穩(wěn)定性，另一方面表明了邊聚類信息在預測缺失鏈路方面的研究價值。如CELP在Football數(shù)據(jù)集上的平均精確度比CCLP算法提高4.48%，比經(jīng)典CN算法提高了33.3%，在Yeast數(shù)據(jù)集上的平均精確度比CCLP算法提高24.31%，比Katz及JC算法分別提高了10.81%、75.25%。同時，可以看出考慮社區(qū)的CELP*算法相比CELP算法，精度有了進一步的提高，在數(shù)據(jù)集Football、Celegans和PB上表現(xiàn)得相對明顯。最后，通過對比表2和圖5還發(fā)現(xiàn)，評估各算法預測性能的指標AUC和Precision并不總是同步。如經(jīng)典的JC算法，雖然在六個數(shù)據(jù)集上都能取得較高水平的AUC值，卻在多個數(shù)據(jù)集上的Precision值很低，如Football、Yeast和Celegans；LP算法在PB數(shù)據(jù)集上的AUC值雖然最大，Precision值卻不及CELP和Katz。

5.4 時間復雜度分析

運算效率是評價鏈路預測算法的重要因素，大多算法是在運算效率和預測效果之間取得一個平衡或謀求某一方面的促進與提升。對于CN算法來說，計算節(jié)點對的共同鄰居的時間復雜度為O(＜k>)。因此計算所有節(jié)點的相似度值的時間復雜度為O(N2＜k>)。AA與JC兩種算法與CN算法計算過程相同，時間復雜度也相同。局部路徑指標LP算法的時間復雜度為O(N＜k>3)?；谌值念A測算法Katz的時間復雜度為O(N3)?；诠?jié)點聚類信息的預測算法CCLP，計算每個節(jié)點的聚類系數(shù)時間復雜度為O(N)，最終分配相似性分數(shù)的時間復雜度為O(N2＜k>2)。本文算法CELP，計算單個節(jié)點CI值的時間復雜度為O(1)，計算所有節(jié)點CI值的時間復雜度為O(N)，計算所有邊聚類系數(shù)的時間復雜度為O(N2＜k>)，預測過程時間復雜度為O(N2)，因此CELP算法的最終時間復雜度為O(N2＜k>)。與其他算法相比，CELP算法在保持時間復雜度較低水平的同時獲得了精確度上的提升。CELP*相比CELP而言，增加了NIBLPA算法進行社區(qū)劃分以及EM算法學習參數(shù)過程，兩過程的時間復雜度[21]分別為 2×O(N)+(2×t+1)×O(M)+O(NlbN)和O(t(ca3+ca2N)),其中t為迭代次數(shù)，c為類的個數(shù)，a為屬性個數(shù)。本文c=2,a=2,故CELP*時間復雜度為2×O(N)+(2×t+1)×O(M)+O(NlbN)+O(N2＜k>+O(tN))。

Fig.5 Precisionof CELP and CELP*and other comparison methods圖5 CELP及CELP＊和其他比較方法的Precision值

6 結(jié)束語

鏈路預測是復雜網(wǎng)絡中的重要研究領域，具有很強的應用前景。本文提出了基于集體影響和邊聚類信息的鏈路預測算法CELP，前者主要是對l=1層的鄰域節(jié)點和種子節(jié)點間的相互作用進行衡量，提取網(wǎng)絡的點信息；后者則根據(jù)共同鄰居節(jié)點在不同的局部網(wǎng)絡環(huán)境中發(fā)揮作用的差異，實現(xiàn)網(wǎng)絡邊信息的利用，二者的融合充分挖掘了網(wǎng)絡拓撲對鏈路相似性的貢獻。另外，結(jié)合網(wǎng)絡的社區(qū)信息，設計出擴展算法CELP*，進一步提升了CELP算法的精度，也使得該算法在標簽網(wǎng)絡同樣能發(fā)揮作用。

該研究的主要貢獻可以歸結(jié)為以下四方面：

（1）將集體影響算法的思想引入到鏈路預測的研究，把節(jié)點的CI值作為鏈路相似性度量的因素之一。

（2）驗證了邊聚類信息在預測缺失鏈路方面的價值，肯定了不同預測節(jié)點對的局部網(wǎng)絡環(huán)境的差異。

（3）提出了適應性更強的擴展算法CELP*，用于標簽網(wǎng)絡及無標簽網(wǎng)絡的鏈路預測，證明了社區(qū)結(jié)構對預測算法精度的提升。

（4）不同領域不同規(guī)模的網(wǎng)絡數(shù)據(jù)集上的實驗結(jié)果表明：與其他算法相比，綜合了點和邊信息的本文算法，在鏈路預測問題上具有相對的競爭力，對該領域的研究具有一定程度上的參考意義。

下一步的工作，則是進一步研究CI算法最短路徑的取值對預測算法效果的影響以及本文算法在其他類型網(wǎng)絡的技術實現(xiàn)。