李旗旗，徐 敏

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

社交網(wǎng)絡(luò)中的鏈路預(yù)測(cè)方法改進(jìn)

李旗旗，徐 敏

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

社交網(wǎng)絡(luò)在近些年得到了迅速發(fā)展，如今各個(gè)行業(yè)都在努力加入社交元素，如何提高鏈路預(yù)測(cè)方法在社交網(wǎng)絡(luò)中的預(yù)測(cè)準(zhǔn)確度成為一個(gè)熱門研究方向。鏈路預(yù)測(cè)方法由于網(wǎng)絡(luò)結(jié)構(gòu)的不同會(huì)表現(xiàn)出不同的預(yù)測(cè)效果，因此可以根據(jù)社交網(wǎng)絡(luò)的結(jié)構(gòu)特性對(duì)鏈路預(yù)測(cè)方法進(jìn)行改進(jìn)，從而提高在社交網(wǎng)絡(luò)中的預(yù)測(cè)準(zhǔn)確度。社交網(wǎng)絡(luò)是對(duì)人與人之間某種社會(huì)關(guān)系的描述，因此和其他復(fù)雜網(wǎng)絡(luò)相比，會(huì)表現(xiàn)出獨(dú)特的網(wǎng)絡(luò)性質(zhì)和結(jié)構(gòu)，其中最主要的是“小世界”特性和無(wú)標(biāo)度特性。針對(duì)社交網(wǎng)絡(luò)的這種特性，對(duì)原有的鏈路預(yù)測(cè)方法進(jìn)行改進(jìn)，在共同鄰居方法的基礎(chǔ)上加入了優(yōu)先連接對(duì)節(jié)點(diǎn)相似性的貢獻(xiàn)。真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集的對(duì)比實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的方法在沒(méi)有增加時(shí)間復(fù)雜度的情況下提高了預(yù)測(cè)準(zhǔn)確度。

社交網(wǎng)絡(luò)；鏈路預(yù)測(cè)；網(wǎng)絡(luò)結(jié)構(gòu)；無(wú)標(biāo)度網(wǎng)絡(luò)

0 引 言

近年來(lái)蓬勃發(fā)展的互聯(lián)網(wǎng)技術(shù)，為社交網(wǎng)絡(luò)提供了一個(gè)優(yōu)質(zhì)的平臺(tái)，在線社交網(wǎng)絡(luò)應(yīng)運(yùn)而生。在線社交網(wǎng)絡(luò)不僅繼承了人們?cè)诰€下的社會(huì)關(guān)系，而且突破了地區(qū)、領(lǐng)域的限制，使得不同的人之間交流更加方便。在線社交網(wǎng)絡(luò)出現(xiàn)以來(lái)，一直被人們所喜愛(ài)，社交網(wǎng)絡(luò)的規(guī)模也因此越來(lái)越大。如今人們對(duì)于在線社交網(wǎng)絡(luò)的依賴越來(lái)越強(qiáng)，同時(shí)對(duì)社交網(wǎng)絡(luò)的要求也越來(lái)越高[1]。因此，如果可以根據(jù)社交網(wǎng)絡(luò)已經(jīng)存在的信息預(yù)測(cè)未來(lái)可能產(chǎn)生的連邊，從而用來(lái)向用戶推薦他們可能感興趣的人，將會(huì)是一項(xiàng)非常有價(jià)值的工作。

復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測(cè)通過(guò)計(jì)算網(wǎng)絡(luò)中尚未連邊的兩個(gè)節(jié)點(diǎn)之間在未來(lái)產(chǎn)生連邊的概率達(dá)到預(yù)測(cè)的目的，其研究思路和方法主要基于馬爾可夫鏈和機(jī)器學(xué)習(xí)。Sarukkai使用馬爾可夫鏈對(duì)網(wǎng)絡(luò)進(jìn)行了鏈路預(yù)測(cè)和路徑分析[2]。之后人們?cè)诖嘶A(chǔ)上進(jìn)行了擴(kuò)展，并提出了一系列模型，但是這些模型大多結(jié)合了網(wǎng)絡(luò)中的節(jié)點(diǎn)屬性，然而很多網(wǎng)絡(luò)中節(jié)點(diǎn)屬性的可靠性并不能得到保證。因此，國(guó)內(nèi)外學(xué)者越來(lái)越關(guān)注基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測(cè)方法。相比于節(jié)點(diǎn)屬性信息，網(wǎng)絡(luò)的結(jié)構(gòu)更加可靠，并且基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測(cè)方法對(duì)于結(jié)構(gòu)相似的網(wǎng)絡(luò)具有一定的普適性。

Liben-Nowell和Kleinberg[3]提出了基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測(cè)方法，并在社會(huì)合作網(wǎng)絡(luò)中分析了一些鏈路預(yù)測(cè)方法的預(yù)測(cè)效果。之后，周濤等[4]在6種網(wǎng)絡(luò)中對(duì)9種鏈路預(yù)測(cè)方法的效果進(jìn)行對(duì)比，發(fā)現(xiàn)同一種方法會(huì)隨著網(wǎng)絡(luò)結(jié)構(gòu)的變化表現(xiàn)出不同的預(yù)測(cè)效果，同時(shí)也可以根據(jù)網(wǎng)絡(luò)的某些結(jié)構(gòu)特點(diǎn)對(duì)鏈路預(yù)測(cè)方法進(jìn)行改進(jìn)[5]。

隨著社交網(wǎng)絡(luò)的快速發(fā)展，對(duì)社交網(wǎng)絡(luò)的研究也逐漸成為一個(gè)熱門方向，而如何預(yù)測(cè)社交網(wǎng)絡(luò)中的關(guān)系成為社交網(wǎng)絡(luò)研究的重要任務(wù)。各種社交網(wǎng)絡(luò)中的鏈路預(yù)測(cè)方法因此被提出，如針對(duì)微博網(wǎng)絡(luò)的鏈路預(yù)測(cè)研究[6]。社交網(wǎng)絡(luò)作為復(fù)雜網(wǎng)絡(luò)的一種典型表現(xiàn)形式，反映了社會(huì)成員之間復(fù)雜的社會(huì)關(guān)系。社交網(wǎng)絡(luò)具有復(fù)雜網(wǎng)絡(luò)的一般特征，又因其連邊存在的社會(huì)性，表現(xiàn)出獨(dú)特的結(jié)構(gòu)特征[7-8]。根據(jù)社交網(wǎng)絡(luò)的結(jié)構(gòu)特性對(duì)鏈路預(yù)測(cè)方法進(jìn)行改進(jìn)，可以在一定程度上提高鏈路預(yù)測(cè)方法在社交網(wǎng)絡(luò)中的預(yù)測(cè)效果。

1 鏈路預(yù)測(cè)方法

用G(V,E)表示一個(gè)無(wú)向網(wǎng)絡(luò)，其中V表示節(jié)點(diǎn)集，E表示邊集。G[t,t1]表示G在[t,t1]時(shí)間段的情況，那么在(t1,t2]時(shí)間段G的情況就是G(t1,t2]。鏈路預(yù)測(cè)關(guān)注的就是如何預(yù)測(cè)網(wǎng)絡(luò)G從[t,t1]到(t1,t2]的變化。

鏈路預(yù)測(cè)經(jīng)過(guò)多年的研究，提出了各種各樣的方法。為了能更好地介紹這些方法，首先介紹一些在文章中使用的符號(hào)。其中，x,y表示節(jié)點(diǎn)，N表示網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量。kx和ky表示節(jié)點(diǎn)x和y的度數(shù)，Γ(x)和Γ(y)分別表示節(jié)點(diǎn)x和y的鄰居節(jié)點(diǎn)集合。

基于局部信息的相似性方法是指僅通過(guò)節(jié)點(diǎn)的局部信息(如節(jié)點(diǎn)的度和最近鄰等)就可以計(jì)算出相似度的方法。這種方法的優(yōu)勢(shì)在于時(shí)間復(fù)雜度低，適用于大型的網(wǎng)絡(luò)應(yīng)用。

1.1共同鄰居(CN)

共同鄰居是一種比較簡(jiǎn)單的鏈路預(yù)測(cè)方法，其基本假設(shè)為：如果兩個(gè)尚未連邊的節(jié)點(diǎn)有更多的共同鄰居，那么它們更傾向于連邊。比如在社交網(wǎng)絡(luò)中，如果兩個(gè)陌生人有很多共同的朋友，那么他們將來(lái)成為朋友的概率也很大[5]。又比如，Newman等發(fā)現(xiàn)在科學(xué)家合作網(wǎng)絡(luò)中，如果兩個(gè)科學(xué)家的共同合作伙伴很多，那么他們將來(lái)也很有可能會(huì)合作[6]。其定義為：

sxy=Γ(x)∩Γ(y)

(1)

在共同鄰居的基礎(chǔ)上，考慮兩個(gè)端點(diǎn)的度對(duì)節(jié)點(diǎn)相似性的影響，又產(chǎn)生了Salton[9]、Jaccard[10]和LNH-I[11]等方法。后來(lái)的研究表明，這些更復(fù)雜的變體在很多情況下都不如CN方法的預(yù)測(cè)效果好，所以選取CN作為基于共同鄰居的方法的代表。

1.2Adamic-Adar(AA)

其思想是度小的共同鄰居節(jié)點(diǎn)的貢獻(xiàn)大于度大的共同鄰居節(jié)點(diǎn)[11-13]。例如，在微博網(wǎng)絡(luò)中，受關(guān)注較多的人往往是某個(gè)領(lǐng)域的專家或者名人，因此共同關(guān)注他們的人之間可能并不擁有特別相似的興趣。相反，如果兩個(gè)人共同關(guān)注了一個(gè)粉絲很少的人(非專家)，那么說(shuō)明這兩個(gè)人確實(shí)具有相同的興趣愛(ài)好或者重疊的社交圈，因此有更高概率相連。

(2)

周濤等根據(jù)網(wǎng)絡(luò)資源分配的啟發(fā)，提出了RA方法[4]。該方法和AA唯一不同的是將公共鄰居的權(quán)重賦值為度的倒數(shù)。

1.3局部路徑(LocalPath,LP)

LP方法在CN方法的基礎(chǔ)上考慮了三階路徑的影響，其定義為：

(3)

1.4Katz

Katz方法考慮了兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的所有路徑對(duì)相似性的貢獻(xiàn)，其定義為[14]：

(4)

其中，β用來(lái)調(diào)節(jié)高階路徑的貢獻(xiàn)。當(dāng)β值很小時(shí)，高階路徑的貢獻(xiàn)也就很小了，此時(shí)Katz的預(yù)測(cè)結(jié)果接近于局部路徑方法。

2 社交網(wǎng)絡(luò)的結(jié)構(gòu)特性

2.1“小世界”特性

“小世界”現(xiàn)象最早出現(xiàn)在20世紀(jì)60年代Milgram的信件投遞實(shí)驗(yàn)中。Milgram通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)每封信平均經(jīng)過(guò)6個(gè)人就可以到達(dá)目標(biāo)收件人手中，并據(jù)此提出了“六度分離”理論[15]。此后，又接連涌現(xiàn)了一些社交網(wǎng)絡(luò)上的“小世界”實(shí)驗(yàn)，比較著名的是“Kevin Bacon”游戲，它的主要目的是計(jì)算電影演員Bacon與其他電影演員之間的距離。該實(shí)驗(yàn)基于美國(guó)Virginia大學(xué)的電影演員數(shù)據(jù)庫(kù)，計(jì)算得到全世界60萬(wàn)演員與Bacon的平均距離為2.944。2011年，F(xiàn)acebook網(wǎng)站與米蘭大學(xué)等共同進(jìn)行的六度分離實(shí)驗(yàn)[16]顯示，F(xiàn)acebook上兩個(gè)用戶之間的平均距離僅為4.74，實(shí)驗(yàn)采用了包含F(xiàn)acebook中7億多用戶和687億條朋友關(guān)系的數(shù)據(jù)，是自2011為止最大規(guī)模的小世界實(shí)驗(yàn)。有研究表明，不同種類的社交網(wǎng)絡(luò)都具有“小世界”現(xiàn)象[17]。

“小世界”現(xiàn)象引發(fā)人們對(duì)如何構(gòu)造一個(gè)小世界網(wǎng)絡(luò)模型的思考，比較著名的小世界網(wǎng)絡(luò)模型是WS小世界模型[18]和NW小世界模型[19]。兩個(gè)網(wǎng)絡(luò)都從規(guī)則網(wǎng)絡(luò)開(kāi)始。WS小世界模型以概率p進(jìn)行隨機(jī)重連，而NW小世界模型以概率p隨機(jī)選擇一定數(shù)量的節(jié)點(diǎn)對(duì)，然后在這些節(jié)點(diǎn)對(duì)之間添加邊。研究表明，兩個(gè)模型都滿足“小世界”網(wǎng)絡(luò)的結(jié)構(gòu)特性，但是在可搜索性角度沒(méi)有進(jìn)行考慮。Kleinberg從可搜索性角度對(duì)NW小世界模型進(jìn)行了修改。Kleinberg認(rèn)為，在兩個(gè)節(jié)點(diǎn)之間增加連邊不應(yīng)該是隨機(jī)的，而是要隨著兩個(gè)節(jié)點(diǎn)之間的網(wǎng)格距離的增加來(lái)降低產(chǎn)生連邊的概率[20]。Kleinberg模型在滿足“小世界”特性的基礎(chǔ)上增加了網(wǎng)絡(luò)的可搜索性，更加符合實(shí)際的網(wǎng)絡(luò)。

2.2無(wú)標(biāo)度特性

無(wú)標(biāo)度特性指網(wǎng)絡(luò)的度分布服從冪律分布，由于這類網(wǎng)絡(luò)中節(jié)點(diǎn)的度沒(méi)有比較明顯的特征長(zhǎng)度，因此稱這類網(wǎng)絡(luò)為無(wú)標(biāo)度網(wǎng)絡(luò)。無(wú)標(biāo)度網(wǎng)路中的度分布為：

P(k)～k-λ

(5)

其中，λ為冪指數(shù)，取值通常在2～3之間。

最著名的無(wú)標(biāo)度網(wǎng)絡(luò)模型是BA無(wú)標(biāo)度網(wǎng)絡(luò)模型[21]。該模型的核心思想在于考慮了網(wǎng)絡(luò)的增加和優(yōu)先連接。網(wǎng)絡(luò)的增長(zhǎng)指的是節(jié)點(diǎn)和連邊的增加，優(yōu)先連接指的是新加入的節(jié)點(diǎn)更容易與度數(shù)大的節(jié)點(diǎn)相連，也稱為“馬太效應(yīng)”。

根據(jù)對(duì)BA無(wú)標(biāo)度網(wǎng)絡(luò)模型構(gòu)造的網(wǎng)絡(luò)研究，發(fā)現(xiàn)網(wǎng)絡(luò)中度為k的節(jié)點(diǎn)出現(xiàn)的概率P(k)近似與k-3成正比，滿足冪律分布。正是這個(gè)原因，文中認(rèn)為同樣滿足度分布為冪律分布的社交網(wǎng)絡(luò)也存在優(yōu)先連接的現(xiàn)象。隨后有研究表明，社交網(wǎng)絡(luò)確實(shí)具有無(wú)標(biāo)度性，即網(wǎng)絡(luò)中大度數(shù)節(jié)點(diǎn)更傾向于與其他大度數(shù)節(jié)點(diǎn)建立連接，而小度數(shù)節(jié)點(diǎn)更傾向于與小度數(shù)節(jié)點(diǎn)相連。

3 鏈路預(yù)測(cè)方法的改進(jìn)方案

針對(duì)社交網(wǎng)絡(luò)中鏈路預(yù)測(cè)方法的改進(jìn)主要是基于社交網(wǎng)絡(luò)的小世界特性和無(wú)標(biāo)度特性，因此改進(jìn)方案的核心思想是在兩個(gè)節(jié)點(diǎn)共同鄰居的基礎(chǔ)上加入對(duì)優(yōu)先連接特性的考慮。在具有無(wú)標(biāo)度特性的網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)x與另一個(gè)節(jié)點(diǎn)y產(chǎn)生連邊的概率與y的度ky成正比[22]，同理，節(jié)點(diǎn)y與節(jié)點(diǎn)x產(chǎn)生連邊的概率與x的度kx成正比，因此節(jié)點(diǎn)x和節(jié)點(diǎn)y產(chǎn)生連邊的概率與kxky的乘積成正比。再根據(jù)“小世界”現(xiàn)象中兩個(gè)節(jié)點(diǎn)之間的連邊概率隨著距離的增加而衰減，需要對(duì)kxky設(shè)置一個(gè)衰減系數(shù)α，用于懲罰距離比較大的節(jié)點(diǎn)對(duì)。由于是在CN的基礎(chǔ)上進(jìn)行改進(jìn)，所以將改進(jìn)的方法命名為ImprovedCN，其定義為：

(6)

4 實(shí) 驗(yàn)

4.1實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)平臺(tái)的硬件信息為：酷睿i5處理器，8 G內(nèi)存，系統(tǒng)版本為Windows 7。

編程語(yǔ)言為Matlab，編程環(huán)境為Matlab2014b。

4.2數(shù)據(jù)集

實(shí)驗(yàn)選取了5個(gè)具有不同功能的社交網(wǎng)絡(luò)，包括朋友網(wǎng)絡(luò)、信息網(wǎng)絡(luò)和通信網(wǎng)絡(luò)，介紹如下：

Wikivote：維基百科中的活躍用戶可以被提名為管理員，當(dāng)一個(gè)用戶被提名時(shí)，維基百科會(huì)組織選舉，獲得支持最多的用戶晉升為管理員。用戶表示為節(jié)點(diǎn)，選舉行為對(duì)應(yīng)于網(wǎng)絡(luò)中的邊，如果用戶A給用戶B投票，那么就有一條邊從A指向B。數(shù)據(jù)集中包含7 115個(gè)節(jié)點(diǎn)和103 689條邊。

Youtube：一個(gè)以視頻分享為主的網(wǎng)站，用戶可以在該網(wǎng)站上分享和下載視頻，也可以通過(guò)朋友關(guān)系組成網(wǎng)絡(luò)社區(qū)進(jìn)行互動(dòng)。網(wǎng)絡(luò)節(jié)點(diǎn)和連邊分別表示用戶和朋友關(guān)系，其中包含8 500個(gè)節(jié)點(diǎn)和77 007條邊。

Facebook：該網(wǎng)絡(luò)包含了Facebook中的朋友列表，是通過(guò)其官方應(yīng)用Facebook.app從調(diào)查參與者中收集到的，數(shù)據(jù)集通過(guò)將Facebook內(nèi)部用戶的id用一個(gè)新的值代替對(duì)真實(shí)網(wǎng)絡(luò)進(jìn)行了匿名化。其中包含4 039個(gè)節(jié)點(diǎn)和88 234條邊。

Email：數(shù)據(jù)集來(lái)自國(guó)外某公司員工的email通信記錄。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)電子郵箱地址，如果一個(gè)地址i發(fā)送給地址j至少一封電子郵件，網(wǎng)絡(luò)中就會(huì)包含一條從i到j(luò)的無(wú)向邊。不考慮公司內(nèi)員工與公司外的電子郵箱地址之間的通信，其中包含1 133個(gè)節(jié)點(diǎn)和10 903條邊。

Gplus：數(shù)據(jù)集包含Google+中的“圈子”，Google+是Google的一個(gè)擴(kuò)展功能，其中心要點(diǎn)是朋友和熟人組成的“圈子”(Circles)。用戶可以把聯(lián)系人按不同的圈子分組，如家庭成員、同事、大學(xué)同學(xué)等，并在“圈子”里分享照片、視頻及其他資訊。用戶之間的每一次互動(dòng)都會(huì)在兩個(gè)用戶對(duì)應(yīng)的節(jié)點(diǎn)之間出現(xiàn)一條連邊。其中包含6 600個(gè)節(jié)點(diǎn)和189 167條邊。

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

實(shí)驗(yàn)中用4種常用鏈路預(yù)測(cè)方法和改進(jìn)的方法ImprovedCN對(duì)五個(gè)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行了預(yù)測(cè)，預(yù)測(cè)準(zhǔn)確度使用AUC來(lái)衡量。AUC從整體上衡量算法的準(zhǔn)確度，它可以理解為測(cè)試集中的邊的分?jǐn)?shù)值比隨機(jī)選取的一個(gè)不存在的邊的分?jǐn)?shù)值高的概率。實(shí)驗(yàn)結(jié)果見(jiàn)表1。

表1 鏈路預(yù)測(cè)方法的預(yù)測(cè)準(zhǔn)確度(AUC)

從表1可以看出，改進(jìn)后的方法在預(yù)測(cè)準(zhǔn)確度上相比CN有了一定的提高，并且在Wikivote、Facebook、Email和Gplus四個(gè)網(wǎng)絡(luò)上都優(yōu)于AA方法，達(dá)到了與LP相當(dāng)?shù)念A(yù)測(cè)水平，在Facebook網(wǎng)絡(luò)中雖然預(yù)測(cè)準(zhǔn)確度不如其他四種方法，但仍然取得了比較理想的效果。

從ImprovedCN的表現(xiàn)來(lái)看，它在一定程度上彌補(bǔ)了CN、AA方法在聚類系數(shù)和平均度都較低的社交網(wǎng)絡(luò)中表現(xiàn)不佳的缺陷，使預(yù)測(cè)準(zhǔn)確度不因網(wǎng)絡(luò)結(jié)構(gòu)的變化而表現(xiàn)出較大的差別。在CN的基礎(chǔ)上增加優(yōu)先連接的考慮確實(shí)取得了更好的效果。

從時(shí)間復(fù)雜度來(lái)分析，雖然ImproveCN在CN的基礎(chǔ)上加入了節(jié)點(diǎn)度的乘積，但是后者可以通過(guò)鄰接矩陣的列向量與自身的轉(zhuǎn)置矩陣相乘計(jì)算，而CN的實(shí)現(xiàn)是鄰接矩陣自身相乘求得，所以在時(shí)間復(fù)雜度上相比于CN沒(méi)有增加。相比于LP和Katz，在運(yùn)行時(shí)間上有比較明顯的優(yōu)勢(shì)。

5 結(jié)束語(yǔ)

研究了社交網(wǎng)絡(luò)的結(jié)構(gòu)特性，并根據(jù)研究結(jié)果對(duì)鏈路預(yù)測(cè)方法進(jìn)行了改進(jìn)，在共同鄰居的基礎(chǔ)上考慮了優(yōu)先連接對(duì)節(jié)點(diǎn)對(duì)的相似性貢獻(xiàn)。通過(guò)實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，改進(jìn)方法的預(yù)測(cè)準(zhǔn)確度有了一定的提高，并且在效果上達(dá)到了局部路徑方法的水平，而且該方法在時(shí)間復(fù)雜度上沒(méi)有增加，比較適合于如今大型的社交網(wǎng)絡(luò)。

[1] 吳信東,李 毅,李 磊.在線社交網(wǎng)絡(luò)影響力分析[J].計(jì)算機(jī)學(xué)報(bào),2014(4):735-752.

[2] Sarukkai R R.Link prediction and path analysis using Markov chains[J].Computer Networks,2000,33(1-6):377-386.

[3] Liben-Nowell D,Kleinberg J.The link-prediction problem for social networks[J].Journal of the American Society for Information Science and Technology,2007,58(7):1019-1031.

[4] Zhou T,Lü L,Zhang Y C.Predicting missing links via local information[J].European Physical Journal B,2009,71(4):623-630.

[5] 劉大偉,呂元娜,余智華.一種改進(jìn)的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(5):1071-1074.

[6] 傅穎斌,陳羽中.基于鏈路預(yù)測(cè)的微博用戶關(guān)系分析[J].計(jì)算機(jī)科學(xué),2014,41(2):201-205.

[7] 許 進(jìn),楊 揚(yáng),蔣 飛,等.社交網(wǎng)絡(luò)結(jié)構(gòu)特性分析及建模研究進(jìn)展[J].中國(guó)科學(xué)院院刊,2015,30(2):216-228.

[8] Lorrain F,White H C.Structural equivalence of individuals in social networks[J].Social Network,1971,1(1):67-98.

[9] Salton G,McGill M J.Inoduction to modern information retrieval[M].Auckland:McGraw-Hill,1983.

[10] Jaccard P.Etude comparative de la distribution florale dans une portion des Alpes et du Jura[J].Bulletin of the Torrey Botanical Club,1901,37:547.

[11] Leicht E A,Holme P,Newman M E.Vertex similarity in networks[J].Physical Review E,2006,73(2):026120.

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

[13] Lü L,Jin C H,Zhou T.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E,2009,80(4):046122.

[14] Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.

[15] Milgram S.The small world problem[J].Psychology Today,1967,2(1):60-67.

[16] Backstrom L,Boldi P,Rosa M,et al.Four degrees of separation[C]//Proceedings of the 4th annual ACM web science conference.[s.l.]:ACM,2012.

[17] Mislove A,Marcon M,Gummadi K P,et al.Measurement and analysis of online social networks[C]//ACM SIGCOMM conference on internet measurement.San Diego,California,USA:ACM,2007.

[18] Watts D J,Strogatz S H.Collective dynamics of “small-world” networks[J].Nature,1998,393(6684):440-442.

[19] Newman M E J,Was D J.Renormalization group analysis of the small-world network model[J].Physics Letters A,1999,263(4-6):341-346.

[20] Kleinberg J.The small-world phenomenon: an algorithm perspective[C]//Proceedings of ACM symposium on theory of computing.[s.l.]:ACM,2010:163-170.

[21] Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[22] 王 林,商 超.無(wú)標(biāo)度網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問(wèn)題研究[J].計(jì)算機(jī)工程,2012,38(3):67-70.

ImprovementofLinkPredictionMethodinSocialNetworks

LI Qi-qi，XU Min

(School of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics,Nanjing 211106，China)

The social network has been developing rapidly in recent years.Various industries are now trying to integrate social elements,so how to improve the accuracy of link prediction methods in social networks has become a popular research.Due to the different network structures,the link prediction methods will be different in prediction performance so that it can be improved according to the characteristics of social network structure,improving of the accuracy of prediction.The social network is a description of certain social relations between people,so compared with other complex networks,it will exhibit its unique properties and network structure,of which the most important is the “small world” and scale-free characteristics.According to the characteristics of social network,the previous link prediction methods can be improved,adding the contribution of priority connection based on common neighbors.The experiments on real social network data sets show that the improved method can improve the accuracy of prediction without increasing time complexity.

social networks；link prediction；network structure；scale-free network

2016-12-30

2017-05-04 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-08-01

國(guó)家“973”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2014CB744900)

李旗旗(1991-)，男，碩士研究生，CCF會(huì)員(E200041166G)，研究方向?yàn)闄C(jī)器學(xué)習(xí)、鏈路預(yù)測(cè)；徐 敏，博士，副教授，研究方向?yàn)槟Ｊ阶R(shí)別、機(jī)器學(xué)習(xí)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1600.084.html

TP393

A

1673-629X(2017)11-0037-04

10.3969/j.issn.1673-629X.2017.11.008