加權(quán)網(wǎng)絡(luò)中基于多路徑節(jié)點(diǎn)相似性的鏈接預(yù)測

郭景峰,劉苗苗,羅　旭

(1. 燕山大學(xué) 信息科學(xué)與工程學(xué)院,河北 秦皇島 066004;2. 東北石油大學(xué) 秦皇島分校, 黑龍江 大慶 163318；3. 燕山大學(xué) 河北省虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實驗室,河北 秦皇島 066004)

?

加權(quán)網(wǎng)絡(luò)中基于多路徑節(jié)點(diǎn)相似性的鏈接預(yù)測

郭景峰1,3,劉苗苗1,2,3,羅旭1,3

(1. 燕山大學(xué) 信息科學(xué)與工程學(xué)院,河北 秦皇島 066004;2. 東北石油大學(xué) 秦皇島分校, 黑龍江 大慶 163318；3. 燕山大學(xué) 河北省虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實驗室,河北 秦皇島 066004)

摘要:鑒于現(xiàn)有大多數(shù)鏈接預(yù)測算法僅考慮了圖的局部或全局特性,在預(yù)測準(zhǔn)確率和計算復(fù)雜度上難以均衡,且有關(guān)加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測研究相對較少,提出新的加權(quán)社會網(wǎng)絡(luò)鏈接預(yù)測算法(STNMP).引入節(jié)點(diǎn)對邊權(quán)強(qiáng)度的概念,用于度量鄰居節(jié)點(diǎn)間的局部相似度.提出路徑相似性貢獻(xiàn)的概念,定義多路徑傳輸節(jié)點(diǎn)相似性,用于描述步長為2和3的所有路徑及這些路徑上的中間節(jié)點(diǎn)對于所連接的兩個節(jié)點(diǎn)的相似性總貢獻(xiàn).在多個真實網(wǎng)絡(luò)中對算法的有效性進(jìn)行驗證,以AUC作為評價指標(biāo),與經(jīng)典相似性算法CN、Jaccard、AA等進(jìn)行預(yù)測準(zhǔn)確率的對比分析.結(jié)果顯示,針對小規(guī)模社會網(wǎng)絡(luò),STNMP算法的預(yù)測準(zhǔn)確率高于現(xiàn)有算法.

關(guān)鍵詞：鏈接預(yù)測；加權(quán)社會網(wǎng)絡(luò)；邊權(quán)強(qiáng)度；路徑相似性貢獻(xiàn)；多路徑傳輸節(jié)點(diǎn)

社會網(wǎng)絡(luò)是高度動態(tài)的,網(wǎng)絡(luò)中實體之間的關(guān)系不斷演化發(fā)展,鏈接預(yù)測成為了一項熱門研究,在推薦系統(tǒng)、信息檢索、社會網(wǎng)絡(luò)結(jié)構(gòu)動態(tài)演變分析[1]、符號網(wǎng)絡(luò)中的節(jié)點(diǎn)分類[2]等眾多領(lǐng)域有著廣泛的研究和應(yīng)用.鏈接預(yù)測指通過已知的網(wǎng)絡(luò)結(jié)構(gòu)信息預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連接邊的兩個節(jié)點(diǎn)間產(chǎn)生鏈接的可能性,分為未知鏈接預(yù)測和未來鏈接預(yù)測[3].未知鏈接預(yù)測是預(yù)測已經(jīng)存在但尚未被發(fā)現(xiàn)的鏈接,是一種數(shù)據(jù)挖掘過程,在蛋白質(zhì)相互作用網(wǎng)[4]這類生物學(xué)網(wǎng)絡(luò)中有著重要的研究意義和應(yīng)用價值.未來預(yù)測是對未來可能產(chǎn)生的連接邊的預(yù)測,與網(wǎng)絡(luò)結(jié)構(gòu)的演化相關(guān).本文關(guān)注未來預(yù)測的研究.

1相關(guān)研究

主流的鏈接預(yù)測算法是通過節(jié)點(diǎn)固有屬性定義基于節(jié)點(diǎn)相似性的算法,即兩個節(jié)點(diǎn)具有較多的共同特征,則兩者的相似度較高.現(xiàn)有基于相似性的鏈接預(yù)測方法絕大多數(shù)都是針對無權(quán)網(wǎng)絡(luò),大體可以分為兩類.一類是基于節(jié)點(diǎn)局部信息的相似性算法如CN指標(biāo)[5]、Jaccard算法[6]、Adamic-Adar算法[7]和優(yōu)先依附PA(preferentialattachment)算法[8]等.該類算法主要利用了節(jié)點(diǎn)及鄰居節(jié)點(diǎn)的度的信息,思路簡單,容易實現(xiàn),計算復(fù)雜度較低且通常能夠獲得較好的預(yù)測結(jié)果.該類算法忽略了鄰居節(jié)點(diǎn)間的聯(lián)系,不能有效地挖掘網(wǎng)絡(luò)拓?fù)湫畔?jié)點(diǎn)間相似性的影響.另一類是基于路徑結(jié)構(gòu)的相似性算法,如最短路徑算法[9]、Katz指標(biāo)[10]和局部路徑算法(localpath,LP)[11]等.該類算法考慮連接節(jié)點(diǎn)對的全部或部分路徑對于節(jié)點(diǎn)對的相似性貢獻(xiàn),但忽略了路徑上傳輸節(jié)點(diǎn)的局部相似度對節(jié)點(diǎn)對的相似性影響,且計算兩節(jié)間所有路徑信息的復(fù)雜度較高.此外,Zhou等[12]研究9種著名的局部相似性指標(biāo),提出2種新的局部指標(biāo).Panagiotis等[13]提出FriendTNS(friendtransitivenodesimilarity)算法,利用最短路徑上過渡節(jié)點(diǎn)局部相似度乘積來度量擴(kuò)展后的相似度.李淑玲[14]提出CNBIEC(commonneighborsbasedonindividualeffectcoefficient)算法,利用公共鄰居節(jié)點(diǎn)間的鏈接信息提高預(yù)測的準(zhǔn)確率.李彥敏[15]提出基于鏈接間依賴程度的鏈接預(yù)測算法,重點(diǎn)研究各個鏈接之間的關(guān)系.加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測是一個重要的方向,然而目前相關(guān)的系統(tǒng)研究工作較少.涂一娜[16]引入節(jié)點(diǎn)權(quán)重和鏈路權(quán)重概念,提出基于時間感知的加權(quán)網(wǎng)絡(luò)鏈接預(yù)測算法,獲得了較好的效果.Lv等[17]使用局部相似性指標(biāo)估計加權(quán)網(wǎng)絡(luò)中鏈接存在的可能性,提出3種加權(quán)相似性指標(biāo),可以分別看作CN、AA和RA(resourceallocation)的變體,但這些加權(quán)指標(biāo)在NetScience和USAirports網(wǎng)絡(luò)中的實驗結(jié)果不理想.

鑒于現(xiàn)有算法的局限性,本文提出新的鏈接預(yù)測算法STNMP,基于節(jié)點(diǎn)對間的多條路徑以及路徑上相鄰傳輸節(jié)點(diǎn)間的局部相似性實現(xiàn)加權(quán)網(wǎng)絡(luò)中的鏈接預(yù)測.

2STNMP算法核心思想

基于相似性的鏈接預(yù)測算法認(rèn)為兩節(jié)點(diǎn)間的相似性越高,兩者建立鏈接的可能性越大.算法的關(guān)鍵是有效地捕獲網(wǎng)絡(luò)的局部和全局特性對節(jié)點(diǎn)相似性的影響,給出合理的相似性指標(biāo)計算方法,提高算法的預(yù)測準(zhǔn)確率和執(zhí)行效率.

在度量節(jié)點(diǎn)局部屬性對相似性的影響時,認(rèn)為不是鄰居的兩節(jié)點(diǎn)間局部相似性為0.度數(shù)小的節(jié)點(diǎn)比度數(shù)大的節(jié)點(diǎn)對局部相似性的貢獻(xiàn)大.權(quán)重表示兩節(jié)點(diǎn)間連接的緊密程度,節(jié)點(diǎn)間的局部相似性應(yīng)與權(quán)重有關(guān).提出邊權(quán)強(qiáng)度的概念,用于度量鄰居節(jié)點(diǎn)間的局部相似性.

在度量路徑信息對節(jié)點(diǎn)相似性的影響時,認(rèn)為兩節(jié)點(diǎn)間的距離越遠(yuǎn),兩者存在鏈接的可能性越小.節(jié)點(diǎn)對間長度較短的路徑對于兩節(jié)點(diǎn)的相似性貢獻(xiàn)大于較長的路徑.提出路徑相似性貢獻(xiàn)的概念,用于描述某條路徑對連接的節(jié)點(diǎn)對的相似性貢獻(xiàn).基于路徑步長這一概念,定義多路徑傳輸節(jié)點(diǎn)的相似性,描述不同步長的所有路徑對節(jié)點(diǎn)對相似性的總貢獻(xiàn).

將多路徑傳輸節(jié)點(diǎn)的相似性作為節(jié)點(diǎn)對鏈接預(yù)測的分?jǐn)?shù),依據(jù)相似性定義公式計算網(wǎng)絡(luò)圖中所有尚未建立鏈接的節(jié)點(diǎn)對間的相似性得分,按降序排列,排在最前面的節(jié)點(diǎn)對建立鏈接的可能性最大.

3相關(guān)定義

為了準(zhǔn)確描述算法中節(jié)點(diǎn)對的相似性定義,給出如下相關(guān)說明：加權(quán)社會網(wǎng)絡(luò)圖G=(V,E,W)、節(jié)點(diǎn)集V、邊集E、邊的權(quán)重集合W.w(vi,vj)為節(jié)點(diǎn)vi與vj連接邊的權(quán)重.對于無權(quán)網(wǎng)絡(luò),所有邊的權(quán)重默認(rèn)為1.

定義1節(jié)點(diǎn)的強(qiáng)度設(shè)G=(V,E,W),vi∈V,{e(vi)}?E是所有連接vi的邊的集合.定義節(jié)點(diǎn)vi的強(qiáng)度為

s(vi)=∑w(e(vi)).

(1)

使用節(jié)點(diǎn)的強(qiáng)度來度量某節(jié)點(diǎn)的邊權(quán)比重在網(wǎng)絡(luò)中的重要性,等于與該節(jié)點(diǎn)相連的所有邊的權(quán)重之和.節(jié)點(diǎn)的強(qiáng)度越大,表明與該節(jié)點(diǎn)相連的邊的權(quán)重之和在整個網(wǎng)絡(luò)中所有邊的權(quán)重之和中所占的比例越大.對于無權(quán)網(wǎng)絡(luò),節(jié)點(diǎn)的強(qiáng)度為節(jié)點(diǎn)的度.

定義2邊權(quán)強(qiáng)度設(shè)G=(V,E,W),vi、vj∈V,定義節(jié)點(diǎn)對的邊權(quán)強(qiáng)度為

(2)

節(jié)點(diǎn)對的邊權(quán)強(qiáng)度用于表示節(jié)點(diǎn)vi與vj連接邊的權(quán)重在節(jié)點(diǎn)vi與vj所有鄰居節(jié)點(diǎn)連接邊的權(quán)重之和中所占的比例.該值越大,意味著節(jié)點(diǎn)vi與vj間的連接強(qiáng)度越大,兩者的相似性越高.使用節(jié)點(diǎn)對的邊權(quán)強(qiáng)度來表示兩節(jié)點(diǎn)間的局部相似性得分,記作lsim(vi,vj),即lsim(vi,vj)=sw(vi,vj).節(jié)點(diǎn)對的邊權(quán)強(qiáng)度越大,兩節(jié)點(diǎn)的局部相似性得分越高.

定義3路徑相似性貢獻(xiàn)設(shè)G=(V,E,W),vi、vj∈V,連接vi到 vj的第k條路徑為lk(vi,vj)=vieikvk1ek1vk2…eknvj,定義路徑lk對節(jié)點(diǎn)對的相似性貢獻(xiàn)為

SLk(vi,vj)=lsim(vi,vk1)×lsim(vk1,vk2)×

…lsim(vkn,vj).

(3)

使用路徑相似性貢獻(xiàn)來度量連接節(jié)點(diǎn)對的每條路徑上的中間傳輸節(jié)點(diǎn)對于節(jié)點(diǎn)對的全局相似性貢獻(xiàn)值.

定義4相似性貢獻(xiàn)設(shè)G=(V,E,W),vi、vj∈V,連接vi到 vj的所有路徑組成的集合為L={l1,l2,…,lp},定義連接vi到vj的所有路徑對節(jié)點(diǎn)對的相似性貢獻(xiàn)為

(4)

相似性貢獻(xiàn)度量了連接vi與vj的所有路徑對于節(jié)點(diǎn)對的相似性貢獻(xiàn)總和.使用相似性貢獻(xiàn)STNMP(vi,vj)作為節(jié)點(diǎn)對基于多路徑傳輸節(jié)點(diǎn)的相似性總得分.得分越高,說明vi和vj的相似度越高,兩者建立鏈接的可能性越大.

定義5路徑的步長設(shè)G=(V,E,W),vi、vj∈V,連接節(jié)點(diǎn)對的某條路徑為lk(vi,vj)=vieikvk1ek1vk2…eknvj,定義路徑lk的步長為該路徑經(jīng)過的邊的數(shù)目,記作|lk(vi,vj)|.

4算法實現(xiàn)步驟

輸入：無向加權(quán)網(wǎng)絡(luò)圖G的鄰接矩陣A.若節(jié)點(diǎn)vi與vj是鄰居,則aij=w(vi,vj),否則aij=0.

輸出：Topk個最可能建立鏈接的節(jié)點(diǎn)對.

算法的實現(xiàn)步驟如下.

1)根據(jù)定義3.2計算G中任意相鄰節(jié)點(diǎn)對間基于邊權(quán)強(qiáng)度的局部相似性得分lsim(vi,vj),并使用鏈表存儲結(jié)果(vi,vj,lsim(vi,vj)).

2)任取vi、vj∈V,且e(vi, vj)?E.根據(jù)定義3.3計算所有|l(vi,vj)|≤6的相似性貢獻(xiàn)STNMP(vi,vj),并存儲結(jié)果(vi,vj,STNMP(vi,vj)).

3)將STNMP(vi,vj)降序排序,取前k個節(jié)點(diǎn)對作為圖G基于多路徑傳輸節(jié)點(diǎn)相似性的鏈接預(yù)測結(jié)果.

5實驗與分析

通過網(wǎng)絡(luò)獲得實驗所需的數(shù)據(jù)集,劃分出訓(xùn)練集和測試集.采用AUC[18]作為評價指標(biāo),與CN、Jaccard、AA以及FriendTNS算法在預(yù)測確率方面進(jìn)行對比分析,驗證了該算法的預(yù)測準(zhǔn)確率總體高于現(xiàn)有算法.

5.1實驗所用數(shù)據(jù)集

采用6個典型的真實數(shù)據(jù)集,代表不同的網(wǎng)絡(luò)類型.前四個為加權(quán)網(wǎng)絡(luò),后兩個為無權(quán)網(wǎng)絡(luò).所選的數(shù)據(jù)集拓?fù)浣Y(jié)構(gòu)信息如表1所示.

表1　數(shù)據(jù)集拓?fù)浣Y(jié)構(gòu)信息

5.2訓(xùn)練集與測試集的劃分

為了衡量算法預(yù)測結(jié)果的準(zhǔn)確率,將已知的邊集E劃分為訓(xùn)練集和測試集.常用的劃分方法是將數(shù)據(jù)集隨機(jī)分成10個子集,每次實驗選擇一個子集作為測試集,剩下的 9個子集組成的集合作為訓(xùn)練集.如此重復(fù)10次,保證10個子集都恰好被作為一次測試集,且所有樣本數(shù)據(jù)既進(jìn)行了訓(xùn)練,也進(jìn)行了測試驗證.

在實驗中,針對每個數(shù)據(jù)集,隨機(jī)從E中取10%的邊作為測試集,記作ETe.剩下的90%的邊作為訓(xùn)練集,記作ETr.滿足E=ETe∪ETr且ETe∩ETr=?,保證所得訓(xùn)練集中的邊能夠組成一個聯(lián)通圖.將訓(xùn)練集中的信息看作已知信息,測試集用來進(jìn)行測試,驗證算法預(yù)測的準(zhǔn)確程度.

5.3評價指標(biāo)

常用的鏈接預(yù)測準(zhǔn)確度的評價指標(biāo)有AUC、Precision和RankingScore3種.三者的側(cè)重點(diǎn)不同：AUC從整體上衡量算法準(zhǔn)確度；Precision只評價排在前L位鏈接的預(yù)測準(zhǔn)確率,與實際實驗中的L取值有很大關(guān)系；RankingScore側(cè)重評價預(yù)測鏈接的排序情況[3].

鑒于AUC是目前被絕大部分鏈接預(yù)測算法廣泛采用的綜合性評價指標(biāo),本文使用AUC作為算法預(yù)測準(zhǔn)確率的衡量指標(biāo).AUC可以理解為測試集中邊的分?jǐn)?shù)比隨機(jī)選擇的不存在的邊的分?jǐn)?shù)高的概率[18].每次隨機(jī)從測試集中選取一條邊與隨機(jī)選擇的不存在的邊進(jìn)行比較,若前者的分?jǐn)?shù)大于后者,則加1分；若兩個分?jǐn)?shù)相等,則加0.5分.獨(dú)立比較n次,若有n′次測試集中邊的分?jǐn)?shù)大于不存在的邊的分?jǐn)?shù),有n″次兩者分?jǐn)?shù)相等,則AUC定義為：AUC=(n′+0.5n″)/n.若所有分?jǐn)?shù)都是隨機(jī)產(chǎn)生的,則AUC=0.5.AUC大于0.5的程度衡量了算法在多大程度上比隨機(jī)選擇的方法精確.在實驗中,AUC指標(biāo)中n設(shè)定為20 000.

5.4算法性能對比分析5.4.1步長的選擇在最初的實驗中,針對每個數(shù)據(jù)集隨機(jī)抽取劃分出訓(xùn)練集和測試集,計算了節(jié)點(diǎn)對間步長2≤|l|≤6的多路徑傳輸節(jié)點(diǎn)相似性值.在相同的實驗環(huán)境下,重復(fù)執(zhí)行10次,得到AUC評價指標(biāo)下基于不同步長的STNMP算法預(yù)測準(zhǔn)確率(見表2)及算法運(yùn)行消耗時間(見表3).表2、3中的第1列為實驗所用的數(shù)據(jù)集,第2～5列分別為取步長2≤|l|≤6的不同路徑時對應(yīng)的預(yù)測準(zhǔn)確率和運(yùn)行時間,所得的數(shù)據(jù)是10次獨(dú)立運(yùn)行結(jié)果的平均值.

從表2、3的數(shù)據(jù)可知,隨著步長的增大,運(yùn)行時間顯著增加,準(zhǔn)確率下降.針對實驗所用的數(shù)據(jù)集,取步長為2和3的所有路徑相似性貢獻(xiàn)時,所得的預(yù)測準(zhǔn)確率均達(dá)到最高值.考慮到絕大多數(shù)網(wǎng)絡(luò)的最短路徑平均長度均約為3,且根據(jù)六度空間理論可知,社會網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)均可以通過步長≤6的路徑相連.基于此,為了避免計算兩節(jié)點(diǎn)間步長≤6的所有路徑相似性貢獻(xiàn)帶來的高計算復(fù)雜度,后期改進(jìn)的STNMP算法將步長上限設(shè)置為3,將基于多路徑節(jié)點(diǎn)的相似性定義為兩節(jié)點(diǎn)間步長為2和3的所有路徑的相似性貢獻(xiàn),在保證算法執(zhí)行效率的前提下實現(xiàn)了更高的預(yù)測準(zhǔn)確率.

表2　基于不同步長的STNMP算法預(yù)測準(zhǔn)確率

表3　基于不同步長的STNMP算法運(yùn)行消耗時間

5.4.2預(yù)測準(zhǔn)確率 針對加權(quán)網(wǎng)絡(luò),將STNMP算法與Lv等[17]給出的加權(quán)CN、加權(quán)AA和加權(quán)Jaccard指標(biāo)進(jìn)行預(yù)測準(zhǔn)確率的對比.針對無權(quán)網(wǎng)絡(luò),將STNMP指標(biāo)與李淑玲[14]給出的CN、Jaccaard、AA以及FriendTNS[13]算法進(jìn)行對比.圖1、2分別給出針對不同的加權(quán)和無權(quán)網(wǎng)絡(luò)數(shù)據(jù)集AUC評價指標(biāo)下每種算法的預(yù)測準(zhǔn)確率.

從圖1、2可知,針對AUC評價指標(biāo), 6個網(wǎng)絡(luò)中STNMP算法的預(yù)測準(zhǔn)確率都是最高的.說明在該類節(jié)點(diǎn)平均度數(shù)較小、節(jié)點(diǎn)度及權(quán)重差異較小的網(wǎng)絡(luò)中,基于邊權(quán)強(qiáng)度的局部相似性定義達(dá)到了較好的效果.AUC指標(biāo)結(jié)果顯示,針對加權(quán)及無權(quán)網(wǎng)絡(luò)中的鏈接預(yù)測,STNMP算法的準(zhǔn)確率總體上優(yōu)于現(xiàn)有算法,達(dá)到了較好的預(yù)測效果.

圖1　加權(quán)網(wǎng)絡(luò)中不同算法鏈接預(yù)測準(zhǔn)確率對比Fig.1　Comparision of prediction accuracy of different algorithms in weighted networks

圖2　無權(quán)網(wǎng)絡(luò)中不同算法鏈接預(yù)測準(zhǔn)確率對比Fig.2　Comparision of prediction accuracy of different algorithms in unweighted networks

5.4.3復(fù)雜度分析STNMP算法使用矩陣和鏈表存儲圖邊關(guān)系和相似性,計算了連接兩節(jié)點(diǎn)的步長為2和3的所有路徑的相似性貢獻(xiàn).與其他幾種算法相比,該算法的計算復(fù)雜度提高.對于小規(guī)模網(wǎng)絡(luò),該算法在達(dá)到較高預(yù)測準(zhǔn)確率的前提下,仍可保證時間上的可行性和有效性.

6結(jié)語

本文提出鏈接預(yù)測算法STNMP,首先定義了邊權(quán)強(qiáng)度和路徑相似性貢獻(xiàn),在此基礎(chǔ)上定義了節(jié)點(diǎn)對間步長為2和3的多路徑傳輸節(jié)點(diǎn)相似性,用于加權(quán)社會網(wǎng)絡(luò)中的鏈接預(yù)測.使用AUC作為評價指標(biāo),在多個真實數(shù)據(jù)集上進(jìn)行實驗,并與經(jīng)典相似性鏈接預(yù)測算法進(jìn)行性能對比.實驗結(jié)果驗證了該算法較高的預(yù)測準(zhǔn)確率和良好的通用性.該算法有待在大規(guī)模真實網(wǎng)絡(luò)中進(jìn)一步驗證,以改進(jìn)相似性指標(biāo)的定義,有效地提高算法執(zhí)行效率.有關(guān)符號網(wǎng)絡(luò)中的節(jié)點(diǎn)類型預(yù)測,并結(jié)合結(jié)構(gòu)平衡理論分析預(yù)測產(chǎn)生的新鏈接對于網(wǎng)絡(luò)結(jié)構(gòu)整體平衡性的影響,是下一步的研究工作.

參考文獻(xiàn)(References)：

[1]KUMARR,NOVAKJ,TOMKINSA.Structureandevolutionofonlinesocialnetworks[C]∥ProceedingsoftheACMSIGKDD.NewYork:ACM, 2006: 611-617．

[2]GALLAGHERB,TONGH,ELIASSI-RADT,etal.Usingghostedgesforclassificationinsparselylabelednetworks[C]∥ProceedingsoftheACMSIGKDD.NewYork:ACM, 2008: 256-264．

[3] 呂琳媛. 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J]. 電子科技大學(xué)學(xué)報, 2010, 39(5): 651-661．

LVLin-yuan.Linkpredictionofcomplexnetworks[J].JournalofUniversityofElectronicScienceandTechnologyofChina, 2010, 39(5): 651-661．[4]YUH,BRAUNP,YILDIRIMMA,etal.High-qualitybinaryproteininteractionmapoftheyeastinteractomenetwork[J].Science, 2008, 322(5898): 104-110．

[5]NEWMANM.Thestructureandfunctionofcomplexnetworks[J].SIAMReview, 2003, 45(2): 167-256．

[6] 張揚(yáng)夫. 有向與加權(quán)網(wǎng)絡(luò)的鏈路預(yù)測[D]. 湘潭:湘潭大學(xué), 2011: 5-11．

ZHANGYang-fu.Linkpredictionindirectedandweightednetworks[D].Xiangtan:XiangtanUniversity, 2011: 5-11．

[7]ADAMICL,ADARE.Howtosearchasocialnetwork[J].SocialNetworks, 2005, 27 (3): 187-203．

[8]NEWMANM.Clusteringandpreferentialattachmentingrowingnetworks[J].PhysicalReviewE, 2001, 64(2): 025102-1-4．

[9] 姚尊強(qiáng).加權(quán)復(fù)雜網(wǎng)絡(luò)的分析和預(yù)測[D]. 青島: 青島理工大學(xué), 2012: 35-43．

YAOZun-qiang.Theanalysisandpredictionofweightedcomplexnetworks[D].Qingdao:QingdaoTechnologicalUniversity, 2012: 35-43．

[10]KATZL.Anewstatusindexderivedfromsocialmetricanalysis[J].Psychometrika, 1953, 18(1): 39-43．

[11] 張珊靚, 周晏. 基于隨機(jī)游走的時間加權(quán)社會網(wǎng)絡(luò)鏈接預(yù)測算法[J].計算機(jī)應(yīng)用與軟件, 2014, 31(7): 28-30．

ZHANGShan-liang,ZHOUYan.Timeweightedsocialnetworkslinkpredictionalgorithmbasedonrandomwalk[J].ComputerApplicationandSoftware, 2014, 31(7): 28-30．

[12]ZHOUTao,LVLin-yuan,ZHANGYi-cheng.Predictingmissinglinksvialocalinformation[J].TheEuropeanPhysicalJournalB, 2009, 10(1140): 623-630．

[13]PANAGIOTISS，ELEFTHERIOST，YANNISM.Transitivenodesimilarityforlinkpredictioninsocialnetworkswithpositiveandnegativelinks[C]∥Proceedingsofthe4thACMConferenceonRecommenderSystem.Barcelona:ACM, 2010: 183-190．

[14] 李淑玲. 基于相似性的鏈接預(yù)測方法研究[D]. 哈爾濱：哈爾濱工程大學(xué), 2012: 25-46．

LIShu-ling.Researchonlinkpredictionmethodsbasedonthesimilarity[D].Harbin:HarbinEngineeringUniversity, 2012: 25-46．

[15] 李彥敏.基于鏈接依賴度的鏈接預(yù)測[D].長春：吉林大學(xué), 2013: 20-33．

LIYan-min.Linkpredictionbasedonlinkdependency[D].Changchun:JilinUniversity, 2013: 20-33．

[16] 涂一娜. 具有時間感知的加權(quán)網(wǎng)絡(luò)鏈路預(yù)測研究[D]. 長沙: 中南大學(xué), 2014: 20-43．

TUYi-na.Studyonlinkpredictionoftheweightednetworkswithtime-aware[D].Changsha:ZhongnanUniversity, 2014: 20-43．

[17]LVLin-yuan,ZHOUTao.Linkpredictioninweightednetworks:theroleofweakties[J].EurophysicsLetters, 2010, 89: 18001．

[18] 余宏俊. 基于符號網(wǎng)絡(luò)的社群分析方法研究[D]. 武漢：華中科技大學(xué), 2011: 31-32．

YUHong-jun.Theresearchofcommunityanalysisbasedonsignedsocialnetworks[D].Wuhan:HuazhongUniversityofScienceandTechnology, 2011: 31-32.

收稿日期：2015-10-17.浙江大學(xué)學(xué)報(工學(xué)版)網(wǎng)址： www.journals.zju.edu.cn/eng

基金項目：國家自然科學(xué)基金資助項目(61472340)；河北省秦皇島市科技支撐資助項目(201502A003).

作者簡介：郭景峰(1962-)，男，教授，博導(dǎo),從事數(shù)據(jù)挖掘、社會網(wǎng)絡(luò)分析研究. 通信聯(lián)系人：劉苗苗，女，副教授.ORCID: 0000-0001-8569-0693. E-mail：liumiaomiao82@163.com

DOI:10.3785/j.issn.1008-973X.2016.07.017

中圖分類號：TP 391

文獻(xiàn)標(biāo)志碼：A

文章編號：1008-973X(2016)07-1347-06

Linkpredictionbasedonsimilarityofnodesofmultipathinweightedsocialnetworks

GUOJing-feng1,3,LIUMiao-miao1,2,3,LUOXu1,3

(1. College of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China;2. Qinhuangdao Branch,Northeast Petroleum University, Daqing 163318, China; 3. Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province, Yanshan University,Qinhuangdao 066004, China)

Abstract:A novel algorithm similarity based on transmission nodes of multipath (STNMP) for link prediction in weighted social networks was proposed in view of the fact that most link prediction algorithms only considered local or global characteristics of the graph, which was difficult to achieve equilibrium in the prediction accuracy and the computational complexity, and researches on link prediction in weighted social networks were relatively less. The concept of the edge weight strength was introduced to measure the local similarity of neighbor node pairs. The similarity of transmission nodes of multipath was proposed and the definition of the path similarity contribution was given, which were used to describe the total contribution of all these paths of 2 and 3 paces to the similarity of node pairs. The effectiveness of the algorithm was verified through experiments on many real networks. The comparison and analysis on prediction accuracy of the algorithm were conducted with those classical link prediction algorithms based on the similarity index, such as common neighbor (CN), Jaccard and Adamic-Adar under the evaluation index of area under the receiver operating characteristic curve (AUC). Results showed the accuracy of STNMP algorithm was higher than those of existing algorithms for small scale of social network.

Key words:link prediction; weighted social network; edge weight strength; path similarity contribution; transmission nodes of multipath