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

郭婷婷，趙承業(yè)

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

?

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

郭婷婷，趙承業(yè)

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

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

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

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

1鏈路預(yù)測

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RA指標(biāo)相對(duì)AA指標(biāo)來說，只是賦予共同鄰居節(jié)點(diǎn)權(quán)重的方式不同，當(dāng)網(wǎng)絡(luò)的平均度較大的時(shí)候兩者的效果才會(huì)顯示較大的區(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é)者對(duì)劃分網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的算法進(jìn)行了大量的研究.

網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)之間的相似性和它們之間的局部結(jié)構(gòu)密度具有一定的關(guān)聯(lián)度.而社團(tuán)結(jié)構(gòu)刻畫節(jié)點(diǎn)之間的親疏關(guān)系.將社團(tuán)結(jié)構(gòu)的思想引入鏈路預(yù)測，考察兩個(gè)節(jié)點(diǎn)的每一個(gè)共同鄰居節(jié)點(diǎn)與這兩個(gè)節(jié)點(diǎn)本身構(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é)點(diǎn)x，y及其所有鄰居節(jié)點(diǎn)組成的小網(wǎng)絡(luò)中，定義共同鄰居節(jié)點(diǎn)z與節(jié)點(diǎn)x，y的歸屬關(guān)系分別為

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

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

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

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

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

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

因?yàn)?/p>

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

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

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

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

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

3.4實(shí)驗(yàn)結(jié)果

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

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

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

4結(jié)論

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

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

【參考文獻(xiàn)】

[1]呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J].電子科技大學(xué)學(xué)報(bào)，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

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

DOI:10.3969/j.issn.1004-1540.2016.01.022

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

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

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

【中圖分類號(hào)】TN711;O157.6

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

Email：tean_g@163. com

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