基于社區信息的鏈接分析與預測研究

楊 磊，李臣龍，汪 婧

基于社區信息的鏈接分析與預測研究

楊 磊，李臣龍，汪 婧

（安徽工程大學計算機與信息學院，安徽蕪湖 241000）

社區結構是社交網絡最重要的拓撲特性之一，有助于理解用戶分布和用戶行為，提高鏈接預測的精確度.通過分析社區結構，結合貝葉斯理論，提出了一種新的基于社區信息的鏈接預測方法，并應用于真實的社交網絡數據中對未來鏈接進行分析與預測.實驗演示了該方法的優點和有效性，取得了很好的預測效果.

鏈接預測；社會網絡分析；社區結構；鏈接分析

鏈接關系在數據挖掘中已經成為了新的研究熱點，鏈接預測利用網絡歷史結構信息來預測未來節點之間產生鏈接的可能性.社交網絡作為一種圖結構，對鏈接更加關注.通過鏈接預測方法可以預測未結交的用戶中哪些“應該是朋友”［1］.此外，鏈接預測方法還可以應用于預測一篇學術論文的類型或合著者關系，發現網絡中恐怖分子的恐怖活動信息以及預測手機用戶是否會切換運營商等領域.

鏈接預測問題有兩種不同的解決策略，即：監督的和無監督的.無監督鏈接預測方法有CN（Common neighbors）、AA（Adamic-Adar）等多種算法［2］，而基于監督的鏈接預測方法通常是作為一個分類問題.大多數無監督的和監督的解決方案關注于開發本地或全局結構化網絡信息，其他的信息如社區信息等并沒有得到充分利用.為了改善鏈接預測精度，Hoseini［3］等提出了混合的方法，利用結構化信息和社區信息進行鏈接預測；Liaghat［4］等利用回歸分析模型預測社交網站用戶之間的鏈接關系，取得了較好的效果；Feng［5］等發現當網絡社區結構增長時，基于結構化信息的鏈接預測方法的精確度將會有很大提高.

本文基于社區信息對社交網絡進行鏈接分析與預測，通過社區發現算法對社交網絡進行了社區劃分，分析了網絡頂點在同一社區和不同社區對預測結果的影響，把新的方法應用在社交網絡數據中，進行了實驗驗證并與其他經典鏈接預測算法做了對比，更好地實現了對網絡節點之間鏈接關系的預測.

1　問題描述與評價方法

對于社交網絡定義網絡圖G（V，E），其中V為網絡圖的頂點集合，E為網絡圖中邊的集合，即鏈接集合.假設|V|表示V集合中的頂點數量，則V集合中頂點之間所有可能的鏈接數量為|V|（|V|-1）/2條，記為全集U，則網絡中屬于U但不屬于E的鏈接即為不存在的鏈接，記為U-E.鏈接預測方法的基本任務是在集合U-E中找出可能存在的鏈接，為每個可能的鏈接指派一個分數并降序排列.假定可能鏈接的頂點對（x，y）∈（U-E），則該分數記為Sx，y.分數Sx，y值越高，則頂點對（x，y）間鏈接存在的可能性越大.

為了衡量鏈接預測算法精確性，集合E被劃分為兩部分，即：訓練集ET和測試集EP.顯然E=ET∪EP且ET∩EP=?.將訓練集信息作為算法的輸入，然后將預測結果和測試集信息比較并根據評價指標衡量預測算法性能.本文使用AUC［6］（Area Under the Receiver Operating Characteristic Curve）指標來衡量算法的精確性.

AUC表示測試集中的邊的分數值比隨機選擇的一個不存在的邊的分數值高的概率，即每次隨機從測試集中選取一條邊與隨機選擇的不存在的邊進行比較，如果測試集中邊的分數值大于不存在的邊的分數值，就加1分；如果兩個分數值相等，就加0.5分.假定n是獨立比較的次數，如果有n′次測試集中的邊的分數值大于不存在的邊的分數，有n″次兩分數值相等，則AUC的值為：

顯然，當所有分數是獨立同分布時，AUC的值等于0.5，鏈接預測算法的測試精度可以用AUC大于0.5的程度來描述，AUC越大，算法精度越高.

2　基于社區信息的鏈接預測方法

假定網絡G中，存在M＞1個社區，分別用C1，C2，…，CM等標簽表示.當一個頂點x∈V屬于標簽Ci的社區，則該頂點用xCi表示，其中i=1，2，…，M，每個頂點看作屬于一個單獨的社區.

社區圖樣例如圖1所示.由圖1可知，圖1中有12個頂點和19條鏈接，為了標識方便，每個頂點用數字和顏色做了標識，同樣顏色的頂點屬于同一社區.頂點從1～5屬于社區C1，用灰色表示；頂點6～8屬于社區C2，用白色表示；頂點9～12屬于社區C3，用黑色表示.

2.1社區發現算法

本文使用標簽傳播算法（Label Propagation Algorithm，LPA）［7］作為社交網絡中的社區發現算法.LPA是一個簡單快速且具有近于線性時間復雜度的社區發現方法，基本思路是用已標記頂點的標簽信息去預測未標記節點的標簽信息.

LPA為網絡圖中每個頂點分配一個標簽，一對頂點所形成的鏈接表示頂點相似度，頂點標簽按相似度傳播給其他頂點，并且該頂點標簽為其大多數鄰近頂點的標簽，相似頂點的標簽越趨于一致，其標簽越容易傳播.在標簽傳播過程中，保持已標注數據的標簽不變，逐步傳向未標注數據.當迭代過程結束時，那些具有相同標簽的頂點便組合構成了同一個社區，從而完成標簽傳播過程.

2.2鏈接預測方法

假設Γ（x）表示頂點x的鄰居頂點集合，Γ（y）表示頂點y的鄰居頂點集合，則Ax，y=Γ（x）∩Γ（y）表示未鏈接的頂點對（x，y）的共同鄰居集合.根據貝葉斯理論，為頂點對（x，y）分配相同社區標簽Ci的條件概率為：

同理，為頂點對（x，y）分配不同社區標簽Ci和Cj的條件概率為：

根據式（2）和式（3）很難獨立確定頂點對（x，y）是在相同社區標簽下還是在不同社區標簽下更有可能存在鏈接.假設是具有相同社區標簽的共同鄰居的集合是具有不同社區標簽的共同鄰居集合，則，顯然

具有同一社區標簽的共同鄰居數量越多，頂點x和y越有可能屬于該社區.則頂點（x，y）具有相同社區標簽Ci的共同鄰居的概率可以定義為具有同一社區標簽的共同鄰居的數量除以共同鄰居總數量，方程如下：

同理，頂點（x，y）具有不同社區標簽Ci和Cj的共同鄰居的概率可以定義為屬于不同社區標簽共同鄰居的數量除以共同鄰居的總數量，方程如下：

為了預測節點對（x，y）之間鏈接存在的可能性，定義分數Sx，y作為式（2）和式（3）的比率，分別代入式（4）和式（5），可以得到方程如下：

當Ci=Cj時，P（xCi，yCi）/（P（xCi，yCj）值為1，此時可得到=?，則Sx，y=0.當時，則AIx，y=?，為了避免分母為0，把替換為Ax，y.根據Ax，y=∪，總體上該替換不改變鏈接預測的結果，可得方程如下：

3　實驗方案

3.1實驗數據

采用3種具有代表性的社交網絡，即：Sina微博、Twitter和Facebook.Sina微博數據來源于數據堂［8］，后兩種社交網絡數據均來源于Stanford［9］，它們的網絡拓撲性質如表1所示.其中，|V|表示網絡頂點數，|E|表示網絡邊數，C為平均網絡聚集系數.

表1　實驗數據網絡拓撲性質

3.2實驗結果與分析

實驗中編程語言：Java，CPU：Intel Xeon E5504，內存：8G.隨機選取實驗數據集中90%的鏈接作為訓練集，其余10%的鏈接為測試集，對訓練集使用本文所提方法進行鏈接預測.通過與經典算法CN、AA對比，根據AUC評估方法，實驗執行10次且進行5次隨機選取訓練集和測試集并且計算AUC平均值，結果如圖2所示.從圖2可以看出，本文方法在Sina微博和Facebook取得了最好的預測準確率，在Twitter網絡預測準確率僅次于CN算法.通過分析10次AUC值的標準差，結果如圖3所示.從圖3可以看出，本文方法在Twitter數據集上標準差最小，意味著每次執行結果值與平均值較近，預測算法穩定性最好；其中，在Sina微博數據集中的標準差最大，表明本算法在該數據集雖然取得了較高的預測準確率，但預測結果準確性并不穩定.各個算法在不同數據集上的運行時間對比如圖4所示.

在算法效率方面，CN和AA算法的時間復雜度均為O（N2）.本文社區發現算法的時間復雜度為O（N），計算AUC的時間復雜度為O（K?M），計算S?x，y的時間復雜度是O（（M+N）?N），所以總體上本文方法的時間復雜度為O（N2）（N是初始網絡G的節點數；M是鏈接數；K表示網絡中不存在的鏈接數）.因此，在保證算法復雜度的情況下，取得了較好的預測效果.

4　結論

在鏈接分析與預測理論基礎上，提出了基于社區信息的鏈接分析與預測方法.考慮了同一社區和不同社區間網絡頂點的相互關系，對3個不同社交網絡數據集進行了實驗.實驗結果表明，新算法的預測準確性有所提高.當然，隨著復雜社交網絡的快速發展，鏈接預測在大規模網絡數據的分析應用還有待更進一步深入研究.

［1］ D Sharma，U Sharma，S K Khatri.An experimental comparison of link prediction techniques in social networks［J］.Int J Model Optim，2014，4（1）：21-24.

［2］ 呂琳媛.復雜網絡鏈路預測［J］.電子科技大學學報，2010，39（5）：651-661.

［3］ E Hoseini，S Hashemi，A Hamzeh.SPCF：a stepwise partitioning for collaborative filtering to alleviate sparsity problems［J］.Journal of Information Science，2012，38（6）：578-592.

［4］ Z Liaghat，A H Rasekh，A Mahdavi.Application of data mining methods for link prediction in social networks［J］.Social Network Analysis and Mining，2013，3（2）：143-150.

［5］ X Feng，J C Zhao，K Xu.Link prediction in complex networks：a clustering perspective［J］.The European Physical Journal B，2012，85（1）：1-9.

［6］ J A Hanley，B J Mc Neil.The meaning and use of the area under a receiver operating characteristic（ROC）curve［J］.Radiology，1982，143（1）：29-36.

［7］ U N Raghavan，R Albert，S Kumara.Near linear time algorithm to detect community structures in large-scale networks［J］.Physical Review E，2007，76（3）：1-11.

［8］ 數據堂.科學數據共享平臺［EB/OL］.http：//www.datatang.com.［2014-05-11］.

［9］ J Leskovec.Stanford large network dataset collection［EB/OL］.http：//snap.stanford.edu/data/index.html.［2012-11-08］.

Research on link analysis and prediction based on community information

YANG Lei，LI Chen-long，WANG Jing
（College of Computer and Information，Anhui Polytechnic University，Wuhu 241000，China）

Community structure is one of the most important social network topological characteristics，which can help to understand the distributions and behaviors of users，and improve the accuracy of the link prediction.By analyzing the community structure，according to Bayesian theory，a new method of link prediction based on community information is proposed，applied to several real social network datasets for predicting and analyzing the future link.The experiment demonstrates the advantages and effectiveness of this method，which achieves a good prediction performance.

link prediction；social network analysis；community structure；link analysis

TP391

A

1672-2477（2015）02-0060-04

2014-07-28

安徽省高校省級優秀青年人才重點基金資助項目（2013SQRL034ZD），安徽工程大學校青年基金資助項目（2009YQ040）

楊 磊（1982-），男，安徽臨泉人，講師，碩士.