郭婷婷，趙承業(yè)

(中國計量學(xué)院 理學(xué)院， 浙江 杭州 310018)

?

基于共同鄰居的鏈路預(yù)測新指標(biāo)

郭婷婷，趙承業(yè)

(中國計量學(xué)院 理學(xué)院， 浙江 杭州 310018)

【摘要】提出一個新的鏈路預(yù)測相似性指標(biāo)——局部社團(tuán)結(jié)構(gòu)指標(biāo)(Local Community Structure，LCS).在已知網(wǎng)絡(luò)局部信息的前提下，LCS指標(biāo)刻畫了網(wǎng)絡(luò)中任意兩個節(jié)點的共同鄰居節(jié)點與這兩個節(jié)點的聚集關(guān)系.在基于真實網(wǎng)絡(luò)的實驗中，我們計算并比較了CN、AA、RA和LCS四個指標(biāo)在7個不同真實網(wǎng)絡(luò)中的AUC評價指標(biāo)，發(fā)現(xiàn)在簇系數(shù)較大的真實網(wǎng)絡(luò)中LCS指標(biāo)的預(yù)測結(jié)果好于其他三個指標(biāo).

【關(guān)鍵詞】鏈路預(yù)測；局部相似性；社團(tuán)結(jié)構(gòu)；AUC評價指標(biāo)；簇系數(shù)

網(wǎng)絡(luò)中的鏈路預(yù)測是指如何通過已知的網(wǎng)絡(luò)節(jié)點以及網(wǎng)絡(luò)結(jié)構(gòu)等信息，預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個節(jié)點之間產(chǎn)生連接的可能性[1].鏈路預(yù)測在很多領(lǐng)域受到廣泛關(guān)注，實現(xiàn)鏈路預(yù)測的方法也有很多，可以從不同的角度對網(wǎng)絡(luò)中的已知數(shù)據(jù)盡可能地進(jìn)行刻畫.在計算機(jī)領(lǐng)域，鏈路預(yù)測的研究思路和方法主要基于馬爾科夫鏈和機(jī)器學(xué)習(xí)，后來Zhu[2]等人將馬爾科夫鏈的預(yù)測方法擴(kuò)展到了WWW網(wǎng)絡(luò)的預(yù)測中；之后，應(yīng)用節(jié)點屬性的預(yù)測方法在實驗中得到了很好的預(yù)測效果，Lin[3]基于節(jié)點的屬性定義了節(jié)點間的相似性，可以直接用來進(jìn)行鏈路預(yù)測.但是在很多情況下這些屬性信息的獲取非常困難，而且即使獲得了節(jié)點的屬性信息也很難保證信息的可靠性(可信性)；相比節(jié)點的屬性信息，網(wǎng)絡(luò)的結(jié)構(gòu)信息更容易獲得、更可靠，所以基于網(wǎng)絡(luò)結(jié)構(gòu)的預(yù)測方法在最近幾年越來越受關(guān)注.其中，基于網(wǎng)絡(luò)局部信息進(jìn)行鏈路預(yù)測的方法比較常用，基于局部信息的相似性指標(biāo)[4]是指那些只通過節(jié)點局部信息即可計算得到的相似性指標(biāo)，基于共同鄰居的相似性指標(biāo)很多學(xué)者從不同方面構(gòu)造了不同的指標(biāo)來進(jìn)行相似性檢驗.在此，我們提出局部社團(tuán)結(jié)構(gòu)指標(biāo)這一鏈路預(yù)測新指標(biāo).

1鏈路預(yù)測

網(wǎng)絡(luò)是一個包含大量個體及個體間相互作用的系統(tǒng)，是把某種現(xiàn)象或關(guān)系抽象為個體(節(jié)點)及個體之間相互作用(邊)而形成的用來描述這一現(xiàn)象或關(guān)系的圖.對任意真實網(wǎng)絡(luò)我們能得到一個觀測網(wǎng)絡(luò)，但在記錄網(wǎng)絡(luò)的過程中由于信息的不完全性，觀測網(wǎng)絡(luò)往往會有鏈路的缺失問題：1).實際存在但未被探測到(信息丟失)；2).暫時不存在但應(yīng)該存在或很可能存在(涉及私密刻意隱藏).網(wǎng)絡(luò)中的鏈路預(yù)測[1,5]就是通過已知的網(wǎng)絡(luò)節(jié)點以及網(wǎng)絡(luò)結(jié)構(gòu)等信息來預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個節(jié)點之間產(chǎn)生連接的可能性.

Γ(x)：節(jié)點x的所有鄰居節(jié)點集合；

z:z∈Γ(x)∩Γ(y)，節(jié)點x,y的共同鄰居；

cxz：節(jié)點x與節(jié)點z共同的鄰居數(shù)；

dx：節(jié)點x的度；

rxz：節(jié)點x與z的緊密性；

sxy：節(jié)點x與y的相似性.

2基于共同鄰居的相似性指標(biāo)

基于網(wǎng)絡(luò)局部結(jié)構(gòu)信息的具有代表性的相似性指標(biāo)主要有：

1)CN[6]，兩節(jié)點間共同鄰居數(shù)越多，相似性越大；

2)AA[7]，度小的共同鄰居節(jié)點的貢獻(xiàn)要大于度大的共同鄰居節(jié)點；

3)RA[8]，該指標(biāo)來源于資源傳遞過程中共同鄰居作為媒介實行的一個平均分配.

2.1CN指標(biāo)(Common Neighbor)

在鏈路預(yù)測中應(yīng)用CN指標(biāo)的基本假設(shè)是，兩個未連接的節(jié)點如果有更多的共同鄰居，則它們更傾向于連邊.CN指標(biāo)被定義為

即兩節(jié)點之間的相似性就等于它們共同的鄰居數(shù).

2.2AA指標(biāo)(Adamic-Adar)

Adamic-Adar為每個共同鄰居節(jié)點賦予了一個權(quán)重：該鄰居節(jié)點度的對數(shù)的倒數(shù)，他們將AA指標(biāo)定義為

該指標(biāo)的意思是兩個節(jié)點都與一個度比較小的節(jié)點相連，那么這兩個節(jié)點相連的概率將會增大.即度小的共同鄰居節(jié)點的貢獻(xiàn)要大于度大的共同鄰居節(jié)點，例如在社交網(wǎng)絡(luò)中，共同關(guān)注一個比較冷門的人或物的兩個人之間相連的概率往往會比關(guān)注同一個關(guān)注度較高的人或事物的兩個人之間相連的概率要高.

2.3RA指標(biāo)(Resource Allocation)

這是周濤[8]等人提出的資源分配指標(biāo)，該指標(biāo)考慮的是未直接相連的兩個節(jié)點之間的資源傳遞過程，它們的共同鄰居節(jié)點作為傳遞的媒介.RA指標(biāo)也是考慮兩個節(jié)點共同鄰居的度的信息，與AA指標(biāo)有異曲同工之妙.周濤等人為每個共同鄰居節(jié)點賦予了一個權(quán)重值：該鄰居節(jié)點度的倒數(shù)，他們將RA指標(biāo)定義為

RA指標(biāo)相對AA指標(biāo)來說，只是賦予共同鄰居節(jié)點權(quán)重的方式不同，當(dāng)網(wǎng)絡(luò)的平均度較大的時候兩者的效果才會顯示較大的區(qū)別.

3LCS指標(biāo)的構(gòu)建

社團(tuán)結(jié)構(gòu)[9]是指網(wǎng)絡(luò)由很多社團(tuán)構(gòu)成，社團(tuán)內(nèi)部連邊緊密，社團(tuán)之間連邊甚少.通過研究網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，可以揭示網(wǎng)絡(luò)功能性模塊組成結(jié)構(gòu)，刻畫網(wǎng)絡(luò)具有的某些重要性質(zhì).眾多學(xué)者對劃分網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的算法進(jìn)行了大量的研究.

網(wǎng)絡(luò)中任意兩節(jié)點之間的相似性和它們之間的局部結(jié)構(gòu)密度具有一定的關(guān)聯(lián)度.而社團(tuán)結(jié)構(gòu)刻畫節(jié)點之間的親疏關(guān)系.將社團(tuán)結(jié)構(gòu)的思想引入鏈路預(yù)測，考察兩個節(jié)點的每一個共同鄰居節(jié)點與這兩個節(jié)點本身構(gòu)成的局部結(jié)構(gòu)的親疏關(guān)系，可以構(gòu)造新的鏈路預(yù)測算法.

3.1LCS指標(biāo)(Local Community Structure)

受網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的啟發(fā)，由節(jié)點x，y及其所有鄰居節(jié)點組成的小網(wǎng)絡(luò)中，定義共同鄰居節(jié)點z與節(jié)點x，y的歸屬關(guān)系分別為

rxz表示節(jié)點z和由z，x共同鄰居組成的局部結(jié)構(gòu)之間的親疏關(guān)系，值越大表明關(guān)系越密切.

我們定義如下的LCS指標(biāo)：

顯然，LCS指標(biāo)刻畫了基于每一個共同鄰居構(gòu)成的局部結(jié)構(gòu)相似程度的節(jié)點相似性.

3.2LCS指標(biāo)的矩陣計算

根據(jù)呂林媛和周濤在文獻(xiàn)[4]中給出的鏈路預(yù)測實驗方案和基于相似性的鏈路預(yù)測程序，我們首先給出LCS的矩陣計算方式(Matlab語言).

將觀測網(wǎng)絡(luò)中的連邊隨機(jī)劃分為訓(xùn)練集ET和測試集EP，E=ET+EP，且ET∩EP=φ.隨機(jī)選取90%的邊作為訓(xùn)練集，剩余10%的邊作為測試集，通過AUC評價指標(biāo)來計算各算法的預(yù)測精度.對不同的指標(biāo)在不同真實網(wǎng)絡(luò)中的預(yù)測精度100次隨機(jī)實驗取平均.

因為

則有如下相似度矩陣計算的Matlab語句:

3.3真實網(wǎng)絡(luò)數(shù)據(jù)

我們在如下7個真實網(wǎng)絡(luò)中計算LCS指標(biāo)及相關(guān)的三個指標(biāo)(CN、AA、RA)的預(yù)測精確度(以AUC指標(biāo)衡量).實驗基本參數(shù)設(shè)置、測試主程序、相關(guān)的三個指標(biāo)(CN、AA、RA)的實現(xiàn)均采用文獻(xiàn)[5]的標(biāo)準(zhǔn).

表1　真實網(wǎng)絡(luò)數(shù)據(jù)

網(wǎng)絡(luò)的簇系數(shù)[10](在圖論中也叫集聚系數(shù))，該系數(shù)通常用來刻畫網(wǎng)絡(luò)的局域結(jié)構(gòu)性質(zhì)，上述網(wǎng)絡(luò)根據(jù)簇系數(shù)，可大概分為兩類：前五個網(wǎng)絡(luò)的集聚性表現(xiàn)得較為明顯，可視為一些具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)；而路由器網(wǎng)絡(luò)和美國西部電力網(wǎng)具有明顯的稀疏性，不僅簇系數(shù)很低，網(wǎng)絡(luò)節(jié)點的平均度也很小.

3.4實驗結(jié)果

我們將上述四個相似性指標(biāo)在7個真實網(wǎng)絡(luò)中的預(yù)測精確度(AUC指標(biāo)衡量)記錄在表2中.

表2　預(yù)測精確度比較(AUC)

從上表中可以看出LCS指標(biāo)在前五個網(wǎng)絡(luò)中的預(yù)測精確度(AUC指標(biāo)衡量)好于其他三個指標(biāo)，而在后兩個網(wǎng)絡(luò)中表現(xiàn)平平.

4結(jié)論

網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)是內(nèi)部聯(lián)系高度聚集，外部聯(lián)系相對稀疏的網(wǎng)絡(luò)局部結(jié)構(gòu).一個網(wǎng)絡(luò)的簇系數(shù)越高，說明該網(wǎng)絡(luò)在某種意義下的聚集度越高.網(wǎng)絡(luò)中兩個節(jié)點x和y的LCS指標(biāo)刻畫了它們的所有共同鄰居z屬于x和z(y和z)構(gòu)成的局部結(jié)構(gòu)的聚集程度.因此，我們分析LCS指標(biāo)可以在一些簇系數(shù)較高的真實網(wǎng)絡(luò)中具有較好的預(yù)測效果.

對7個擁有不同簇系數(shù)的真實網(wǎng)絡(luò)仿真實驗表明我們的分析是合理的，LCS指標(biāo)能夠在簇系數(shù)較大的網(wǎng)絡(luò)中提高鏈路預(yù)測的精確度.

【參考文獻(xiàn)】

[1]呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J].電子科技大學(xué)學(xué)報，2010,39(5):651-661.

LYU Linyuan. Link prediction in complex networks[J]. Journal of University of Electronic Science and Technology,2010,39(5):651-661.

[2]ZHU J, HONG J, HUGHES J G. Soft-Ware 2002:Computing in an Imperfect World[M]. Berlin Heidelberg: Springer,2002:60-73.

[3]LIN D. An information-theoretic definition of similarity[C]// Proceedings of the Fifteenth International Conference on Machine Learning. San Francisco: Morgan Kaufman Publishers,1998:296-304.

[4]NOWELL D L, KLEINBERG J. The link-prediction problem for social networks[J]. Journal of American Society for Information Science and Technology,2007,58(7):1019-1031.

[5]呂琳媛,周濤.鏈路預(yù)測[M].北京：高等教育出版社,2013：8.

[6]LORRAIN F, WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematics Sociology,1971,1(1):49-80.

[7]ADAMIC L A, ADAR E. Friends and neighbors on the web[J].Social Networks,2003,25(3):211-230.

[8]ZHOU T, LYU L, ZHANG Y C. Predicting missing links via local information[J]. The European Physical Journal B,2009,71(4):623-630.

[9]郭世澤,陸哲明.復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論[M].北京：科學(xué)出版社,2012:265-270.

[10]FENG X, ZHAO J C, XU K. Link prediction in complex networks: a clustering perspective[J].The European Physical Journal B-Condensed Matter and Complex Systems,2012,85(1):1-9.

A new measurement of link prediction based on common neighbors

GUO Tingting，ZHAO Chengye

(College of Sciences, China Jiliang University, Hangzhou 310018, China)

Abstract:We presented a new similarity measurement, the local community structure(LCS)in networks. Under the premise of local information on networks, the LCS measurement characterized the relationship between any two nodes in a network with their common neighbors. By a comparison of AUC, CN, AA, RA and LCS in seven real networks, we found that the accuracy of LCS was better than the other three measurements in the networks with big clustering coefficients.

Key words:link prediction; local similarity; community structure; AUC; clustering coefficient

【文章編號】1004-1540(2015)01-0121-04

DOI:10.3969/j.issn.1004-1540.2016.01.022

【收稿日期】2015-09-23《中國計量學(xué)院學(xué)報》網(wǎng)址：zgjl.cbpt.vnki.net

【基金項目】國家自然科學(xué)基金面上項目(No. 61173002)，浙江省自然科學(xué)基金資助項目(No. LY14F020040).

【作者簡介】郭婷婷(1991-)，女，山西省平遙人，碩士研究生，主要研究方向為圖論、算法設(shè)計與分析、復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測．

【中圖分類號】TN711;O157.6

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

Email：tean_g@163. com

通信聯(lián)系人：趙承業(yè)，男，副教授.Email: cyzhao@cjlu. edu. cn