李婷, 張海,2

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

?

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

李婷1, 張海1,2

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

摘要：研究社會(huì)網(wǎng)絡(luò)中邊的鏈接預(yù)測(cè)問(wèn)題，試圖根據(jù)網(wǎng)絡(luò)中邊的結(jié)構(gòu)權(quán)重信息，將無(wú)權(quán)網(wǎng)絡(luò)轉(zhuǎn)換為加權(quán)網(wǎng)絡(luò)進(jìn)行研究。進(jìn)而，對(duì)于一些加權(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ù)測(cè)情況。實(shí)驗(yàn)結(jié)果表明，文中所提統(tǒng)計(jì)方法有著良好的預(yù)測(cè)效果，而且加權(quán)RALP指標(biāo)的預(yù)測(cè)精度優(yōu)于加權(quán)RA指標(biāo)和加權(quán)LP指標(biāo)。

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

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

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

鏈接預(yù)測(cè)的許多算法已被應(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ù)測(cè)精度，但在共同作者網(wǎng)絡(luò)和美國(guó)航空網(wǎng)絡(luò)中加權(quán)指標(biāo)預(yù)測(cè)結(jié)果反而比無(wú)權(quán)的差，即所謂的“弱連接”效應(yīng)。Zhou等[8]研究了CN、AA、RA指標(biāo)以及其加權(quán)形式等在3個(gè)真實(shí)網(wǎng)絡(luò)中的預(yù)測(cè)效果，驗(yàn)證了鏈接預(yù)測(cè)問(wèn)題中存在的“弱連接”效應(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ù)測(cè)情況，實(shí)驗(yàn)結(jié)果表明，當(dāng)以邊的簇系數(shù)作為權(quán)重時(shí)，可以有效提高加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測(cè)精度。一個(gè)很自然的問(wèn)題是，能否將RALP指標(biāo)應(yīng)用于考慮結(jié)構(gòu)權(quán)重或者同時(shí)考慮結(jié)構(gòu)權(quán)重和真實(shí)權(quán)重信息時(shí)的網(wǎng)絡(luò)鏈接預(yù)測(cè)情況呢？

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

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

我們考慮簡(jiǎn)單無(wú)向網(wǎng)絡(luò)G(V,E)，其中V表示節(jié)點(diǎn)集，E表示邊集合，并且忽略節(jié)點(diǎn)間多邊信息和同一節(jié)點(diǎn)自連接信息。對(duì)于每一對(duì)節(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之間長(zhǎng)度為2的路徑數(shù)目，(A3)xy表示節(jié)點(diǎn)x和節(jié)點(diǎn)y之間長(zhǎng)度為3的路徑數(shù)目，ε=0.001為可調(diào)參數(shù)。

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

(3)

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

上述3個(gè)相似性指標(biāo)都是基于無(wú)權(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]的工作，分別對(duì)4個(gè)無(wú)權(quán)網(wǎng)絡(luò)和3個(gè)加權(quán)網(wǎng)絡(luò)進(jìn)行了研究。由于在真實(shí)世界中，一些網(wǎng)絡(luò)中的邊是不含權(quán)重信息的，所以為了研究和提高無(wú)權(quán)網(wǎng)絡(luò)的鏈接預(yù)測(cè)精度，以結(jié)構(gòu)權(quán)重作為網(wǎng)絡(luò)中邊的權(quán)重，研究RALP、RA和LP3個(gè)指標(biāo)的鏈接預(yù)測(cè)問(wèn)題。同時(shí)為了比較，也研究了無(wú)權(quán)網(wǎng)絡(luò)在不考慮結(jié)構(gòu)權(quán)重信息時(shí)的鏈接預(yù)測(cè)情況。其中結(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ù)測(cè)效果，我們分別以網(wǎng)絡(luò)的真實(shí)權(quán)重、結(jié)構(gòu)權(quán)重、兩者結(jié)合后的值作為邊的權(quán)重，研究RALP、RA、LP3個(gè)指標(biāo)的預(yù)測(cè)情況。其中分別采用3種方式結(jié)合真實(shí)權(quán)重和結(jié)構(gòu)權(quán)重：平均值法、最小值法、最大值法。

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

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

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

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

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

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

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

其中，每個(gè)數(shù)值都是將數(shù)據(jù)隨機(jī)獨(dú)立分成訓(xùn)練集和測(cè)試集進(jìn)行10次實(shí)驗(yàn)平均得到的，ε=0.001?！盁o(wú)權(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ù)測(cè)。

3結(jié)論

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

參考文獻(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ù)測(cè)[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)目：國(guó)家自然科學(xué)基金(11571011)資助

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

中圖分類號(hào)：O212.1

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

文章編號(hào):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