伍杰華，程智鋒

(1.廣東工貿職業(yè)技術學院 計算機與信息工程學院，廣東 廣州 510510； 2.廣東工貿職業(yè)技術學院 教育部虛擬現(xiàn)實信息化協(xié)同創(chuàng)新中心，廣東 廣州 510510)

0 引 言

信息網絡(information network)[1]是一種由實體和實體之間的關聯(lián)組成的圖結構。對信息網絡的分析和理解是數據挖掘領域的其中一個主要研究方向，該研究方向又可以分為社區(qū)發(fā)現(xiàn)[2]、影響力節(jié)點識別[3]、鏈接預測[4]等。其中，社區(qū)發(fā)現(xiàn)(community detection)[2]是一個類似聚類的算法，旨在找出網絡結構中的密集群組，使群組之間的鏈接稀疏，群組內部的鏈接緊密。該技術能夠幫助科研人員在生物信息網絡中找到功能類似的蛋白質結構[5]；影響力節(jié)點識別(influential node identification)[3]目的是發(fā)現(xiàn)網絡中最具備傳播能力的節(jié)點。該技術能夠理解和識別社交網絡和輿情網絡中謠言的傳播機制和路徑[6]，改進供應鏈網絡的物流運輸方式[7]。鏈接預測(link prediction)[4]是預測尚未產生鏈接的節(jié)點之間是否會產生關聯(lián)。社交網絡中的朋友關系推薦、交通網絡中的路線設計、生化網絡中的食物鏈分析和科研合作網絡中的科研工作者合作關系推薦等應用的實現(xiàn)均需以鏈接預測技術作為基礎[8]。由于社區(qū)發(fā)現(xiàn)和影響力節(jié)點識別兩種技術均需要對鏈接這一信息網絡結構的核心組成部分進行分析，因此本文擬針對目前許多鏈接預測指標無法有效集成局部和全局結構信息對的問題，研究3個信息網絡分析子領域之間的關聯(lián)，設計一種高效的可擴展性的鏈接預測算法。

1 相關工作和問題定義

1.1 相關工作

鏈接預測問題由來已久，但隨著其它領域工作的不斷發(fā)展，該技術也在推陳出新，其中最主要的一個研究方向的基于網絡結構的鏈接預測。比較經典的有基于局部共鄰節(jié)點結構信息的算法(也可稱為指標)((common neighbors，CN)、(adamic-adar，AA)、(preferential attachment，PA)、(resource allocation，RA)等等)[8]，基于半全局路徑或隨機游走結構的算法((local path，LP)[9]、Katz[9]、(return random walk，RRW)[10]等等)。近年來，一些工作嘗試引入局部密集結構到鏈接預測算法中，例如Wu等[11]提出了一種基于聚類系數(cluster coefficient，CC)的鏈接預測算法，該算法引入共鄰結點的聚類系數反映鏈接生成的機制。Chen等[12]把聚類系數的定義嵌入樸素貝葉斯模型中，取得更好的預測效果。此外，Wu等[13]還提出一種集成節(jié)點和鏈接聚類信息的算法(node and link clustering，NLC)，在top-L測試中取得比基準算法更好的性能。但是上述算法提取的僅僅是局部鏈接密集度信息?；谠撔畔⒍x的相似度指標盡管結構簡單、時間復雜度低，但是沒有充分引入網絡的經典密集度結構(社區(qū)結構)計算其影響力，而且不同規(guī)模社區(qū)之間存在差異性，直接把社區(qū)信息適配到相似度指標會造成信息不完整和損失。

與此同時，盡管社區(qū)反映了部分網頁的全局信息，但是相關工作表明，一些使用全局結構信息的預測算法(SPM[14]、LR[15])的效果是更優(yōu)的，但是它們運行速度慢，內存占用率高，如何在劃分社區(qū)的基礎上引入全局信息保持運行效率是其中的關鍵。近期，一些工作嘗試從影響力節(jié)點識別方法設計鏈接預測算法。相關綜述指出[3]，影響力節(jié)點識別方法目的是在網絡中找出信息傳播中產生影響范圍最大最廣的節(jié)點或者節(jié)點集合。該方法有效描述了節(jié)點在全局網絡結構中的許多動態(tài)活動，例如傳染病暴發(fā)、謠言傳播等等。這些方法為每個信息傳播過程中經過的節(jié)點賦予一個全局的影響力函數度量節(jié)點的影響力，相關工作[16]把它作為得分加入到鏈接預測相似度得分公式中，并取得較好的效果。圖1用網絡圖描述了這一問題。其中a，b是兩待預測節(jié)點，它們之間的虛線表示潛在需要預測的鏈接，實線表示存在鏈接。該結構劃分成左右兩個社區(qū)A和B，節(jié)點顏色的深淺表示該節(jié)點的影響力大小，顏色越深，影響力則越大。很明顯，在社區(qū)劃分狀態(tài)下不同共鄰節(jié)點的影響力是會對鏈接預測結果產生影響的。

圖1 算法結構模型

因此，本文提出一個可擴展性的融合社區(qū)發(fā)現(xiàn)和影響力節(jié)點識別兩種技術的鏈接預測算法。該算法首先提取各節(jié)點的影響力函數得分(節(jié)點影響力)，然后采用社區(qū)發(fā)現(xiàn)算法劃分社區(qū)，運用社區(qū)參與度的概念計算不同規(guī)模社區(qū)內共鄰節(jié)點對鏈接生成的影響得分(社區(qū)影響力)，最后把上述得分集成到一個統(tǒng)一的模型中。同時，還討論了不同社區(qū)發(fā)現(xiàn)算法和多個類型的影響力得分計算函數的性能。在各類型真實信息網絡的實驗結果表明，算法復雜度較低，是通用且可擴展的，同時預測的性能優(yōu)于基準算法。

1.2 問題定義

給定一個信息網絡G=(V,E,C)， 其中V和E分別是節(jié)點和鏈接的集合，C是網絡劃分成k個社區(qū)的集合，其中C={c1,c2,c3…ck},k>2， 同時ck表示第k個社區(qū)，c(i) 表示節(jié)點i所處的社區(qū)，I(i) 則表示該節(jié)點的影響力得分。此外，給定u和v兩個節(jié)點，N(u) 表示節(jié)點u的鄰接節(jié)點集合。共鄰節(jié)點則定義為u和v鄰接節(jié)點集合N(u) 和N(v) 的交集，表示為：CN(u,v)=N(u)∩N(v)。

鏈接預測的任務可描述成如下的流程：①把G按照比例r劃分成訓練集、預測集并劃分社區(qū)，計算社區(qū)影響力和節(jié)點影響力。②計算訓練集中每對節(jié)點對的相似度得分。③和預測集比較前N個相似度最大值計算評估指標，獲取預測結果。

2 算法模型

相似度表示兩節(jié)點關系的緊密程度，計算兩個潛在節(jié)點的相似度是基于網絡結構鏈接預測方法的最主要方式。大部分相似度鏈接預測方法基于局部共鄰節(jié)點構建，這是因為共鄰節(jié)點信息是影響鏈接生成最直觀的結構，例如在社交網絡中，節(jié)點u和v表示目前不存在關系的兩個用戶，鏈接表示他們之間的朋友、關注關系，共鄰節(jié)點表示和u、v均存在朋友關系的共同朋友。很明顯，兩個用戶的共同朋友越多，他們產生朋友關系的可能性就越高。因此，許多相似度算法基于共鄰節(jié)點結構展開，它們的通用表達形式為[17]

(1)

其中，ω是共鄰節(jié)點，s(u,v) 表示兩節(jié)點之間的相似度值，一般相似度值越高，u和v之間產生鏈接的可能性則越高。f(ω) 表示由共鄰節(jié)點結構屬性構成的得分函數。在許多經典相似度指標中，f(ω) 可以表示為局部的共鄰節(jié)點數目、度、度的對數和聚類系數等結構，也可以定義為隨機森林、鄰接矩陣等全局結構。

為了使得分函數更好反映網絡的局部和全局信息，在本文工作中擬保留式(1)中的f(ω) 表示局部社區(qū)影響力函數，同時添加1/g(ω) 表示全局節(jié)點影響力函數的倒數，并定義如下

(2)

需要注意的是，節(jié)點影響力得分放在了分母。這是因為在相似度得分中，共鄰節(jié)點影響力大，其對鏈接生成的影響成反比。

2.1 社區(qū)影響力函數

信息網絡拓撲結構和其表示的實體結構相似，都是由若干個節(jié)點之間的鏈接緊密的“社區(qū)”或“社團”構成。根據社區(qū)屬性可知，社區(qū)結構內部的鏈接往往比社區(qū)之間的關系要緊密。因此社區(qū)結構對于理解鏈接是如何形成是非常重要的。一些工作指出[18]，由于社區(qū)內部鏈接密度高，新鏈接傾向于在內部產生，一些工作則認為，社區(qū)之間鏈接是信息跨領域傳播的重要路徑，新鏈接也有很大概率在此產生。由圖1可見，待預測節(jié)點a，b對的共鄰節(jié)點可能在社區(qū)A，也可能在社區(qū)B，共鄰節(jié)點的鄰接節(jié)點也可能分屬不同的社區(qū)。由于社區(qū)A和社區(qū)B內部的鏈接密度不同，構建基于共鄰節(jié)點的相似度得分函數需要把該屬性考慮進去。況且兩個社區(qū)的規(guī)模也不一致，如何區(qū)別不同共鄰節(jié)點的貢獻也需要解決。

(3)

可以看出，ω的鄰接度和越大，kω(c(ω)) 的值便越大，則在計算相似度得分時它的貢獻就越大。

第二步，找到和待預測節(jié)點屬于不同社區(qū)的共鄰節(jié)點，計算其貢獻。由于共鄰節(jié)點和待預測節(jié)點不屬于相同社區(qū)，根據社區(qū)理論其鏈接相對稀疏，因此貢獻通過ω的參與系數pω(c(ω)) 來定義，其公式是

(4)

(5)

當ck≠c(ω) 時，pω(ck)=0代表共鄰節(jié)點的鄰接節(jié)點均在該節(jié)點所處社區(qū)的內部。采用單位減法的含義在于根據劃分社區(qū)的屬性，社區(qū)內部鏈接生成的概率比社區(qū)之間的要高。因此，局部的社區(qū)影響力函數為

根據差異化共鄰節(jié)點貢獻的目的，算法需要強調(增大)社區(qū)內部共鄰節(jié)點的影響同時懲罰(減少)社區(qū)外部共鄰節(jié)點的影響，同時在社區(qū)內部和社區(qū)之間的鏈接生成找到平衡。因此，后者的乘積采用負數，且共鄰節(jié)點的參與系數越大，其對相似度得分的貢獻越小。

2.2 影響力節(jié)點識別函數

盡管引入社區(qū)屬性，但是上述算法均從局部角度建立公式，并沒有考慮網絡的全局結構。作者最新的工作[16]嘗試使用影響力節(jié)點識別指標表示g(ω)， 在許多數據集上均取得了較好的效果。但是該指標缺少局部信息，因此本節(jié)結合局部社區(qū)屬性或局部密集度屬性提升預測的準確度，進一步擴展該指標。

影響力節(jié)點識別(又稱關鍵節(jié)點識別)的核心是如何度量節(jié)點的影響力，一般來說定義為該節(jié)點與網絡中的其它節(jié)點具備不同的信息傳播能力(重要性，顯著性)，用網絡的屬性結構可以表示為度、局部中心性、核度、混合度和隨機游走等等。為了驗證算法的適配性和可擴展性，本部分引入幾個新穎的、經典的影響力節(jié)點識別指標定義g(ω)， 并嵌入到鏈接預測相似度框架中。

(1)Katz向量中心性(Katz eigenvector centrality，EC)[19]。Katz是在特征向量中心性的基礎上提出的，特征向量中心性把鄰接矩陣的最大特征值的特征向量作為中心性度量值，但是不適應當圖中出現(xiàn)有向無環(huán)圖的情況，Katz在此提出了一個改進方法，即每個節(jié)點初始就有一個中心度值。節(jié)點ω的重要性g(ω) 可表示為

(6)

其中，b=1， 衰減因子c=0.5λmax，λmax是鄰接矩陣的最大特征值。

(2)PageRank(PR)[20]。PageRank是一個基于隨機游走的影響力節(jié)點識別指標。該指標是一個搜索算法，它借鑒了學術界評判學術論文重要性的通用方法——引用，通過網頁之間的鏈接關系給網頁的級別或者重要性進行排序，并把排序的結果作為搜索結果提供給用戶。隨著網絡科學研究的不斷深入，PageRank作為影響力節(jié)點識別，已經廣泛用于社交網絡關鍵用戶發(fā)現(xiàn)、航空網絡樞紐識別等多個領域。該指標ω在t時間的重要性gt(ω) 可表示為

(7)

其中，γ是阻尼系數，表示從某個節(jié)點跳轉到下一個節(jié)點的概率，一般設置為γ=0.15， (1-γ) 則表示隨機跳轉到其它節(jié)點的概率。ki表示第i個節(jié)點的入度，N為網絡總節(jié)點數，aiω表示節(jié)點ω到i有一條路徑，取值為1，如不存在則取值為0；當ki=0時，σkI,0=1。

(3)LeaderRank(LR)[21]。該指標是對PageRank的一種改進。添加了一個基礎節(jié)點ground node指向所有節(jié)點，保證每個節(jié)點的度均大于1，其依據在于鄰接度低的節(jié)點訪問基礎節(jié)點的概率比鄰接度高的節(jié)點訪問基礎節(jié)點的概率要大。該指標ω的重要性gt(ω) 可表示為

(8)

(4)ClusterRank(CR)[22]。近期，相關工作在科學家合作網絡等真實數據集上的實驗驗證了聚類系數對于節(jié)點獲取新的鄰居節(jié)點是不利的。同時它們認為在影響力節(jié)點識別問題中，聚類系數值越大，對于一個節(jié)點的影響力來說，是一個負面的因素。該指標ω的重要性g(ω) 可表示為

(9)

ccω表示節(jié)點ω的聚類系數，h(ccω) 是把聚類系數作為參數的函數，一般用指數函數h(ccω)=10-ccω表示。特別需要指出的是，g(ω) 和上一小節(jié)討論的f(ω) 均是以共鄰節(jié)點ω作為參數的函數，因此可以適配任意包含共鄰節(jié)點結構信息的特征，因此算法的相似度模型對不同的影響力節(jié)點識別函數是通用的。

2.3 可擴展性討論

2.1小節(jié)中的社區(qū)影響力函數盡管在一定程度上能夠表示共鄰節(jié)點的局部影響，但是其定義和概念也是全局的，尤其對于稀疏網絡，該影響力很難給予相似度得分貢獻。因此在本小節(jié)中探討加入更具備局部屬性的影響力得分到f(ω) 中，驗證算法的可擴展性和魯棒性。

2.3.1 局部密集度影響的可擴展性

(1)聚類系數。聚類系數是網絡局部結構中節(jié)點聚集程度的度量，其具體被定義為任何節(jié)點ω作為其中一個頂點參與形成的三角形數目tω與其最大可能參與形成的三角形數目之間的比率

(10)

如果ccω=0表示該節(jié)點沒有鄰居節(jié)點，ccω=1則表示所有鄰接節(jié)點均緊密相連。

(2)局部社區(qū)范式(local community paradigm，LCP)[23]。LCP總結了局部結構中鏈接互連的多種模式，提出了一系列結構簡單且高效的局部密集度指標，文中選取了實驗效果表現(xiàn)最好的(Cannistraci resource allocation，CRA)，其定義為

(11)

其中，γ(ω) 表示ω集合中也是u和v共鄰節(jié)點的數目。

2.3.2 不同模塊度社區(qū)影響的可擴展性

模塊度刻畫社區(qū)的緊密程度，是一種經典的衡量社區(qū)發(fā)現(xiàn)算法質量的指標。不同的模塊度和社區(qū)數目決定節(jié)點相鄰局部結構的緊密程度，也會導致不同的相似度得分。為了驗證提出模型在不同社區(qū)發(fā)現(xiàn)算法都是適用的，本小節(jié)通過綜述[24,25]介紹另外兩個經典的模塊度社區(qū)發(fā)現(xiàn)算法：

(1)F-N(Fast Newman)算法。Newman在該工作中首次定義了模塊度(Modularity)概念并提出對應的社區(qū)發(fā)現(xiàn)算法F-N。該算法的思想是：當進行社區(qū)劃分時，將結點加入它的某個鄰接節(jié)點所在的社區(qū)中，如果能夠提升當前社區(qū)結構模塊度，則進行迭代劃分，直至模塊度不再收斂為止。

(2)多尺度貪婪算法。該算法由社區(qū)發(fā)現(xiàn)領域的知名學者Erwan Le Martelot提出，該算法除了采用模塊度定義外，還使用了穩(wěn)定性(Stability)概念度量劃分的質量，然后使用一個多尺度的貪婪算法最大化模塊度和穩(wěn)定性，取得較好的劃分性能。

2.4 通用性討論

前文介紹算法主要針對無權的信息網絡建立，而在現(xiàn)實世界中，存在節(jié)點之間的鏈接強度不一的信息網絡。為了驗證算法的通用性，本小節(jié)將提出的算法拓展到加權網絡的鏈接預測任務中。從式(2)可以看出，其中一個核心模塊是引入影響力節(jié)點識別函數定義g(ω)。 因此，加權網絡通用性的驗證思路是引入鏈接的加權信息，將無權的節(jié)點影響力識別指標變成加權形式。由于并沒有相關文獻給出每一種影響節(jié)點識別指標的加權形式，因此一般的做法是通過將鄰接矩陣替換為加權鄰接矩陣來計算各指標的加權影響力，對應的加權指標稱為WEC(Weighted EC)、WPR(Weighted PR)、WLR(Weighted LR)和WCR(Weighted CR)，其中Weighted表示加權的含義。

3 實驗結果與分析

3.1 實驗準備

本文實驗采用Konect平臺[26]提供的不同類型的公共數據集，它們的名稱和屬性顯示在表1中，其中N是節(jié)點，E是鏈接，CC是聚類系數，K是平均度，Community 1和Community 2分別是采用上述兩種社區(qū)劃分算法劃分的社區(qū)數目，-表示無法劃分社區(qū)。

表1 數據集屬性

本實驗采用以下5類方法對上述數據集開展實驗：

方法1：基于局部共鄰節(jié)點結構信息算法：AA。

方法2：基于局部密集和社區(qū)結構算法：CC、LNBAA(Local Na?ve Bayse Adamic-Adar)、NLC。

方法3：基于路徑的算法：Katz、LP。

方法4：新近提出的基于全局鄰接矩陣變換的鏈接預測方法：(structural perturbation method，SPM)、(matrix completion，MC)。

方法5：本文提出算法：(eigenvector centrality link prediction，ECLP)、(pagerank link prediction，PRLP)、(leaderrank link prediction，LRLP)、(clusterrank link prediction，CRLP)。

同時，各算法的加權形式即在原始算法名稱前添加字母W，表示weighted。所有實驗都是在一臺具有1.5 GHz CPU內核和8 GB RAM的計算機通過Matlab語言單線程實現(xiàn)的。

3.2 實驗結果

為了驗證本文提出框架的性能，本部分實驗分成兩部分進行比較。第一組實驗把社區(qū)影響力賦予f(ω)， 把4種節(jié)點影響力賦予g(ω)， 計算該框架下各指標的性能。從表2的結果中可以得出如下結論：

(1)從總體上看，對于絕大多數數據集，提出框架的幾個指標所表示的鏈接預測效果明顯要好于其它基準算法。在Macaca和Corecipient數據集中，盡管最佳效果分別是LNBAA和NLC，但第2-第5名次優(yōu)值均是本文提出的指標。這表示g(ω) 是通用的可以嵌入不同的影響力節(jié)點指標。此外，我們在社區(qū)1下計算4類方法在各數據集中所有Precision值的平均值，第四類方法的預測準確度比第一類方法到第3類方法分別提高了4.36%、2.77%、16.62%。上述的結果不僅驗證局部函數的通用性，也充分體現(xiàn)了將兩個影響力函數考慮進去能夠得到性能更優(yōu)的指標。

(2)從不同社區(qū)算法下預測效果來看，最優(yōu)和次優(yōu)的指標基本上均是本文提出的指標，且其排名類似。除此之外，我們還測試了另外幾個社區(qū)發(fā)現(xiàn)算法，發(fā)現(xiàn)各算法的表現(xiàn)情況基本一致，由于版面關系在此不再一一列出。由此可以看出，框架是可擴展的，適配于任何社區(qū)發(fā)現(xiàn)算法。此外，盡管不同的社區(qū)劃分算法劃分的社區(qū)數目基本一致，但比較各數據集在不同社區(qū)發(fā)現(xiàn)下的效果，可以看出F-N算法的效果從整體上要更優(yōu)，具體原因可能是該社區(qū)劃分的模塊度更大，社區(qū)之間關系更加稀疏，社區(qū)影響力更能給予鏈接相似度得分貢獻。

為進一步驗證框架的魯棒性和可擴展性，第二組實驗在第一組的基礎上把2.3小節(jié)中兩個局部密集度影響賦予f(ω)， 計算該框架下各指標的性能，結果在表3中所示。從對比結果可以發(fā)現(xiàn)：

(1)和第一組實驗一樣，無論在哪種社區(qū)劃分和哪類密集度度量下，CRLP指標的預測性能最好。同時，有提出的指標在所有數據集中基本維持和實驗一一致的性能。

(2)更重要的是，在第一組實驗中Corecipient數據集各指標的預測效果均在0.7以下，低于NLC的最優(yōu)值。但是一旦引入了CC和CRA度量，4個指標的預測效果均提升了至少6%，最高達到8%。該組實驗說明了局部密集度度量能在部分數據集提升預測性能并不影響原有的社區(qū)屬性和影響力節(jié)點貢獻，也再一次驗證了提出的框架是可擴展和通用的。

表2 各指標的算法性能

表3 局部社區(qū)密集度可擴展性分析

3.3 實驗分析

為了進一步驗證算法的精度、敏感和穩(wěn)定性，本部分進行了兩部分的拓展實驗。第一部分實驗嘗試調節(jié)隨機抽取數據作為訓練集的比例，從0.6采取0.02的步長逐步調高為0.9，輸出每一步各指標下不同數據集下的預測值，這里把局部密集度影響賦予f(ω)。 為了更加清晰地比較，實驗在基準方法和提出方法均選擇2個性能最好的指標繪圖。FB和Corecipient數據集下的效果如圖2所示，其中Corecipient-com1表示對Corecipient數據集采用社區(qū)發(fā)現(xiàn)算法1，CRLP表示采用CR的鏈接預測指標。可以看出，方法4中的2個指標在大多數情況下均在右上方，尤其表示CRLP的曲線始終在右上方，這和上一小節(jié)的實驗相吻合，表明提出的指標對訓練規(guī)模是不敏感的，預測性能是穩(wěn)定的。以圖2(c)為例，當訓練集的比例從0.6到0.7時，各指標的預測值均相差無幾，當橫坐標變成0.8時，CRLP仍然是0.993，AA、CC、LNBAA、NLC、Katz、LP、EC、PR、LR分別變成0.969、0.974、0.971、0.977、0.856、0.968、0.962、0.962、0.97。然后比例漸漸升到0.85，這時LRLP效果逐漸變優(yōu)，和CRLP基本一致，均比其它基準算法要優(yōu)。第二部分實驗調整Precision@N中的N值，從N=500采取50的步長逐步調高為N=1000，輸出每一步各指標下不同數據集下的預測值，這部分使用原始的f(ω)。 和第一部分實驗一致在基準方法和提出方法均選擇2個性能最好的指標繪圖，F(xiàn)B和Corecipient數據集下的實驗如圖3所示。從結果可以看出，子圖(a)，(b)，(c)的每一步上位居右上角的曲線均是本文提出的指標，其在N值變化下預測效果是穩(wěn)定的。而子圖(d)中在N>700后最優(yōu)的指標是NLC，上述結果一方面和表1的相對應，一方面也體現(xiàn)提出指標在N<700時候性能是非常好的。該部分實驗和基于全局鄰接矩陣變幻的SPM和MC算法相比較，其中SPM基于網絡結構一致性(structural consistence)這一特性構建，該指標表示結構一致性越強的結構存在的鏈接越容易預測；MC則引入矩陣缺失信息補全的概念進行預測。在各數據集上的預測時間及結果如圖4、圖5所示。從結果可以看出，盡管各數據集最優(yōu)的預測效果出現(xiàn)在MC算法中，但是PRLP和LRLP和其相差不遠，且它們的預測性能均比SPM要高許多(在Jazz和Airport數據集上至少要高80%)。更值得注意的是：PRLP和LRLP的運行時間比SPM和MC要低許多，例如在Jazz數據集中，PRLP和LRLP運行時間僅僅需要1.3 s～1.6 s，而SPM和MC則分別達到9.2 s和5.6 s。這充分表明，本文提出的算法能在保證較高預測精確度的同時縮短運行時間，對更大規(guī)模更加密集的網絡預測場景產生更優(yōu)的效果。

圖2 FB和Corecipient數據訓練集變化下的預測效果

圖3 FB和Corecipient數據TopN變化下的預測效果

圖4 和全局指標比較的預測效果

為了綜合考慮不同Precision@N下的預測性能，本文還在加權網絡數據集上進行了兩組不同的實驗，結果見表4。從實驗結果可以看出，各數據集下N=1000的預測效果要比N=1500的預測效果要優(yōu)，這是符合鏈接預測實驗的一般規(guī)律的，表明實驗結果是有效的。更重要的是，本文提出的4類算法相比基準算法普遍能得到較好的效果，在WECLP、WPRLP、WLRLP和WCRLP各數據集的平均預測準確度是34.233%、32.767%、16.7%和21.933%，普遍要高于WAA、WLNBAA、WCC和WLP的14.967%、23.4%、16.333%和13.4%，其中最優(yōu)的效果均出現(xiàn)在WEC算法中。這說明盡管引入額外的加權信息，但是本文提出框架的幾個算法均能夠在各個加權數據集上都有優(yōu)良的表現(xiàn)，也反映出框架對不同的網絡類型是通用的。

圖5 和全局指標比較的運行時間

表4 加權算法的預測效果對比

4 結束語

本文主要介紹了一個融合社區(qū)影響力和節(jié)點影響力的鏈接預測算法。該算法集成了局部密集度信息，有效分析了不同社區(qū)結構對鏈接相似度的影響，同時充分考慮了節(jié)點影響力這一全局屬性，結合上述因素提出了一個通用的、可擴展性強的模型。實驗結果驗證了模型的有效性。

下一步工作中，我們將探索其它局部和全局因素對鏈接相似度的影響，例如網絡動態(tài)演化模式、模態(tài)(motifs)等等。此外，如何把本文方法拓展到異質、多維信息網絡也是下一步需要研究的方向。