李婷, 張海,2

(1.西北大學(xué) 數(shù)學(xué)學(xué)院, 陜西 西安　710127；2.中國科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)院應(yīng)用數(shù)學(xué)所, 北京　100190)

?

基于結(jié)構(gòu)加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測

李婷1, 張海1,2

(1.西北大學(xué) 數(shù)學(xué)學(xué)院, 陜西 西安710127；2.中國科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)院應(yīng)用數(shù)學(xué)所, 北京100190)

摘要：研究社會網(wǎng)絡(luò)中邊的鏈接預(yù)測問題，試圖根據(jù)網(wǎng)絡(luò)中邊的結(jié)構(gòu)權(quán)重信息，將無權(quán)網(wǎng)絡(luò)轉(zhuǎn)換為加權(quán)網(wǎng)絡(luò)進行研究。進而，對于一些加權(quán)網(wǎng)絡(luò)，重新考慮其權(quán)重，分別以真實權(quán)重、結(jié)構(gòu)權(quán)重以及將兩者結(jié)合后的值作為網(wǎng)絡(luò)中邊的權(quán)重，研究resource allocation along local path(RALP)等指標、資源分配(RA)指標和局部路徑(LP)指標在加權(quán)網(wǎng)絡(luò)中的鏈接預(yù)測情況。實驗結(jié)果表明，文中所提統(tǒng)計方法有著良好的預(yù)測效果，而且加權(quán)RALP指標的預(yù)測精度優(yōu)于加權(quán)RA指標和加權(quán)LP指標。

關(guān)鍵詞：鏈接預(yù)測；結(jié)構(gòu)權(quán)重；統(tǒng)計方法

復(fù)雜系統(tǒng)通常都可以通過網(wǎng)絡(luò)表示，其中節(jié)點表示系統(tǒng)中的個體或諸多對象，邊則表示個體或?qū)ο箝g的關(guān)系[1-2]。隨著互聯(lián)網(wǎng)的快速發(fā)展，形成了諸如Facebook、人人網(wǎng)、微博等社交網(wǎng)絡(luò)，使得人與人之間的交流變得更加便利。因此，開展此類數(shù)據(jù)分析，提取網(wǎng)絡(luò)特征是一項非常有意義的工作。網(wǎng)絡(luò)的社會分析也成為近年來統(tǒng)計學(xué)、計算機科學(xué)、物理學(xué)、社會科學(xué)等研究領(lǐng)域的一個熱點，其中鏈接預(yù)測是網(wǎng)絡(luò)分析中的一個基本問題。

鏈接預(yù)測是指通過網(wǎng)絡(luò)已知的連接邊及節(jié)點屬性或網(wǎng)絡(luò)結(jié)構(gòu)等信息，預(yù)測未連接邊的2個節(jié)點之間產(chǎn)生連接的可能性。近年來，基于網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點屬性的鏈接預(yù)測方法受到廣泛關(guān)注[3-4]，例如O′Madadhain等[5]利用節(jié)點屬性以及網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息，建立了一個局部條件概率模型并以此進行預(yù)測；Bai等[6]通過結(jié)合RA指標和LP指標提出了一個半局部相似性指標(即RALP指標)，實驗得出該指標在網(wǎng)絡(luò)的鏈接預(yù)測中優(yōu)于RA和LP指標。

鏈接預(yù)測的許多算法已被應(yīng)用于很多真實的網(wǎng)絡(luò)，但是這些學(xué)習(xí)算法很少考慮網(wǎng)絡(luò)中邊的權(quán)重信息。Murata和Moriyasu[7]提出了共同鄰居(CN)、Adamic-Adar(AA)、偏好連接(PA)3個相似性指標及其加權(quán)形式，并將其應(yīng)用于Question-AnswerBulletinBoardsSystem網(wǎng)絡(luò)。結(jié)果顯示，考慮權(quán)重信息提高了鏈接預(yù)測精度，但在共同作者網(wǎng)絡(luò)和美國航空網(wǎng)絡(luò)中加權(quán)指標預(yù)測結(jié)果反而比無權(quán)的差，即所謂的“弱連接”效應(yīng)。Zhou等[8]研究了CN、AA、RA指標以及其加權(quán)形式等在3個真實網(wǎng)絡(luò)中的預(yù)測效果，驗證了鏈接預(yù)測問題中存在的“弱連接”效應(yīng)。進而，Wang等[9]考慮了網(wǎng)絡(luò)節(jié)點的鄰域結(jié)構(gòu)信息，提出了將網(wǎng)絡(luò)中每條邊的簇系數(shù)作為其權(quán)重的方法，研究了CN、AA、RA、LP4種相似性指標在8個真實網(wǎng)絡(luò)中的鏈接預(yù)測情況，實驗結(jié)果表明，當以邊的簇系數(shù)作為權(quán)重時，可以有效提高加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測精度。一個很自然的問題是，能否將RALP指標應(yīng)用于考慮結(jié)構(gòu)權(quán)重或者同時考慮結(jié)構(gòu)權(quán)重和真實權(quán)重信息時的網(wǎng)絡(luò)鏈接預(yù)測情況呢？

本文中，我們將考慮網(wǎng)絡(luò)的結(jié)構(gòu)權(quán)重信息，研究RALP等指標在這些真實網(wǎng)絡(luò)中的鏈接預(yù)測效果。通過研究，我們發(fā)現(xiàn)無論是無權(quán)網(wǎng)絡(luò)還是加權(quán)網(wǎng)絡(luò)，當其考慮結(jié)構(gòu)權(quán)重信息時對于RALP、RA和LP指標都能有效提高網(wǎng)絡(luò)的鏈接預(yù)測效果，同時RALP指標的預(yù)測結(jié)果優(yōu)于RA指標和LP指標。

1基于加權(quán)網(wǎng)絡(luò)的模型

我們考慮簡單無向網(wǎng)絡(luò)G(V,E)，其中V表示節(jié)點集，E表示邊集合，并且忽略節(jié)點間多邊信息和同一節(jié)點自連接信息。對于每一對節(jié)點x,y∈V，根據(jù)文中所提相似性指標計算數(shù)值Sxy，其中Sxy表示2個節(jié)點x和y間的相似性，值越高表示兩節(jié)點越相似。

1)資源分配(RA)指標：Zhou等[10]提出了資源分配指標,其定義為

(1)

式中，k(z)表示節(jié)點z的度，Γ(x)表示節(jié)點x的鄰居。

2)局部路徑(LP)指標：Zhou等[10-11]提出基于局部路徑的相似性指標。其定義為

(2)

式中，(A2)xy表示節(jié)點x和節(jié)點y之間長度為2的路徑數(shù)目，(A3)xy表示節(jié)點x和節(jié)點y之間長度為3的路徑數(shù)目，ε=0.001為可調(diào)參數(shù)。

3)沿局部路徑的資源分配(RALP)指標：Bai等[6]提出了將資源分配過程結(jié)合到局部路徑中得到了一個新的指標。其定義為

(3)

式中，lx→y表示從節(jié)點x到節(jié)點y的長度為3的路徑，i和j是路徑lx→y中的2個節(jié)點。

上述3個相似性指標都是基于無權(quán)網(wǎng)絡(luò)定義的，然而在真實世界中，網(wǎng)絡(luò)中的邊通常都含有權(quán)重信息。因此當考慮權(quán)重信息時，上述3個相似性指標的加權(quán)形式可定義如下：

1)加權(quán)RA(WRA)指標：

(4)

2)加權(quán)LP(WLP)指標：

(5)

3)加權(quán)RALP(WRALP)指標：

(6)

本文結(jié)合RALP、RA和LP3個加權(quán)相似性指標與結(jié)構(gòu)權(quán)重信息，推廣了Zhou等[8]和Bai等[6]的工作，分別對4個無權(quán)網(wǎng)絡(luò)和3個加權(quán)網(wǎng)絡(luò)進行了研究。由于在真實世界中，一些網(wǎng)絡(luò)中的邊是不含權(quán)重信息的，所以為了研究和提高無權(quán)網(wǎng)絡(luò)的鏈接預(yù)測精度，以結(jié)構(gòu)權(quán)重作為網(wǎng)絡(luò)中邊的權(quán)重，研究RALP、RA和LP3個指標的鏈接預(yù)測問題。同時為了比較，也研究了無權(quán)網(wǎng)絡(luò)在不考慮結(jié)構(gòu)權(quán)重信息時的鏈接預(yù)測情況。其中結(jié)構(gòu)權(quán)重(主要研究邊的簇系數(shù))[9]表示真實網(wǎng)絡(luò)中邊存在的概率，其定義為：

(7)

式中，Nij表示共同鄰居的個數(shù)。

當然，有些網(wǎng)絡(luò)中的邊是含有權(quán)重信息的。所以，為了研究和提高這些加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測效果，我們分別以網(wǎng)絡(luò)的真實權(quán)重、結(jié)構(gòu)權(quán)重、兩者結(jié)合后的值作為邊的權(quán)重，研究RALP、RA、LP3個指標的預(yù)測情況。其中分別采用3種方式結(jié)合真實權(quán)重和結(jié)構(gòu)權(quán)重：平均值法、最小值法、最大值法。

2實驗

選用UCI數(shù)據(jù)庫中來自不同領(lǐng)域的7個網(wǎng)絡(luò)，并忽略網(wǎng)絡(luò)中邊的方向。其中這7個網(wǎng)絡(luò)分別為：空手道俱樂部、海豚社會網(wǎng)絡(luò)、美國大學(xué)橄欖球、美國政治書籍網(wǎng)絡(luò)、線蟲的神經(jīng)網(wǎng)絡(luò)、孤星淚網(wǎng)絡(luò)小說中的人物共性網(wǎng)絡(luò)、國航空網(wǎng)絡(luò)。

研究了無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)。實驗1中將網(wǎng)絡(luò)結(jié)構(gòu)權(quán)重作為無權(quán)網(wǎng)絡(luò)的權(quán)重，作為比較，同時也研究在其不考慮結(jié)構(gòu)權(quán)重信息時的鏈接預(yù)測能力，結(jié)果如表1所示。

表1　4個無權(quán)網(wǎng)絡(luò)在考慮結(jié)構(gòu)權(quán)重時的鏈接預(yù)測結(jié)果比較

表2　3個加權(quán)網(wǎng)絡(luò)在考慮結(jié)構(gòu)權(quán)重時的鏈接預(yù)測結(jié)果比較

在實驗2中，分別以網(wǎng)絡(luò)的真實權(quán)重、結(jié)構(gòu)權(quán)重、兩者結(jié)合后的值作為邊的權(quán)重，結(jié)果如表2所示。

通過比較，發(fā)現(xiàn)以結(jié)構(gòu)權(quán)重作為網(wǎng)絡(luò)邊的權(quán)重時，提高了網(wǎng)絡(luò)的鏈接預(yù)測精度，且實驗2中同時考慮結(jié)構(gòu)權(quán)重和真實權(quán)重(尤其是取兩者中最小值)時也提高了網(wǎng)絡(luò)的鏈接預(yù)測效果，而且RALP指標的預(yù)測精度比RA指標和LP指標的高。

其中，每個數(shù)值都是將數(shù)據(jù)隨機獨立分成訓(xùn)練集和測試集進行10次實驗平均得到的，ε=0.001?！盁o權(quán)”、“結(jié)構(gòu)權(quán)重”、“真實權(quán)重”、“最小值權(quán)重”分別表示不含權(quán)重時、以結(jié)構(gòu)權(quán)重作為邊的權(quán)重時、以網(wǎng)絡(luò)本身含有的權(quán)重、取真實權(quán)重和結(jié)構(gòu)權(quán)重兩者中最小的值作為網(wǎng)絡(luò)中邊的權(quán)重時的鏈接預(yù)測。

3結(jié)論

本文中，我們根據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)權(quán)重(邊的簇系數(shù))，研究了3個相似性指標在7個真實網(wǎng)絡(luò)中的鏈接預(yù)測情況。研究發(fā)現(xiàn)，當網(wǎng)絡(luò)中考慮結(jié)構(gòu)權(quán)重信息時，可有效提高網(wǎng)絡(luò)的鏈接預(yù)測效果，而且RALP指標的預(yù)測精度優(yōu)于RA和LP指標。當加權(quán)網(wǎng)絡(luò)中同時考慮結(jié)構(gòu)權(quán)重和真實權(quán)重(尤其是取兩者中最小值)時也改善了網(wǎng)絡(luò)的鏈接預(yù)測效果。從實驗結(jié)果可知：結(jié)構(gòu)權(quán)重在提高網(wǎng)絡(luò)的鏈接預(yù)測過程中起了很重要的作用；而且加權(quán)RALP指標的預(yù)測效果也得到改善。

參考文獻：

[1]BoccalettiS,LatoraV,MorenoY,etal.ComplexNetworks:StructureandDynamics[J].PhysicsReports, 2006, 424(4): 175-308

[2]CostaLF,RodriguesFA,TraviesoG,etal.CharacterizationofComplexNetworks:ASurveyofMeasurements[J].AdvancesinPhysics, 2007, 56(1): 167-242

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

LüLinyuan.LinkPredictioninComplexNetworks[J].JournalofUniversityofElectronicScienceandTechnology, 2010, 39(5): 651-661 (inChinese)

[4]LüL,ZhouT.LinkPredictioninComplexNetworks:aSurvey[J].PhysicalA:StatisticalMachanicsandItsApplications, 2011, 290(6): 1150-1170

[5]O′MadadhainJ,HutchinsJ,SmythP.PredictionandRankingAlgorithmsforEvent-BasedNetworkData[C]∥ProceedingsofACMSIGKDD, 2005: 23-30

[6]BaiM,HuK,TangY.LinkPredictionBasedonaSemi-LocalSimilarityIndex[J].ChinesePhysicsB, 2011, 20(12): 128902

[7]MurataT,MoriyasuS.LinkPredictionofSocialNetworkBasedonWeightedProximityMeasures[C]∥ProceedingIEEE/WIC/ACMInternationalConferenceonWebIntelligence, 2007

[8]LüL,ZhouT.LinkPredictioninWeightedNetworks:TheRoleofWeakTies[J].EurophysicsLetters, 2010, 89(1): 18001

[9]WangL,HuK,TangY.RobustnessofLink-PredictionAlgorithmBasedonSimilarityandApplicationtoBiologicalNetworks[J].CurrentBioinformatics, 2014, 9(5): 1-7

[10]ZhouT,LüL,ZhangYC.PredictingMissingLinksViaLocalInformation[J].TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystem, 2009, 71(4): 623-630

[11]LüL,JinCH,ZhouT.SimilarityIndexBasedonLocalPathsforLinkPredictionofComplexNetworks[J].PhysicalReviewE, 2009, 80 (4):046122

收稿日期：2015-10-27

基金項目：國家自然科學(xué)基金(11571011)資助

作者簡介：李婷(1990—)，女，西北大學(xué)碩士研究生，主要從事機器學(xué)習(xí)研究。

中圖分類號：O212.1

文獻標志碼：A

文章編號:1000-2758(2016)03-0544-04

LinkPredictioninStructureWeight-BasedNetworks

LiTing1,ZhangHai1,2

1.School of Mathematics, Northwest University, Xi′an 710127, China 2.Institute of Applied Mathematics, Academy of Mathematics and System Sciences,Chinese Academy of Sciences,Beijing 100190,China

Abstract:In this paper, we try to study the link prediction problem of social network by treating the structure information as a transform function and transforming un-weighted network to weighted one. Further, for some weighted networks, we rethink their weights, and consider the real weights、structure weights as well as the combination of these two values as the weight of these networks respectively and study the link prediction problem of resource allocation along local path、resource allocation index and local path index in weighted networks. The experiments show that statistical method in structure weight-based networks has a well prediction effect. Simultaneously, weighted RALP also performs better than both the weighted RA and weighted LP.

Keywords:link prediction; structure weight; statistical method