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

楊曉翠，宋甲秀，張曦煌

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

1 引言

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

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

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

2 相關(guān)工作

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

基于網(wǎng)絡(luò)局部結(jié)構(gòu)的預(yù)測算法只利用節(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)絡(luò)提出了用H指標(biāo)[7]代替度，以加權(quán)方式有效衡量引文重要性的同時，增強了Salton、Sorenson和AA這三種經(jīng)典鏈路預(yù)測算法，實驗結(jié)果表明該方法在引文網(wǎng)絡(luò)表現(xiàn)良好。高等人[8]提出了一種基于三元閉包的節(jié)點相似性鏈路預(yù)測算法，通過計算出每個節(jié)點在網(wǎng)絡(luò)中所占三元閉包的權(quán)重，并將該權(quán)重用于節(jié)點相似性指標(biāo)中，提高了預(yù)測精度，但卻是以O(shè)(N3)的時間復(fù)雜度為代價。

相對于局部結(jié)構(gòu)的預(yù)測算法,全局結(jié)構(gòu)相似性算法則考慮了整個網(wǎng)絡(luò)的結(jié)構(gòu)，包括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]等。基于準(zhǔn)局部結(jié)構(gòu)的預(yù)測算法，無需全局網(wǎng)絡(luò)拓?fù)湫畔ⅲ抢帽染植恐笜?biāo)更多的信息，如 LP(local path)[6]、LRW(local random walk)和 SRW(superposed random walk)[6]。近期基于準(zhǔn)局部結(jié)構(gòu)的研究成果有，孫等人將節(jié)點的度和鄰居信息相結(jié)合，提出了LAS(local affinity structure)[9]算法，來顯示節(jié)點對和其共同鄰居間的親密關(guān)系,并通過實驗說明了該算法的可行性，但該方法依舊只是停留在節(jié)點信息的利用上，并未考慮鏈路對于相似性的貢獻(xiàn)。武等人直接根據(jù)節(jié)點聚類系數(shù)設(shè)計了一個新的方法，稱為基于聚類系數(shù)的鏈路預(yù)測算法（clustering coefficient for link prediction，CCLP）[10]。實驗表明，具有節(jié)點聚類系數(shù)的簡單的基于共同鄰居的方法在預(yù)測缺失鏈接方面具有很好的有效性，但其仍然采用通用估計，同樣沒有考慮特定預(yù)測節(jié)點對的局部網(wǎng)絡(luò)環(huán)境。

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

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

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

3 基本算法

3.1 問題描述及基準(zhǔn)算法介紹

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

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

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

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

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

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

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

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

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

（6）CCLP指標(biāo)，將共同鄰居及其鄰居形成的三角形這一信息，以共同鄰居節(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]進(jìn)行社區(qū)發(fā)現(xiàn)，該算法是對LPA（label propagation algorithm）算法[22]的改進(jìn)，通過在多個標(biāo)簽被最大節(jié)點數(shù)所包含時，改進(jìn)標(biāo)簽更新的節(jié)點順序和標(biāo)簽選擇機制，提高了LPA的性能，描述如算法1。

算法1NIBLPA算法

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

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

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

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

（3）迭代標(biāo)簽傳播：

①設(shè)置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é)點擁有最多的標(biāo)簽，當(dāng)出現(xiàn)次數(shù)最多的標(biāo)簽不止一個時，重新計算標(biāo)簽重要度，選擇最大值標(biāo)簽分配給vi。

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

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

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

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

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

期望最大化（expectation-maximization，EM）算法包括期望化步驟（E步驟）和最大化步驟（M步驟）兩個步驟，是一個在已知部分相關(guān)變量的情況下，估計未知變量的迭代技術(shù)，可用于貝葉斯網(wǎng)絡(luò)的參數(shù)學(xué)習(xí)。給定數(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中的權(quán)值或貢獻(xiàn)。接下來，在M步驟中，EM使用P(Ci|xj)重新估計θ。M步上找到的參數(shù)估計值被用于下一個E步計算中，交替進(jìn)行此過程直到收斂。

3.4 評價指標(biāo)

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

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

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

對于給定的L，Precision越大預(yù)測越準(zhǔn)確。若兩算法的AUC差不多，Precision越大的算法，效果越好。

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

4.1 集體影響

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

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

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

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

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

4.2 邊聚類信息

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

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

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

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

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

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

算法2CELP算法

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

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

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

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

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

（4）CI計算：根據(jù)式（14）計算當(dāng)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é)點（預(yù)測邊的端節(jié)點）l=1時的CI值以及公共鄰居節(jié)點對種子節(jié)點影響力的占比，然后重點關(guān)注種子節(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算法思想的簡單示例圖

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

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

算法3CELP*算法

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

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

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

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

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

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

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

（6）CI計算：根據(jù)式（14）計算當(dāng)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ù)學(xué)習(xí)：利用train以及步驟（4）和步驟（8）的結(jié)果學(xué)習(xí)貝葉斯網(wǎng)絡(luò)的參數(shù)概率。

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

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

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

5 實驗和分析

為了不破壞原始網(wǎng)絡(luò)的結(jié)構(gòu)，設(shè)置10%的鏈接作為測試鏈接，即采用十字交叉驗證法。AUC中的采樣次數(shù)n=10 000，Precision排列表的長度選擇L=20、40、60、80、100和50、100、150、200、250，分別對應(yīng)網(wǎng)絡(luò)鏈路數(shù)小于1 000和大于1 000的數(shù)據(jù)集，實驗的最終結(jié)果是各網(wǎng)絡(luò)的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ī)模不同領(lǐng)域的六個真實數(shù)據(jù)集進(jìn)行了測試，包括美式足球比賽的網(wǎng)絡(luò)Football[28]、線蟲的神經(jīng)網(wǎng)絡(luò)Celegans[29]、蛋白質(zhì)相互作用網(wǎng)絡(luò)Yeast[30]、美國政治博客之間的超鏈接網(wǎng)絡(luò)political blogs(PB)[31]、機場之間的定向航班網(wǎng)絡(luò)USA airports(USAir)[32]和社交網(wǎng)絡(luò) Facebook[33]。

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

Table 1 Basic topological features of datasets表1 數(shù)據(jù)集的基本拓?fù)涮卣?/p>

5.3 結(jié)果分析

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

Fig.3 Algorithm architecture diagram of CELP*圖3 CELP*的算法架構(gòu)圖

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

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

根據(jù)六個網(wǎng)絡(luò)數(shù)據(jù)集的實驗結(jié)果，可以看出：首先，由于各網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不同，各算法在不同數(shù)據(jù)集上的預(yù)測性能有所差異。如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)絡(luò)上的總體表現(xiàn)優(yōu)于其他算法，隨著L的變化，Precision值均處于領(lǐng)先位置，一方面說明了二者預(yù)測的穩(wěn)定性，另一方面表明了邊聚類信息在預(yù)測缺失鏈路方面的研究價值。如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算法，精度有了進(jìn)一步的提高，在數(shù)據(jù)集Football、Celegans和PB上表現(xiàn)得相對明顯。最后，通過對比表2和圖5還發(fā)現(xiàn)，評估各算法預(yù)測性能的指標(biāo)AUC和Precision并不總是同步。如經(jīng)典的JC算法，雖然在六個數(shù)據(jù)集上都能取得較高水平的AUC值，卻在多個數(shù)據(jù)集上的Precision值很低，如Football、Yeast和Celegans；LP算法在PB數(shù)據(jù)集上的AUC值雖然最大，Precision值卻不及CELP和Katz。

5.4 時間復(fù)雜度分析

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

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

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

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

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

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

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

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