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

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

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

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

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

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

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

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

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

復雜網(wǎng)絡; 鏈路預測；緊密度；相似性；拓撲結構

0 引言

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

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

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

圖1 不同的共同鄰居拓撲結構舉例Fig. 1 Example of topological structures for different common neighbors

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

1 相關相似性指標

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

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

(1)

2)AA[14]。在CN的基礎上根據(jù)共同鄰居節(jié)點的度為每個節(jié)點賦予一個權重，而權重為該節(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)絡的鄰接矩陣，α則為調節(jié)參數(shù)。

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

(5)

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

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

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

網(wǎng)絡節(jié)點之間的緊密性往往與節(jié)點之間存在間接聯(lián)系的數(shù)目有關，共同鄰居節(jié)點作為大多數(shù)相似性指標最為關注的對象，其和兩個端點之間的拓撲結構是影響相似性的主要根源。圖2所示，z1和z2分別為節(jié)點x和y的共同鄰居節(jié)點。對于共同鄰居和節(jié)點x之間的緊密性來說，雖然兩個共同鄰居節(jié)點具有相同的節(jié)點度(連邊數(shù)目)，但由于z1與x之間存在更多的相關邊，因此緊密性R(z1,x)>R(z2,x)。同理，對于z1與x、y之間的緊密性來說，R(z1,x)>R(z1,y)。基于上述定性討論，本文將從共同鄰居角度分析、定義其周圍拓撲結構對于端點之間的緊密性。

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

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

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

(6)

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

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

(7)

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

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

(8)

具體算法步驟如下：

步驟1 輸入訓練集網(wǎng)絡矩陣；

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

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

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

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

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

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

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

Precision=m/L

(9)

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

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

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

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

4 結果及分析

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

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

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

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

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

4.2 與其他相似性指標對比

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

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

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

5 結語

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

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)絡增長的網(wǎng)絡演化模型[J].物理學報,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)絡表示學習與隨機游走的鏈路預測算法[J/OL].計算機應用,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)絡安全； 靳彥青(1983—)，女，河南南召人，工程師，主要研究方向：無線通信； 劉樹新(1987—)，男，山東濰坊人，博士，主要研究方向：復雜網(wǎng)絡。

1001- 9081(2017)08- 2129- 04

10.11772/j.issn.1001- 9081.2017.08.2129