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

李婷, 張海,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)

摘要：研究社會(huì)網(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ò)進(jìn)行研究。進(jìn)而，對于一些加權(quán)網(wǎng)絡(luò)，重新考慮其權(quán)重，分別以真實(shí)權(quán)重、結(jié)構(gòu)權(quán)重以及將兩者結(jié)合后的值作為網(wǎng)絡(luò)中邊的權(quán)重，研究resource allocation along local path(RALP)等指標(biāo)、資源分配(RA)指標(biāo)和局部路徑(LP)指標(biāo)在加權(quán)網(wǎng)絡(luò)中的鏈接預(yù)測情況。實(shí)驗(yàn)結(jié)果表明，文中所提統(tǒng)計(jì)方法有著良好的預(yù)測效果，而且加權(quán)RALP指標(biāo)的預(yù)測精度優(yōu)于加權(quán)RA指標(biāo)和加權(quán)LP指標(biāo)。

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

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

(4)

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

(5)

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

(6)

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

(7)

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

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

2實(shí)驗(yàn)

選用UCI數(shù)據(jù)庫中來自不同領(lǐng)域的7個(gè)網(wǎng)絡(luò)，并忽略網(wǎng)絡(luò)中邊的方向。其中這7個(gè)網(wǎng)絡(luò)分別為：空手道俱樂部、海豚社會(huì)網(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ò)。實(shí)驗(yàn)1中將網(wǎng)絡(luò)結(jié)構(gòu)權(quán)重作為無權(quán)網(wǎng)絡(luò)的權(quán)重，作為比較，同時(shí)也研究在其不考慮結(jié)構(gòu)權(quán)重信息時(shí)的鏈接預(yù)測能力，結(jié)果如表1所示。

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

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

在實(shí)驗(yàn)2中，分別以網(wǎng)絡(luò)的真實(shí)權(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)重時(shí)，提高了網(wǎng)絡(luò)的鏈接預(yù)測精度，且實(shí)驗(yàn)2中同時(shí)考慮結(jié)構(gòu)權(quán)重和真實(shí)權(quán)重(尤其是取兩者中最小值)時(shí)也提高了網(wǎng)絡(luò)的鏈接預(yù)測效果，而且RALP指標(biāo)的預(yù)測精度比RA指標(biāo)和LP指標(biāo)的高。

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

3結(jié)論

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

參考文獻(xiàn)：

[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é)報(bào)，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

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

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

中圖分類號：O212.1

文獻(xiàn)標(biāo)志碼：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