楊 磊，李臣龍，汪 婧

基于社區(qū)信息的鏈接分析與預(yù)測(cè)研究

楊 磊，李臣龍，汪 婧

（安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽蕪湖 241000）

社區(qū)結(jié)構(gòu)是社交網(wǎng)絡(luò)最重要的拓?fù)涮匦灾?，有助于理解用戶分布和用戶行為，提高鏈接預(yù)測(cè)的精確度.通過(guò)分析社區(qū)結(jié)構(gòu)，結(jié)合貝葉斯理論，提出了一種新的基于社區(qū)信息的鏈接預(yù)測(cè)方法，并應(yīng)用于真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)中對(duì)未來(lái)鏈接進(jìn)行分析與預(yù)測(cè).實(shí)驗(yàn)演示了該方法的優(yōu)點(diǎn)和有效性，取得了很好的預(yù)測(cè)效果.

鏈接預(yù)測(cè)；社會(huì)網(wǎng)絡(luò)分析；社區(qū)結(jié)構(gòu)；鏈接分析

鏈接關(guān)系在數(shù)據(jù)挖掘中已經(jīng)成為了新的研究熱點(diǎn)，鏈接預(yù)測(cè)利用網(wǎng)絡(luò)歷史結(jié)構(gòu)信息來(lái)預(yù)測(cè)未來(lái)節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性.社交網(wǎng)絡(luò)作為一種圖結(jié)構(gòu)，對(duì)鏈接更加關(guān)注.通過(guò)鏈接預(yù)測(cè)方法可以預(yù)測(cè)未結(jié)交的用戶中哪些“應(yīng)該是朋友”［1］.此外，鏈接預(yù)測(cè)方法還可以應(yīng)用于預(yù)測(cè)一篇學(xué)術(shù)論文的類(lèi)型或合著者關(guān)系，發(fā)現(xiàn)網(wǎng)絡(luò)中恐怖分子的恐怖活動(dòng)信息以及預(yù)測(cè)手機(jī)用戶是否會(huì)切換運(yùn)營(yíng)商等領(lǐng)域.

鏈接預(yù)測(cè)問(wèn)題有兩種不同的解決策略，即：監(jiān)督的和無(wú)監(jiān)督的.無(wú)監(jiān)督鏈接預(yù)測(cè)方法有CN（Common neighbors）、AA（Adamic-Adar）等多種算法［2］，而基于監(jiān)督的鏈接預(yù)測(cè)方法通常是作為一個(gè)分類(lèi)問(wèn)題.大多數(shù)無(wú)監(jiān)督的和監(jiān)督的解決方案關(guān)注于開(kāi)發(fā)本地或全局結(jié)構(gòu)化網(wǎng)絡(luò)信息，其他的信息如社區(qū)信息等并沒(méi)有得到充分利用.為了改善鏈接預(yù)測(cè)精度，Hoseini［3］等提出了混合的方法，利用結(jié)構(gòu)化信息和社區(qū)信息進(jìn)行鏈接預(yù)測(cè)；Liaghat［4］等利用回歸分析模型預(yù)測(cè)社交網(wǎng)站用戶之間的鏈接關(guān)系，取得了較好的效果；Feng［5］等發(fā)現(xiàn)當(dāng)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)增長(zhǎng)時(shí)，基于結(jié)構(gòu)化信息的鏈接預(yù)測(cè)方法的精確度將會(huì)有很大提高.

本文基于社區(qū)信息對(duì)社交網(wǎng)絡(luò)進(jìn)行鏈接分析與預(yù)測(cè)，通過(guò)社區(qū)發(fā)現(xiàn)算法對(duì)社交網(wǎng)絡(luò)進(jìn)行了社區(qū)劃分，分析了網(wǎng)絡(luò)頂點(diǎn)在同一社區(qū)和不同社區(qū)對(duì)預(yù)測(cè)結(jié)果的影響，把新的方法應(yīng)用在社交網(wǎng)絡(luò)數(shù)據(jù)中，進(jìn)行了實(shí)驗(yàn)驗(yàn)證并與其他經(jīng)典鏈接預(yù)測(cè)算法做了對(duì)比，更好地實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)之間鏈接關(guān)系的預(yù)測(cè).

1　問(wèn)題描述與評(píng)價(jià)方法

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

為了衡量鏈接預(yù)測(cè)算法精確性，集合E被劃分為兩部分，即：訓(xùn)練集ET和測(cè)試集EP.顯然E=ET∪EP且ET∩EP=?.將訓(xùn)練集信息作為算法的輸入，然后將預(yù)測(cè)結(jié)果和測(cè)試集信息比較并根據(jù)評(píng)價(jià)指標(biāo)衡量預(yù)測(cè)算法性能.本文使用AUC［6］（Area Under the Receiver Operating Characteristic Curve）指標(biāo)來(lái)衡量算法的精確性.

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

顯然，當(dāng)所有分?jǐn)?shù)是獨(dú)立同分布時(shí)，AUC的值等于0.5，鏈接預(yù)測(cè)算法的測(cè)試精度可以用AUC大于0.5的程度來(lái)描述，AUC越大，算法精度越高.

2　基于社區(qū)信息的鏈接預(yù)測(cè)方法

假定網(wǎng)絡(luò)G中，存在M＞1個(gè)社區(qū)，分別用C1，C2，…，CM等標(biāo)簽表示.當(dāng)一個(gè)頂點(diǎn)x∈V屬于標(biāo)簽Ci的社區(qū)，則該頂點(diǎn)用xCi表示，其中i=1，2，…，M，每個(gè)頂點(diǎn)看作屬于一個(gè)單獨(dú)的社區(qū).

社區(qū)圖樣例如圖1所示.由圖1可知，圖1中有12個(gè)頂點(diǎn)和19條鏈接，為了標(biāo)識(shí)方便，每個(gè)頂點(diǎn)用數(shù)字和顏色做了標(biāo)識(shí)，同樣顏色的頂點(diǎn)屬于同一社區(qū).頂點(diǎn)從1～5屬于社區(qū)C1，用灰色表示；頂點(diǎn)6～8屬于社區(qū)C2，用白色表示；頂點(diǎn)9～12屬于社區(qū)C3，用黑色表示.

2.1社區(qū)發(fā)現(xiàn)算法

本文使用標(biāo)簽傳播算法（Label Propagation Algorithm，LPA）［7］作為社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)算法.LPA是一個(gè)簡(jiǎn)單快速且具有近于線性時(shí)間復(fù)雜度的社區(qū)發(fā)現(xiàn)方法，基本思路是用已標(biāo)記頂點(diǎn)的標(biāo)簽信息去預(yù)測(cè)未標(biāo)記節(jié)點(diǎn)的標(biāo)簽信息.

LPA為網(wǎng)絡(luò)圖中每個(gè)頂點(diǎn)分配一個(gè)標(biāo)簽，一對(duì)頂點(diǎn)所形成的鏈接表示頂點(diǎn)相似度，頂點(diǎn)標(biāo)簽按相似度傳播給其他頂點(diǎn)，并且該頂點(diǎn)標(biāo)簽為其大多數(shù)鄰近頂點(diǎn)的標(biāo)簽，相似頂點(diǎn)的標(biāo)簽越趨于一致，其標(biāo)簽越容易傳播.在標(biāo)簽傳播過(guò)程中，保持已標(biāo)注數(shù)據(jù)的標(biāo)簽不變，逐步傳向未標(biāo)注數(shù)據(jù).當(dāng)?shù)^(guò)程結(jié)束時(shí)，那些具有相同標(biāo)簽的頂點(diǎn)便組合構(gòu)成了同一個(gè)社區(qū)，從而完成標(biāo)簽傳播過(guò)程.

2.2鏈接預(yù)測(cè)方法

假設(shè)Γ（x）表示頂點(diǎn)x的鄰居頂點(diǎn)集合，Γ（y）表示頂點(diǎn)y的鄰居頂點(diǎn)集合，則Ax，y=Γ（x）∩Γ（y）表示未鏈接的頂點(diǎn)對(duì)（x，y）的共同鄰居集合.根據(jù)貝葉斯理論，為頂點(diǎn)對(duì)（x，y）分配相同社區(qū)標(biāo)簽Ci的條件概率為：

同理，為頂點(diǎn)對(duì)（x，y）分配不同社區(qū)標(biāo)簽Ci和Cj的條件概率為：

根據(jù)式（2）和式（3）很難獨(dú)立確定頂點(diǎn)對(duì)（x，y）是在相同社區(qū)標(biāo)簽下還是在不同社區(qū)標(biāo)簽下更有可能存在鏈接.假設(shè)是具有相同社區(qū)標(biāo)簽的共同鄰居的集合是具有不同社區(qū)標(biāo)簽的共同鄰居集合，則，顯然

具有同一社區(qū)標(biāo)簽的共同鄰居數(shù)量越多，頂點(diǎn)x和y越有可能屬于該社區(qū).則頂點(diǎn)（x，y）具有相同社區(qū)標(biāo)簽Ci的共同鄰居的概率可以定義為具有同一社區(qū)標(biāo)簽的共同鄰居的數(shù)量除以共同鄰居總數(shù)量，方程如下：

同理，頂點(diǎn)（x，y）具有不同社區(qū)標(biāo)簽Ci和Cj的共同鄰居的概率可以定義為屬于不同社區(qū)標(biāo)簽共同鄰居的數(shù)量除以共同鄰居的總數(shù)量，方程如下：

為了預(yù)測(cè)節(jié)點(diǎn)對(duì)（x，y）之間鏈接存在的可能性，定義分?jǐn)?shù)Sx，y作為式（2）和式（3）的比率，分別代入式（4）和式（5），可以得到方程如下：

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

3　實(shí)驗(yàn)方案

3.1實(shí)驗(yàn)數(shù)據(jù)

采用3種具有代表性的社交網(wǎng)絡(luò)，即：Sina微博、Twitter和Facebook.Sina微博數(shù)據(jù)來(lái)源于數(shù)據(jù)堂［8］，后兩種社交網(wǎng)絡(luò)數(shù)據(jù)均來(lái)源于Stanford［9］，它們的網(wǎng)絡(luò)拓?fù)湫再|(zhì)如表1所示.其中，|V|表示網(wǎng)絡(luò)頂點(diǎn)數(shù)，|E|表示網(wǎng)絡(luò)邊數(shù)，C為平均網(wǎng)絡(luò)聚集系數(shù).

表1　實(shí)驗(yàn)數(shù)據(jù)網(wǎng)絡(luò)拓?fù)湫再|(zhì)

3.2實(shí)驗(yàn)結(jié)果與分析

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

在算法效率方面，CN和AA算法的時(shí)間復(fù)雜度均為O（N2）.本文社區(qū)發(fā)現(xiàn)算法的時(shí)間復(fù)雜度為O（N），計(jì)算AUC的時(shí)間復(fù)雜度為O（K?M），計(jì)算S?x，y的時(shí)間復(fù)雜度是O（（M+N）?N），所以總體上本文方法的時(shí)間復(fù)雜度為O（N2）（N是初始網(wǎng)絡(luò)G的節(jié)點(diǎn)數(shù)；M是鏈接數(shù)；K表示網(wǎng)絡(luò)中不存在的鏈接數(shù)）.因此，在保證算法復(fù)雜度的情況下，取得了較好的預(yù)測(cè)效果.

4　結(jié)論

在鏈接分析與預(yù)測(cè)理論基礎(chǔ)上，提出了基于社區(qū)信息的鏈接分析與預(yù)測(cè)方法.考慮了同一社區(qū)和不同社區(qū)間網(wǎng)絡(luò)頂點(diǎn)的相互關(guān)系，對(duì)3個(gè)不同社交網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明，新算法的預(yù)測(cè)準(zhǔn)確性有所提高.當(dāng)然，隨著復(fù)雜社交網(wǎng)絡(luò)的快速發(fā)展，鏈接預(yù)測(cè)在大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的分析應(yīng)用還有待更進(jìn)一步深入研究.

［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］ 呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)［J］.電子科技大學(xué)學(xué)報(bào)，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］ 數(shù)據(jù)堂.科學(xué)數(shù)據(jù)共享平臺(tái)［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

安徽省高校省級(jí)優(yōu)秀青年人才重點(diǎn)基金資助項(xiàng)目（2013SQRL034ZD），安徽工程大學(xué)校青年基金資助項(xiàng)目（2009YQ040）

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