丁大釗，陳云杰，靳彥青，劉樹新

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002)

(*通信作者電子郵箱18603860002@126.com)

基于拓撲連接緊密度的相似性鏈路預(yù)測算法

丁大釗*，陳云杰，靳彥青，劉樹新

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002)

(*通信作者電子郵箱18603860002@126.com)

許多鏈路預(yù)測方法僅僅關(guān)注預(yù)測的準確度衡量指標，忽略了精確度衡量標準在實際應(yīng)用中的重要作用，且沒有考慮共同鄰居與預(yù)測節(jié)點間緊密度對相似性刻畫的影響。針對上述問題，提出了一種基于拓撲連接緊密度的相似性鏈路預(yù)測算法。該方法通過局部拓撲結(jié)構(gòu)定義共同鄰居緊密度，并引入?yún)?shù)調(diào)節(jié)不同網(wǎng)絡(luò)中緊密程度，最終刻畫網(wǎng)絡(luò)節(jié)點間的相似度。6個實際網(wǎng)絡(luò)測試表明，相比共同鄰居(CN)、資源分配(RA)、Adamic-Adar(AA)、局部路徑(LP)、Katz等相似性指標，該算法提升了鏈路預(yù)測的預(yù)測精度。

復(fù)雜網(wǎng)絡(luò); 鏈路預(yù)測；緊密度；相似性；拓撲結(jié)構(gòu)

0 引言

隨著復(fù)雜網(wǎng)絡(luò)研究的不斷深入，越來越多的復(fù)雜系統(tǒng)都成為了復(fù)雜網(wǎng)絡(luò)的研究對象[1-5]。鏈路預(yù)測作為網(wǎng)絡(luò)科學(xué)領(lǐng)域的研究熱點，主要用于預(yù)測網(wǎng)絡(luò)中任意兩個節(jié)點間連接的可能性[6]。鏈路預(yù)測方法在實際應(yīng)用中受到廣泛關(guān)注，其可以預(yù)測發(fā)現(xiàn)生物蛋白質(zhì)網(wǎng)絡(luò)中未知的連接[7]、預(yù)測人際關(guān)系網(wǎng)絡(luò)中將來可能發(fā)生的連接[8]以及糾正航空運輸網(wǎng)絡(luò)中錯誤的統(tǒng)計連接[9]等。

當(dāng)前，基于復(fù)雜網(wǎng)絡(luò)拓撲演化機制，已經(jīng)提出許多相關(guān)的鏈路預(yù)測方法。其中，基于拓撲結(jié)構(gòu)的相似性方法具有簡單、高效、低復(fù)雜度的特點，受到普遍關(guān)注[10]。根據(jù)算法的復(fù)雜度和涉及網(wǎng)絡(luò)結(jié)構(gòu)的范圍，相似性鏈路預(yù)測方法可以分為局部相似性指標和全局相似性指標[11]。局部相似性鏈路預(yù)測方法包括直接計算共同鄰居數(shù)目的共同鄰居(Common Neighbor, CN)指標[12]、對共同鄰居進行加權(quán)的資源分配(Resource Allocation, RA)指標[13]和Adamic-Adar (AA)[14]指標以及考慮了三階路徑的局部路徑(Local Path, LP)指標[15]，當(dāng)然也有對RA指標的拓展(Extend Resource Allocation, ERA)[16]以及基于隨機游走的鏈路預(yù)測方法[17]，均取得了較好的效果。雖然局部相似性指標在較低的時間復(fù)雜度上取得了較好的效果，但為了進一步提高預(yù)測精度，又提出了許多全局相似性指標，如：Katz指標、LHN-II[18]指標、平均通勤時間(Average Commute Time, ACT)和余弦相似性指標[19]。雖然多數(shù)全局相似性指標能夠取得較好的預(yù)測效果，但具有較高的時間復(fù)雜度，難以應(yīng)用到大型實際網(wǎng)絡(luò)中。許多相似性方法忽略了節(jié)點和共同鄰居節(jié)點之間緊密性的影響，且僅僅關(guān)注準確性評價指標，缺少對精確度指標的關(guān)注。而實際網(wǎng)絡(luò)應(yīng)用如蛋白質(zhì)網(wǎng)絡(luò)的鏈路預(yù)測中，會更多地關(guān)注排名靠前的連接的預(yù)測精度。因此，提高鏈路預(yù)測方法的精確度同樣具有重要的實際意義。

在人際交互網(wǎng)絡(luò)中，如果兩個陌生人和共同好友的聯(lián)系緊密，其更有可能成為朋友，且聯(lián)系越緊密，其成為朋友的可能性越大。圖1所示兩對不同的節(jié)點均包含一個共同鄰居節(jié)點。根據(jù)CN、RA、AA和LP等局部相似性指標，兩對節(jié)點之間存在連接的可能性是相同的。但實際情況中，由于節(jié)點與其共同鄰居之間的緊密性更高(存在多個可能的連接)，所以相比而言它們更有可能建立連接。因此節(jié)點間的緊密性對于鏈路預(yù)測的精確性起著較大的作用。

圖1 不同的共同鄰居拓撲結(jié)構(gòu)舉例Fig. 1 Example of topological structures for different common neighbors

基于上述分析，本文基于節(jié)點和共同鄰居之間連接的緊密性，提出了一種基于拓撲連接緊密度的相似性鏈路預(yù)測算法，進而提高復(fù)雜網(wǎng)絡(luò)中鏈路預(yù)測的精確度指標。在6個實際網(wǎng)絡(luò)數(shù)據(jù)上的實驗結(jié)果表明，相比CN、RA、AA、LP和Katz，該方法具有較高的預(yù)測精度。

1 相關(guān)相似性指標

相似性鏈路預(yù)測指標主要根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)特點計算網(wǎng)絡(luò)中兩個未連接節(jié)點之間的相似程度。對于一對網(wǎng)絡(luò)節(jié)點來說，算法標定得分值越高，其相似性越高，即存在連接的可能性越大?；谙嗨菩缘逆溌奉A(yù)測方法較多，以下將主要介紹CN、RA、AA和LP四個局部相似性指標以及Katz全局相似性鏈路預(yù)測方法。

1)CN[12]。通過共同鄰居的數(shù)目衡量任意未連接的兩個節(jié)點vx和vy的相似度，以Γ(x)表示節(jié)點vx的鄰居集合，則共同鄰居指標表示為：

(1)

2)AA[14]。在CN的基礎(chǔ)上根據(jù)共同鄰居節(jié)點的度為每個節(jié)點賦予一個權(quán)重，而權(quán)重為該節(jié)點度的對數(shù)分之一，定義為：

(2)

3)RA[13]。對于未連接的兩個節(jié)點vx和vy，從vx經(jīng)過共同鄰居傳遞部分資源到vy，共同鄰居傳遞資源的多少和其節(jié)點度成反比，則相似度描述為：

(3)

4)LP[15]。在二階路徑(共同鄰居)上，考慮了三階路徑對相似性的貢獻：

s=A2+αA3

(4)

其中:A為網(wǎng)絡(luò)的鄰接矩陣，α則為調(diào)節(jié)參數(shù)。

5)Katz?？紤]了未連邊節(jié)點之間的所有路徑，表示為：

(5)

上述指標中，CN、RA、AA和LP為局部相似性指標，而Katz則為全局相似性指標，復(fù)雜度較高。

2 基于節(jié)點間緊密性的相似性鏈路預(yù)測指標

對于一個無權(quán)無向網(wǎng)絡(luò)G(V,E)，V和E分別為網(wǎng)絡(luò)中點和邊的集合。每一個鏈路預(yù)測算法給任意一對網(wǎng)絡(luò)節(jié)點x和y分配一個分數(shù)值sxy用于衡量節(jié)點x和y之間的相似性，即存在連接的可能性。在實際網(wǎng)絡(luò)預(yù)測中，通過分數(shù)值的高低便可確定連邊可能的大小。

網(wǎng)絡(luò)節(jié)點之間的緊密性往往與節(jié)點之間存在間接聯(lián)系的數(shù)目有關(guān)，共同鄰居節(jié)點作為大多數(shù)相似性指標最為關(guān)注的對象，其和兩個端點之間的拓撲結(jié)構(gòu)是影響相似性的主要根源。圖2所示，z1和z2分別為節(jié)點x和y的共同鄰居節(jié)點。對于共同鄰居和節(jié)點x之間的緊密性來說，雖然兩個共同鄰居節(jié)點具有相同的節(jié)點度(連邊數(shù)目)，但由于z1與x之間存在更多的相關(guān)邊，因此緊密性R(z1,x)>R(z2,x)。同理，對于z1與x、y之間的緊密性來說，R(z1,x)>R(z1,y)?；谏鲜龆ㄐ杂懻摚疚膶墓餐従咏嵌确治?、定義其周圍拓撲結(jié)構(gòu)對于端點之間的緊密性。

圖2 共同鄰居節(jié)點緊密性示意圖Fig. 2 Schematic diagram of closeness of common neighbors

定義1 共同鄰居緊密度。對于網(wǎng)絡(luò)中的任意兩個節(jié)點x和y，其共同鄰居節(jié)點為z。共同鄰居z和節(jié)點x的緊密度為在共同鄰居z的所有鄰居節(jié)點中和節(jié)點x存在直接聯(lián)系的比例，具體表示為：

R(z,x)=((|Γ(x)∩Γ(z)|+1)/kz)δ

(6)

其中δ為調(diào)節(jié)參數(shù)，用于刻畫不同具體網(wǎng)絡(luò)中緊密度的強度。同理，共同鄰居z和節(jié)點y的緊密度表示為：

R(z,y)=((|Γ(y)∩Γ(z)|+1)/kz)δ

(7)

緊密度R在一定程度上反映了共同鄰居節(jié)點和其他節(jié)點交互的可能性，且通過一個調(diào)節(jié)強度的參數(shù)來刻畫不同實際網(wǎng)絡(luò)中共同鄰居周圍結(jié)構(gòu)對于緊密程度的影響。在共同鄰居緊密度的基礎(chǔ)上，本文進一步提出基于節(jié)點間緊密性的相似性鏈路預(yù)測指標，具體定義如下：

定義2 基于節(jié)點間緊密性的相似性指標(RC)。對于一個無權(quán)無向網(wǎng)絡(luò)G(V,E)，網(wǎng)絡(luò)中的任意兩個節(jié)點x和y，z為共同鄰居節(jié)點。節(jié)點x和y之間的相似性為所有共同鄰居節(jié)點與其之間緊密度的求和，具體為：

(8)

具體算法步驟如下：

步驟1 輸入訓(xùn)練集網(wǎng)絡(luò)矩陣；

步驟2 選取一對節(jié)點i和j，其中i≠j；

步驟3 尋找節(jié)點i和j的共同鄰居{z1,z2,…}；

步驟4 根據(jù)式(8)計算節(jié)點間的相似度，并記錄到相似矩陣的i行j列中；

步驟5 返回步驟2，直到所有網(wǎng)絡(luò)節(jié)點對間相似度計算完畢。

算法與CN、RA的復(fù)雜度相同，均為O(n2)。相比全局性預(yù)測方法，其時間復(fù)雜度較低，可以應(yīng)用于大型復(fù)雜網(wǎng)絡(luò)中。

3 衡量指標與網(wǎng)絡(luò)數(shù)據(jù)

本文所關(guān)注的鏈路預(yù)測算法衡量標準為精確度指標Precision[20]。Precision具體為前L個預(yù)測邊中預(yù)測準確的比例，可以表示為：

Precision=m/L

(9)

其中：m為預(yù)測準確的個數(shù)，文中設(shè)置L=100[21]。顯然，算法的Precision值越大，其預(yù)測的精度則越高。許多實際復(fù)雜網(wǎng)絡(luò)如蛋白質(zhì)網(wǎng)絡(luò)更多地關(guān)注預(yù)測結(jié)果中排名靠前邊的準確性，故越來越多的文章使用Precision作為衡量指標。

為了測試本文方法的有效性，選擇了6個常用的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)：1)Jazz[22]，即爵士音樂家合作網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點代表音樂家，而連邊則表示音樂家之間存在合作關(guān)系；2)Kohonen[23]，是有關(guān)自組織映射主題或T. Kohonen的論文引用網(wǎng)絡(luò)； 3)Hamster[24]，是在hamsterster.com網(wǎng)頁上的用戶朋友關(guān)系網(wǎng)絡(luò)，其中點表示網(wǎng)頁用戶，連邊表示他們之間存在朋友關(guān)系；4)Metabolic[25]，即線蟲的新陳代謝網(wǎng)絡(luò)；5)Email[26]，是一個中型企業(yè)的郵件通信網(wǎng)絡(luò)，節(jié)點為員工，連邊則表示他們之間的郵件往來； 6)Yeast[27]，是蛋白質(zhì)相互作用網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點表示蛋白質(zhì)，而邊則為它們之間的相互作用關(guān)系。

上述6個網(wǎng)絡(luò)具體的特征參數(shù)如表1所示，包含節(jié)點數(shù)目|V|、邊的數(shù)目|E|、平均度〈k〉、集聚系數(shù)C和匹配系數(shù)r。在實驗測試中，每個網(wǎng)絡(luò)數(shù)據(jù)分為訓(xùn)練集合ET邊數(shù)占比為0.9，測試集合EP則為0.1，每個測試結(jié)果均為20次結(jié)果的均值。

表1 實際網(wǎng)絡(luò)的基本特征參數(shù)Tab. 1 Basic topological features of real networks

4 結(jié)果及分析

以精確度指標Precision為衡量標準，在6個實際網(wǎng)絡(luò)中測試基于節(jié)點間緊密性的相似性指標的預(yù)測效果，具體結(jié)果分為兩部分：一是不同網(wǎng)絡(luò)中共同鄰居節(jié)點集聚性對Precision結(jié)果的影響；二是與其他相似性指標的對比結(jié)果分析。

4.1 不同網(wǎng)絡(luò)中精確度結(jié)果分析

針對6個實際網(wǎng)絡(luò)數(shù)據(jù)，首先了分析不同網(wǎng)絡(luò)中緊密度參數(shù)δ對RC預(yù)測結(jié)果的影響。圖3中顯示了δ>0時所有網(wǎng)絡(luò)的Precision曲線。相比δ=0(此時RC即CN指標)，指標均不同程度地提高了其預(yù)測精度，且在合適的參數(shù)下均可以取得最大預(yù)測精度。一般情形下，在取得最大精度值后Precision曲線都會呈現(xiàn)不同程度的下降。但在某些網(wǎng)絡(luò)如Email、Yeast、Metbolic等網(wǎng)絡(luò)中，Precision曲線會保持在一定數(shù)值之上，這一定程度上說明了在這些網(wǎng)絡(luò)中緊密度參數(shù)在達到一定數(shù)值后對相似性的影響就相對穩(wěn)定。

圖3 不同網(wǎng)絡(luò)中Precision結(jié)果Fig. 3 Results of Precision in different networks

RC指標的Precision最大精度均高于δ=0時的預(yù)測值，這說明了共同鄰居的緊密度確實能夠提升鏈路預(yù)測中的精確度Precision。同樣，相比δ=1時，即共同鄰居緊密度沒有強度時，最大Precision精度也明顯更高，這從另一個側(cè)面表達了緊密度的強度對于Precision的提高具有重要作用?？傮w來說，在不同的網(wǎng)絡(luò)數(shù)據(jù)中，RC均能夠在δ>0時迅速提高預(yù)測的Precision值，且一般情形下在δ>3時取最高點，在實際應(yīng)用中可在一定范圍內(nèi)調(diào)節(jié)，可較大程度上提高預(yù)測精度。

4.2 與其他相似性指標對比

為了進一步說明RC指標的有效性，以下將與現(xiàn)有的相似性指標進行對比性分析。

表2顯示了各個相似性指標的Precision結(jié)果對比，其中每個結(jié)果均是20次預(yù)測的均值，每次均是獨立隨機產(chǎn)生訓(xùn)練集和測試集。可以看出，6個實際網(wǎng)絡(luò)中，相比CN、RA、AA、LP等局部相似性指標和Katz全局相似性指標，RC指標具有較高的預(yù)測精度。在局部相似性指標中，CN僅僅利用了共同鄰居數(shù)量這一信息，表現(xiàn)相對一般；RA和AA利用共同鄰居的節(jié)點度進行加權(quán)，在復(fù)雜度較低的情形下，大多數(shù)網(wǎng)絡(luò)中Precision結(jié)果明顯好于CN；在考慮了三階路徑后，LP指標在多數(shù)網(wǎng)絡(luò)中如Kohonen、Hamster等網(wǎng)絡(luò)中均表現(xiàn)較好。Katz雖然考慮了網(wǎng)絡(luò)中所有可能的路徑，但其在Precision標準下與LP指標非常接近，且Katz指標的時間復(fù)雜度較高。RC指標在考慮了共同鄰居與預(yù)測節(jié)點間緊密度的情況下，取得了較高的預(yù)測精度。很明顯，在許多集聚系數(shù)較低的網(wǎng)絡(luò)中，多數(shù)相似性指標預(yù)測精度較低，而RC指標可以極大限度地提高其預(yù)測精度，如在Hamster網(wǎng)絡(luò)中CN的預(yù)測精度為0.015，而RC的預(yù)測精度為0.186，提高比率為12.4倍。此外，RC的時間復(fù)雜度較低，非常適合于大型實際網(wǎng)絡(luò)中的鏈路預(yù)測。

表2 不同指標下Precision值對比Tab. 2 Comparison of Precision for different indices

5 結(jié)語

近年來，提出了大量的相似性鏈路預(yù)測方法，許多方法都取得了較好的預(yù)測效果。針對現(xiàn)有的方法在精確度衡量標準Precision上效果較差的問題，提出了一種基于拓撲連接緊密度的相似性鏈路預(yù)測算法。6個實際網(wǎng)絡(luò)數(shù)據(jù)測試表明，當(dāng)前方法具有較高的精確度，而且該方法的時間復(fù)雜度較低，完全可以用于大型復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測。本文算法完全基于網(wǎng)絡(luò)結(jié)構(gòu)進行鏈路預(yù)測，下一步可以結(jié)合網(wǎng)絡(luò)節(jié)點屬性、行為等多維度信息研究大數(shù)據(jù)挖掘下的鏈路預(yù)測方法。

References)

[1] GAO Z-K, SMALL M, KURTHS J. Complex network analysis of time series [J]. Europhysics Letters, 2017, 116(5): 50001-50005.

[2] LIU S, JI X, LIU C, et al. Similarity indices based on link weight assignment for link prediction of unweighted complex networks [J]. International Journal of Modern Physics B, 2016, 31(2): 1650254.

[3] ZHANG Y, BAO Z, CAO Y, et al. Long-term effect of different topology evolutions on blackouts in power grid [J]. International Journal of Electrical Power & Energy Systems, 2014, 62(2014): 718-726.

[4] 劉樹新,季新生,劉彩霞,等.一種信息傳播促進網(wǎng)絡(luò)增長的網(wǎng)絡(luò)演化模型[J].物理學(xué)報,2014,63(15):158902. (LIU S X, JI X S, LIU C X, et al. A complex network evolution model for network growth promoted by information transmission [J]. Acta Physica Sinica, 2014, 63(15): 158902.

[5] PECH R, HAO D, PAN L, et al. Link prediction via matrix completion [J]. Europhysics Letters, 2017, 117(3): 38002.

[6] WANG P, XU B W, WU Y R, et al. Link prediction in social networks: the state-of-the-art [J]. Science China Information Sciences, 2015, 58(1): 1-38.

[7] VON MERING C, JENSEN L J, SNEL B, et al. STRING: known and predicted protein-protein associations, integrated and transferred across organisms [J]. Nucleic Acids Research, 2005(33): D433-D437.

[8] SCELLATO S, NOULAS A, MASCOLO C. Exploiting place features in link prediction on location-based social networks [C]// KDD ’11: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2011: 1046-1054.

[9] HOLLAND P W, LASKEY K B, LEINHARDT S. Stochastic blockmodels: first steps [J]. Social Networks, 1983, 5(2): 109-137.

[10] FENG X, ZHAO J C, XU K. Link prediction in complex networks: a clustering perspective [J]. The European Physical Journal B, 2012, 85: 3.

[11] Lü L, ZHOU T. Link prediction in complex networks: a survey [J]. Physica A: Statistical Mechanics and its Applications, 2011, 390(6): 1150-1170.

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

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

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

[15] Lü L, JIN C-H, ZHOU T. Similarity index based on local paths for link prediction of complex networks [J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2009, 80(4): 046122.

[16] LIU S, JI X, LIU C, et al. Extended resource allocation index for link prediction of complex network [J]. Physica A: Statistical Mechanics and its Applications, 2017, 479: 174-183.

[17] 劉思,劉海,陳啟買,等.基于網(wǎng)絡(luò)表示學(xué)習(xí)與隨機游走的鏈路預(yù)測算法[J/OL].計算機應(yīng)用,2017 [2017- 04- 01]. http://www.joca.cn/CN/abstract/abstract20373.shtml. (LIU S, LIU H, CHEN Q M, et al. Link prediction algorithm based on network representation learning and random walk [J/OL]. Journal of Computer Applications, 2017 [2017- 04- 01]. http://www.joca.cn/CN/abstract/abstract20373.shtml.)

[18] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks [J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2006, 73(2): 026120.

[19] FOUSS F, PIROTTE A, RENDERS J-M, et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation [J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(3): 355-369.

[20] HERLOCKER J L, KONSTAN J A, TERVEEN L G, et al. Evaluating collaborative filtering recommender systems [J]. ACM Transactions on Information Systems, 2004, 22(1): 5-53.

[21] Lü L, ZHOU T. Link prediction in weighted networks: the role of weak ties [J]. Europhysics Letters, 2010, 89(1): 18001.

[22] GLEISER P M, DANON L. Community structure in Jazz [J]. Advances in Complex Systems, 2003, 6(4): 565-573.

[23] ZHANG Q, Lü L, WANG W, et al. Potential theory for directed networks [J]. PLoS ONE, 2013, 8(2): e55437.

[24] Lü L, PAN L, ZHOU T, et al. Toward link predictability of complex networks [J]. Proceedings of the National Academy of Sciences, 2015, 112(8): 2325-2330.

[25] DUCH J, ARENAS A. Community detection in complex networks using extremal optimization [J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2005, 72(2): 027104.

[26] MICHALSKI R, PALUS S, KAZIENKO P. Matching organizational structure and social network extracted from email communication [C]// BIS 2011: Proceedings of the International Conference on Business Information Systems. Berlin: Springer-Verlag, 2011: 197-206.

[27] BU D, ZHAO Y, CAI L, et al. Topological structure analysis of the protein-protein interaction network in budding yeast [J]. Nucleic Acids Research, 2003, 31(9): 2443-2450.

This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2015AA01A708, 2016YFB080160).

DINGDazhao, born in 1979, M. S., engineer. His research interests include communication and information system.

CHENYunjie, born in 1981, M. S., engineer. His research interests include wireless communication security.

JINYanqing, born in 1983, engineer. Her research interests include wireless communication.

LIUShuxin, born in 1987, Ph. D. His research interests include complex network.

Linkpredictionmethodforcomplexnetworkbasedonclosenessbetweennodes

DING Dazhao*, CHEN Yunjie, JIN Yanqing, LIU Shuxin

(NationalDigitalSwitchingSystemEngineeringandTechnologicalR&DCenter,ZhengzhouHenan450002,China)

Many link prediction methods only focus on the standard metric AUC (Area Under receiver operating characteristic Curve), ignoring the metric precision and closeness of common neighbors and endpoints under different topological structures. To solve these problems, a link prediction method based on closeness between nodes was proposed. In order to describe the similarity between endpoints more accurately, the closeness of common neighbors was designed by considering the local topological information around common neighbors, which was adjusted for different networks through a parameter. Empirical study on six real networks show that compared with the similarity indicators such as Common Neighbor (CN), Resource Allocation (RA), Adamic-Adar (AA), Local Path (LP) and Katz, the proposed index can improve the prediction accuracy.

complex network; link prediction; closeness; similarity; topological structure

TP393.02

A

2017- 02- 24;

2017- 05- 06。

國家863計劃項目(2015AA01A708， 2016YFB0801605)。

丁大釗(1979—)，男，河南許昌人，工程師，碩士，主要研究方向：通信與信息系統(tǒng)； 陳云杰(1981—)，男，河南新鄉(xiāng)人，工程師，碩士，主要研究方向：無線通信網(wǎng)絡(luò)安全； 靳彥青(1983—)，女，河南南召人，工程師，主要研究方向：無線通信； 劉樹新(1987—)，男，山東濰坊人，博士，主要研究方向：復(fù)雜網(wǎng)絡(luò)。

1001- 9081(2017)08- 2129- 04

10.11772/j.issn.1001- 9081.2017.08.2129