聯(lián)合社區(qū)和影響節(jié)點的通用可擴(kuò)展的鏈接預(yù)測

伍杰華，程智鋒

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

0 引 言

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

1 相關(guān)工作和問題定義

1.1 相關(guān)工作

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

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

圖1 算法結(jié)構(gòu)模型

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

1.2 問題定義

給定一個信息網(wǎng)絡(luò)G=(V,E,C)， 其中V和E分別是節(jié)點和鏈接的集合，C是網(wǎng)絡(luò)劃分成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)。

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

2 算法模型

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

(1)

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

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

(2)

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

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

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

(3)

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

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

(4)

(5)

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

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

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

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

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

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

(6)

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

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

(7)

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

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

(8)

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

(9)

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

2.3 可擴(kuò)展性討論

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

2.3.1 局部密集度影響的可擴(kuò)展性

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

(10)

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

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

(11)

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

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

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

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

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

2.4 通用性討論

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

3 實驗結(jié)果與分析

3.1 實驗準(zhǔn)備

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

表1 數(shù)據(jù)集屬性

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

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

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

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

方法4：新近提出的基于全局鄰接矩陣變換的鏈接預(yù)測方法：(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)。

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

3.2 實驗結(jié)果

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

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

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

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

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

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

表2 各指標(biāo)的算法性能

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

3.3 實驗分析

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

圖2 FB和Corecipient數(shù)據(jù)訓(xùn)練集變化下的預(yù)測效果

圖3 FB和Corecipient數(shù)據(jù)TopN變化下的預(yù)測效果

圖4 和全局指標(biāo)比較的預(yù)測效果

為了綜合考慮不同Precision@N下的預(yù)測性能，本文還在加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了兩組不同的實驗，結(jié)果見表4。從實驗結(jié)果可以看出，各數(shù)據(jù)集下N=1000的預(yù)測效果要比N=1500的預(yù)測效果要優(yōu)，這是符合鏈接預(yù)測實驗的一般規(guī)律的，表明實驗結(jié)果是有效的。更重要的是，本文提出的4類算法相比基準(zhǔn)算法普遍能得到較好的效果，在WECLP、WPRLP、WLRLP和WCRLP各數(shù)據(jù)集的平均預(yù)測準(zhǔn)確度是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算法中。這說明盡管引入額外的加權(quán)信息，但是本文提出框架的幾個算法均能夠在各個加權(quán)數(shù)據(jù)集上都有優(yōu)良的表現(xiàn)，也反映出框架對不同的網(wǎng)絡(luò)類型是通用的。

圖5 和全局指標(biāo)比較的運行時間

表4 加權(quán)算法的預(yù)測效果對比

4 結(jié)束語

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

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