基于結構加權網絡的鏈接預測

李婷, 張海,2

(1.西北大學 數學學院, 陜西 西安　710127；2.中國科學院 數學與系統科學院應用數學所, 北京　100190)

?

基于結構加權網絡的鏈接預測

李婷1, 張海1,2

(1.西北大學 數學學院, 陜西 西安710127；2.中國科學院 數學與系統科學院應用數學所, 北京100190)

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

關鍵詞：鏈接預測；結構權重；統計方法

復雜系統通常都可以通過網絡表示，其中節點表示系統中的個體或諸多對象，邊則表示個體或對象間的關系[1-2]。隨著互聯網的快速發展，形成了諸如Facebook、人人網、微博等社交網絡，使得人與人之間的交流變得更加便利。因此，開展此類數據分析，提取網絡特征是一項非常有意義的工作。網絡的社會分析也成為近年來統計學、計算機科學、物理學、社會科學等研究領域的一個熱點，其中鏈接預測是網絡分析中的一個基本問題。

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

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

本文中，我們將考慮網絡的結構權重信息，研究RALP等指標在這些真實網絡中的鏈接預測效果。通過研究，我們發現無論是無權網絡還是加權網絡，當其考慮結構權重信息時對于RALP、RA和LP指標都能有效提高網絡的鏈接預測效果，同時RALP指標的預測結果優于RA指標和LP指標。

1基于加權網絡的模型

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

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

(1)

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

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

(2)

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

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

(3)

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

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

1)加權RA(WRA)指標：

(4)

2)加權LP(WLP)指標：

(5)

3)加權RALP(WRALP)指標：

(6)

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

(7)

式中，Nij表示共同鄰居的個數。

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

2實驗

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

研究了無權網絡和加權網絡。實驗1中將網絡結構權重作為無權網絡的權重，作為比較，同時也研究在其不考慮結構權重信息時的鏈接預測能力，結果如表1所示。

表1　4個無權網絡在考慮結構權重時的鏈接預測結果比較

表2　3個加權網絡在考慮結構權重時的鏈接預測結果比較

在實驗2中，分別以網絡的真實權重、結構權重、兩者結合后的值作為邊的權重，結果如表2所示。

通過比較，發現以結構權重作為網絡邊的權重時，提高了網絡的鏈接預測精度，且實驗2中同時考慮結構權重和真實權重(尤其是取兩者中最小值)時也提高了網絡的鏈接預測效果，而且RALP指標的預測精度比RA指標和LP指標的高。

其中，每個數值都是將數據隨機獨立分成訓練集和測試集進行10次實驗平均得到的，ε=0.001。“無權”、“結構權重”、“真實權重”、“最小值權重”分別表示不含權重時、以結構權重作為邊的權重時、以網絡本身含有的權重、取真實權重和結構權重兩者中最小的值作為網絡中邊的權重時的鏈接預測。

3結論

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

參考文獻：

[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]呂琳媛. 復雜網路鏈接預測[J]. 電子科技大學學報，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

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

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

中圖分類號：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