加權網絡中基于多路徑節點相似性的鏈接預測
2016-08-04 07:05:36郭景峰劉苗苗
浙江大學學報(工學版) 2016年7期
郭景峰,劉苗苗,羅 旭
(1. 燕山大學 信息科學與工程學院,河北 秦皇島 066004;2. 東北石油大學 秦皇島分校, 黑龍江 大慶 163318；3. 燕山大學 河北省虛擬技術與系統集成重點實驗室,河北 秦皇島 066004)
?
加權網絡中基于多路徑節點相似性的鏈接預測
郭景峰1,3,劉苗苗1,2,3,羅旭1,3
(1. 燕山大學 信息科學與工程學院,河北 秦皇島 066004;2. 東北石油大學 秦皇島分校, 黑龍江 大慶 163318；3. 燕山大學 河北省虛擬技術與系統集成重點實驗室,河北 秦皇島 066004)
摘要:鑒于現有大多數鏈接預測算法僅考慮了圖的局部或全局特性,在預測準確率和計算復雜度上難以均衡,且有關加權網絡的鏈接預測研究相對較少,提出新的加權社會網絡鏈接預測算法(STNMP).引入節點對邊權強度的概念,用于度量鄰居節點間的局部相似度.提出路徑相似性貢獻的概念,定義多路徑傳輸節點相似性,用于描述步長為2和3的所有路徑及這些路徑上的中間節點對于所連接的兩個節點的相似性總貢獻.在多個真實網絡中對算法的有效性進行驗證,以AUC作為評價指標,與經典相似性算法CN、Jaccard、AA等進行預測準確率的對比分析.結果顯示,針對小規模社會網絡,STNMP算法的預測準確率高于現有算法.
關鍵詞：鏈接預測；加權社會網絡；邊權強度；路徑相似性貢獻；多路徑傳輸節點
社會網絡是高度動態的,網絡中實體之間的關系不斷演化發展,鏈接預測成為了一項熱門研究,在推薦系統、信息檢索、社會網絡結構動態演變分析[1]、符號網絡中的節點分類[2]等眾多領域有著廣泛的研究和應用.鏈接預測指通過已知的網絡結構信息預測網絡中尚未產生連接邊的兩個節點間產生鏈接的可能性,分為未知鏈接預測和未來鏈接預測[3].未知鏈接預測是預測已經存在但尚未被發現的鏈接,是一種數據挖掘過程,在蛋白質相互作用網[4]這類生物學網絡中有著重要的研究意義和應用價值.未來預測是對未來可能產生的連接邊的預測,與網絡結構的演化相關.本文關注未來預測的研究.
1相關研究
主流的鏈接預測算法是通過節點固有屬性定義基于節點相似性的算法,即兩個節點具有較多的共同特征,則兩者的相似度較高.現有基于相似性的鏈接預測方法絕大多數都是針對無權網絡,大體可以分為兩類.一類是基于節點局部信息的相似性算法如CN指標[5]、Jaccard算法[6]、Adamic-Adar算法[7]和優先依附PA(preferentialattachment)算法[8]等.該類算法主要利用了節點及鄰居節點的度的信息,思路簡單,容易實現,計算復雜度較低且通常能夠獲得較好的預測結果.該類算法忽略了鄰居節點間的聯系,不能有效地挖掘網絡拓撲信息對節點間相似性的影響.另一類是基于路徑結構的相似性算法,如最短路徑算法[9]、Katz指標[10]和局部路徑算法(localpath,LP)[11]等.該類算法考慮連接節點對的全部或部分路徑對于節點對的相似性貢獻,但忽略了路徑上傳輸節點的局部相似度對節點對的相似性影響,且計算兩節間所有路徑信息的復雜度較高.此外,Zhou等[12]研究9種著名的局部相似性指標,提出2種新的局部指標.Panagiotis等[13]提出FriendTNS(friendtransitivenodesimilarity)算法,利用最短路徑上過渡節點局部相似度乘積來度量擴展后的相似度.李淑玲[14]提出CNBIEC(commonneighborsbasedonindividualeffectcoefficient)算法,利用公共鄰居節點間的鏈接信息提高預測的準確率.李彥敏[15]提出基于鏈接間依賴程度的鏈接預測算法,重點研究各個鏈接之間的關系.加權網絡的鏈接預測是一個重要的方向,然而目前相關的系統研究工作較少.涂一娜[16]引入節點權重和鏈路權重概念,提出基于時間感知的加權網絡鏈接預測算法,獲得了較好的效果.Lv等[17]使用局部相似性指標估計加權網絡中鏈接存在的可能性,提出3種加權相似性指標,可以分別看作CN、AA和RA(resourceallocation)的變體,但這些加權指標在NetScience和USAirports網絡中的實驗結果不理想.
鑒于現有算法的局限性,本文提出新的鏈接預測算法STNMP,基于節點對間的多條路徑以及路徑上相鄰傳輸節點間的局部相似性實現加權網絡中的鏈接預測.
2STNMP算法核心思想
基于相似性的鏈接預測算法認為兩節點間的相似性越高,兩者建立鏈接的可能性越大.算法的關鍵是有效地捕獲網絡的局部和全局特性對節點相似性的影響,給出合理的相似性指標計算方法,提高算法的預測準確率和執行效率.
在度量節點局部屬性對相似性的影響時,認為不是鄰居的兩節點間局部相似性為0.度數小的節點比度數大的節點對局部相似性的貢獻大.權重表示兩節點間連接的緊密程度,節點間的局部相似性應與權重有關.提出邊權強度的概念,用于度量鄰居節點間的局部相似性.
在度量路徑信息對節點相似性的影響時,認為兩節點間的距離越遠,兩者存在鏈接的可能性越小.節點對間長度較短的路徑對于兩節點的相似性貢獻大于較長的路徑.提出路徑相似性貢獻的概念,用于描述某條路徑對連接的節點對的相似性貢獻.基于路徑步長這一概念,定義多路徑傳輸節點的相似性,描述不同步長的所有路徑對節點對相似性的總貢獻.
將多路徑傳輸節點的相似性作為節點對鏈接預測的分數,依據相似性定義公式計算網絡圖中所有尚未建立鏈接的節點對間的相似性得分,按降序排列,排在最前面的節點對建立鏈接的可能性最大.
3相關定義
為了準確描述算法中節點對的相似性定義,給出如下相關說明：加權社會網絡圖G=(V,E,W)、節點集V、邊集E、邊的權重集合W.w(vi,vj)為節點vi與vj連接邊的權重.對于無權網絡,所有邊的權重默認為1.
定義1節點的強度設G=(V,E,W),vi∈V,{e(vi)}?E是所有連接vi的邊的集合.定義節點vi的強度為
s(vi)=∑w(e(vi)).
(1)
使用節點的強度來度量某節點的邊權比重在網絡中的重要性,等于與該節點相連的所有邊的權重之和.節點的強度越大,表明與該節點相連的邊的權重之和在整個網絡中所有邊的權重之和中所占的比例越大.對于無權網絡,節點的強度為節點的度.
定義2邊權強度設G=(V,E,W),vi、vj∈V,定義節點對
(2)
節點對
定義3路徑相似性貢獻設G=(V,E,W),vi、vj∈V,連接vi到 vj的第k條路徑為lk(vi,vj)=vieikvk1ek1vk2…eknvj,定義路徑lk對節點對
SLk(vi,vj)=lsim(vi,vk1)×lsim(vk1,vk2)×
…lsim(vkn,vj).
(3)
使用路徑相似性貢獻來度量連接節點對
定義4相似性貢獻設G=(V,E,W),vi、vj∈V,連接vi到 vj的所有路徑組成的集合為L={l1,l2,…,lp},定義連接vi到vj的所有路徑對節點對
(4)
相似性貢獻度量了連接vi與vj的所有路徑對于節點對
定義5路徑的步長設G=(V,E,W),vi、vj∈V,連接節點對
4算法實現步驟
輸入：無向加權網絡圖G的鄰接矩陣A.若節點vi與vj是鄰居,則aij=w(vi,vj),否則aij=0.
輸出：Topk個最可能建立鏈接的節點對.
算法的實現步驟如下.
1)根據定義3.2計算G中任意相鄰節點對間基于邊權強度的局部相似性得分lsim(vi,vj),并使用鏈表存儲結果(vi,vj,lsim(vi,vj)).
2)任取vi、vj∈V,且e(vi, vj)?E.根據定義3.3計算所有|l(vi,vj)|≤6的相似性貢獻STNMP(vi,vj),并存儲結果(vi,vj,STNMP(vi,vj)).
3)將STNMP(vi,vj)降序排序,取前k個節點對作為圖G基于多路徑傳輸節點相似性的鏈接預測結果.
5實驗與分析
通過網絡獲得實驗所需的數據集,劃分出訓練集和測試集.采用AUC[18]作為評價指標,與CN、Jaccard、AA以及FriendTNS算法在預測確率方面進行對比分析,驗證了該算法的預測準確率總體高于現有算法.
5.1實驗所用數據集
采用6個典型的真實數據集,代表不同的網絡類型.前四個為加權網絡,后兩個為無權網絡.所選的數據集拓撲結構信息如表1所示.
表1 數據集拓撲結構信息
5.2訓練集與測試集的劃分
為了衡量算法預測結果的準確率,將已知的邊集E劃分為訓練集和測試集.常用的劃分方法是將數據集隨機分成10個子集,每次實驗選擇一個子集作為測試集,剩下的 9個子集組成的集合作為訓練集.如此重復10次,保證10個子集都恰好被作為一次測試集,且所有樣本數據既進行了訓練,也進行了測試驗證.
在實驗中,針對每個數據集,隨機從E中取10%的邊作為測試集,記作ETe.剩下的90%的邊作為訓練集,記作ETr.滿足E=ETe∪ETr且ETe∩ETr=?,保證所得訓練集中的邊能夠組成一個聯通圖.將訓練集中的信息看作已知信息,測試集用來進行測試,驗證算法預測的準確程度.
5.3評價指標
常用的鏈接預測準確度的評價指標有AUC、Precision和RankingScore3種.三者的側重點不同：AUC從整體上衡量算法準確度；Precision只評價排在前L位鏈接的預測準確率,與實際實驗中的L取值有很大關系；RankingScore側重評價預測鏈接的排序情況[3].
鑒于AUC是目前被絕大部分鏈接預測算法廣泛采用的綜合性評價指標,本文使用AUC作為算法預測準確率的衡量指標.AUC可以理解為測試集中邊的分數比隨機選擇的不存在的邊的分數高的概率[18].每次隨機從測試集中選取一條邊與隨機選擇的不存在的邊進行比較,若前者的分數大于后者,則加1分；若兩個分數相等,則加0.5分.獨立比較n次,若有n′次測試集中邊的分數大于不存在的邊的分數,有n″次兩者分數相等,則AUC定義為：AUC=(n′+0.5n″)/n.若所有分數都是隨機產生的,則AUC=0.5.AUC大于0.5的程度衡量了算法在多大程度上比隨機選擇的方法精確.在實驗中,AUC指標中n設定為20 000.
5.4算法性能對比分析5.4.1步長的選擇在最初的實驗中,針對每個數據集隨機抽取劃分出訓練集和測試集,計算了節點對間步長2≤|l|≤6的多路徑傳輸節點相似性值.在相同的實驗環境下,重復執行10次,得到AUC評價指標下基于不同步長的STNMP算法預測準確率(見表2)及算法運行消耗時間(見表3).表2、3中的第1列為實驗所用的數據集,第2～5列分別為取步長2≤|l|≤6的不同路徑時對應的預測準確率和運行時間,所得的數據是10次獨立運行結果的平均值.
從表2、3的數據可知,隨著步長的增大,運行時間顯著增加,準確率下降.針對實驗所用的數據集,取步長為2和3的所有路徑相似性貢獻時,所得的預測準確率均達到最高值.考慮到絕大多數網絡的最短路徑平均長度均約為3,且根據六度空間理論可知,社會網絡中任意兩節點均可以通過步長≤6的路徑相連.基于此,為了避免計算兩節點間步長≤6的所有路徑相似性貢獻帶來的高計算復雜度,后期改進的STNMP算法將步長上限設置為3,將基于多路徑節點的相似性定義為兩節點間步長為2和3的所有路徑的相似性貢獻,在保證算法執行效率的前提下實現了更高的預測準確率.
表2 基于不同步長的STNMP算法預測準確率
表3 基于不同步長的STNMP算法運行消耗時間
5.4.2預測準確率 針對加權網絡,將STNMP算法與Lv等[17]給出的加權CN、加權AA和加權Jaccard指標進行預測準確率的對比.針對無權網絡,將STNMP指標與李淑玲[14]給出的CN、Jaccaard、AA以及FriendTNS[13]算法進行對比.圖1、2分別給出針對不同的加權和無權網絡數據集AUC評價指標下每種算法的預測準確率.
從圖1、2可知,針對AUC評價指標, 6個網絡中STNMP算法的預測準確率都是最高的.說明在該類節點平均度數較小、節點度及權重差異較小的網絡中,基于邊權強度的局部相似性定義達到了較好的效果.AUC指標結果顯示,針對加權及無權網絡中的鏈接預測,STNMP算法的準確率總體上優于現有算法,達到了較好的預測效果.
圖1 加權網絡中不同算法鏈接預測準確率對比Fig.1 Comparision of prediction accuracy of different algorithms in weighted networks
圖2 無權網絡中不同算法鏈接預測準確率對比Fig.2 Comparision of prediction accuracy of different algorithms in unweighted networks
5.4.3復雜度分析STNMP算法使用矩陣和鏈表存儲圖邊關系和相似性,計算了連接兩節點的步長為2和3的所有路徑的相似性貢獻.與其他幾種算法相比,該算法的計算復雜度提高.對于小規模網絡,該算法在達到較高預測準確率的前提下,仍可保證時間上的可行性和有效性.
6結語
本文提出鏈接預測算法STNMP,首先定義了邊權強度和路徑相似性貢獻,在此基礎上定義了節點對間步長為2和3的多路徑傳輸節點相似性,用于加權社會網絡中的鏈接預測.使用AUC作為評價指標,在多個真實數據集上進行實驗,并與經典相似性鏈接預測算法進行性能對比.實驗結果驗證了該算法較高的預測準確率和良好的通用性.該算法有待在大規模真實網絡中進一步驗證,以改進相似性指標的定義,有效地提高算法執行效率.有關符號網絡中的節點類型預測,并結合結構平衡理論分析預測產生的新鏈接對于網絡結構整體平衡性的影響,是下一步的研究工作.
參考文獻(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] 呂琳媛. 復雜網絡鏈路預測[J]. 電子科技大學學報, 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] 張揚夫. 有向與加權網絡的鏈路預測[D]. 湘潭:湘潭大學, 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] 姚尊強.加權復雜網絡的分析和預測[D]. 青島: 青島理工大學, 2012: 35-43．
YAOZun-qiang.Theanalysisandpredictionofweightedcomplexnetworks[D].Qingdao:QingdaoTechnologicalUniversity, 2012: 35-43．
[10]KATZL.Anewstatusindexderivedfromsocialmetricanalysis[J].Psychometrika, 1953, 18(1): 39-43．
[11] 張珊靚, 周晏. 基于隨機游走的時間加權社會網絡鏈接預測算法[J].計算機應用與軟件, 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] 李淑玲. 基于相似性的鏈接預測方法研究[D]. 哈爾濱：哈爾濱工程大學, 2012: 25-46．
LIShu-ling.Researchonlinkpredictionmethodsbasedonthesimilarity[D].Harbin:HarbinEngineeringUniversity, 2012: 25-46．
[15] 李彥敏.基于鏈接依賴度的鏈接預測[D].長春：吉林大學, 2013: 20-33．
LIYan-min.Linkpredictionbasedonlinkdependency[D].Changchun:JilinUniversity, 2013: 20-33．
[16] 涂一娜. 具有時間感知的加權網絡鏈路預測研究[D]. 長沙: 中南大學, 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] 余宏俊. 基于符號網絡的社群分析方法研究[D]. 武漢：華中科技大學, 2011: 31-32．
YUHong-jun.Theresearchofcommunityanalysisbasedonsignedsocialnetworks[D].Wuhan:HuazhongUniversityofScienceandTechnology, 2011: 31-32.
收稿日期：2015-10-17.浙江大學學報(工學版)網址： www.journals.zju.edu.cn/eng
基金項目：國家自然科學基金資助項目(61472340)；河北省秦皇島市科技支撐資助項目(201502A003).
作者簡介：郭景峰(1962-)，男，教授，博導,從事數據挖掘、社會網絡分析研究. 通信聯系人：劉苗苗，女，副教授.ORCID: 0000-0001-8569-0693. E-mail：liumiaomiao82@163.com
DOI:10.3785/j.issn.1008-973X.2016.07.017
中圖分類號：TP 391
文獻標志碼：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
