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

楊曉翠，宋甲秀，張曦煌

江南大學 物聯網工程學院，江蘇 無錫 214122

1 引言

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

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

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

2 相關工作

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

基于網絡局部結構的預測算法只利用節點的鄰居信息，以 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等人針對引用網絡提出了用H指標[7]代替度，以加權方式有效衡量引文重要性的同時，增強了Salton、Sorenson和AA這三種經典鏈路預測算法，實驗結果表明該方法在引文網絡表現良好。高等人[8]提出了一種基于三元閉包的節點相似性鏈路預測算法，通過計算出每個節點在網絡中所占三元閉包的權重，并將該權重用于節點相似性指標中，提高了預測精度，但卻是以O(N3)的時間復雜度為代價。

相對于局部結構的預測算法,全局結構相似性算法則考慮了整個網絡的結構，包括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]等。基于準局部結構的預測算法，無需全局網絡拓撲信息，而是利用比局部指標更多的信息，如 LP(local path)[6]、LRW(local random walk)和 SRW(superposed random walk)[6]。近期基于準局部結構的研究成果有，孫等人將節點的度和鄰居信息相結合，提出了LAS(local affinity structure)[9]算法，來顯示節點對和其共同鄰居間的親密關系,并通過實驗說明了該算法的可行性，但該方法依舊只是停留在節點信息的利用上，并未考慮鏈路對于相似性的貢獻。武等人直接根據節點聚類系數設計了一個新的方法，稱為基于聚類系數的鏈路預測算法（clustering coefficient for link prediction，CCLP）[10]。實驗表明，具有節點聚類系數的簡單的基于共同鄰居的方法在預測缺失鏈接方面具有很好的有效性，但其仍然采用通用估計，同樣沒有考慮特定預測節點對的局部網絡環境。

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

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

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

3 基本算法

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

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

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

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

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

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

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

其中，β>0為控制權重的可調參數；表示連接節點x和y的路徑中長度為l的路徑數。

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

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

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

式中，tz是通過節點z的三角形的數量，kz是z的度。

3.2 社區發現算法

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

算法1NIBLPA算法

輸入：數據集網絡G(V,E)。

輸出：社區劃分的結果。

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

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

（3）迭代標簽傳播：

①設置t=1。

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

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

（4）社區劃分：將所有擁有共同標簽的節點分配到同一社區中，標簽的類型表示社區的數量。

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

3.3 貝葉斯網絡及期望最大化算法

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

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

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

3.4 評價指標

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

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

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

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

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

4.1 集體影響

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

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

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

其中，ki是節點i的度；l是預定義的不超過有限網絡的網絡直徑的非負整數。

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

4.2 邊聚類信息

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

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

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

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

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

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

算法2CELP算法

輸入：數據集Dataset,訓練集比例ratioTrain。

輸出：算法的AUC和precision結果。

（1）讀入數據Dataset，生成鄰接矩陣Net。

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

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

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

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

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

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

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

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

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

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

算法3CELP*算法

輸入：數據集Dataset,訓練集比例ratioTrain。

輸出：算法的AUC和Precision結果。

（1）讀入數據Dataset，生成鄰接矩陣Net。

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

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

（4）社區相關性計算：根據式（19）計算社區關聯性矩陣CR。

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

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

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

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

（9）參數學習：利用train以及步驟（4）和步驟（8）的結果學習貝葉斯網絡的參數概率。

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

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

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

5 實驗和分析

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

5.1 實驗平臺

硬件環境為2.80 GHz Intel?CoreTMi7-7700HQ CPU，8 GB RAM，操作系統為Windows,開發環境為Matlab 2016a。

5.2 數據集

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

詳細信息如表1所示（其中N表示節點數，M表示邊數，

Table 1 Basic topological features of datasets表1 數據集的基本拓撲特征

5.3 結果分析

本文CELP及CELP*算法與對比的鏈路預測相似性算法包括CN、JC、AA、Katz、LP和CCLP在表1各數據集上的AUC實驗結果如表2，對應于圖4。不同L取值對應的Precision實驗結果如圖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值

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

5.4 時間復雜度分析

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

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

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

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

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

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

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

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