一種基于局部社團和全局信息的鏈路預測算法

楊旭華，凌 非

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

一種基于局部社團和全局信息的鏈路預測算法

楊旭華，凌 非

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

以往復雜網絡的鏈路預測研究常常只考慮了公共鄰居等局部網絡的拓撲信息，不能很好的反映網絡整體上的情況.在考慮局部社團網絡拓撲信息的基礎上，將同配系數等全局信息也引入預測算法中，提出了一種基于局部社團和全局信息的LCII預測算法.應用該算法對多個真實網絡進行了鏈路預測，發現與其他幾種經典鏈路預測算法相比，LCII預測算法有較好的預測效果和準確度.可見，綜合考慮局部社團和全局信息可以挖掘出候選節點間更多的信息，從而能在一定程度上提升預測的命中率.

復雜網絡；鏈路預測；局部社團；全局信息

網絡科學已成為現階段研究領域的熱門學科，網絡科學的基本觀點是從拓撲結構入手，用網絡來描述系統[1].利用這種方法，把系統中的個體看成節點，個體間的相互作用看成連接節點的邊，我們就得到了一個描述系統內部關聯的網絡[2].利用網絡，我們可以研究對應系統的某些靜態或動態的拓撲特性[3]，并幫助我們能更有效地預測[4]甚至控制復雜系統[5].而鏈路預測是網絡科學的一個重要分支，它是通過已知的各種信息預測網絡中尚不存在連邊的兩個節點在網絡進化過程中產生連邊的可能性[6].其中，單一拓撲結構中擁有多個局部社團的網絡是廣大科研工作者研究的重點[7]，而這種網絡被稱為局部社團范式(Local community paradigm, LCP).LCP網絡[8]主要是由節點間的弱相互作用形成的，并同時刻畫了以自組織為適應策略的動態系統.考慮到LCP網絡的普遍存在，研究針對LCP網絡的鏈路預測算法也是很有必要的.

目前，已經有許多基于局部網絡拓撲信息的鏈路預測方法被提出來了，其中公共鄰居(Common neighbors)算法[9]描述的是，兩個節點的共同鄰居數量越多，這兩個節點就越傾向于連接，文中用連接可能性來表征節點間傾向于連接的程度，它是由x節點和y節點的公共鄰居節點屬性體現.而Cannistraci等提出了一個把關注點從節點轉變到連邊的新方法，他們認為該方法可用來解決復雜網絡中的鏈路預測問題，并且他們的CAR算法是在公共節點及其公共節點間連邊關系的基礎上提出的[8].CAR算法表示，如果兩個節點的公共鄰居節點組成了一個內部有連邊的局部社團(Local community, LC)，他們更可能相連，其中，LC的內部連邊叫作局部社團連邊(Local community links, LCL).他們在一些真實網絡的仿真中，得出了CAR算法的效果明顯比CN算法要優的結果.那么，在公共節點和公共節點之間連邊的基礎上，是否可以繼續挖掘局部社團網絡(Local community network, LCN)中更進一步的關系，比如平均最短路徑長度和邊聚類系數？是否引入同配系數以及節點度值大小關系就可以更有效的鏈路預測呢？筆者對此問題進行了研究，結果顯示：平均最短路徑長度、邊聚類系數、同配系數以及節點度值大小關系這些因素能在一定程度上提升鏈路預測的精度.

1 基于局部社團和全局信息的LCII預測算法描述

LCII算法旨在根據網絡中節點之間的連邊關系，為尚未產生連邊的兩個節點預測可能會在未來產生的連邊.通過分析節點所在網絡的同配系數，考慮兩個候選節點的度值，以及局部社團網絡中邊聚類系數和LCN中的平均最短路徑長度，構成LCII算法(圖1).

圖1 LCII算法預測的過程圖示Fig.1 The image of prediction process of LCII

LCII不僅考慮了整個網絡的同配系數以及無連邊節點對的節點度大小關系，還考慮了LCN中邊聚類系數p以及平均最短路徑長度對鏈路預測算法的影響，LCII算法定義為

LCII=CN·LCL·LCC·DU

(1)

其中：CN為候選節點間的共同鄰居數；LCL為局部社團網絡的連邊總數；LCC為局部社團系數；DU為候選節點間度關系的值.為了體現全局信息與局部社團信息的平等，LCII由CN，LCL，LCC和DU以相乘的形式得出，其中LCC綜合了邊聚類系數和平均最短路徑長度，其定義為

(2)

(3)

邊聚類系數p表示一個網絡中連邊聚集程度的系數[10]，其定義為網絡中鄰居節點間的實際連邊數量與網絡中所有節點可能存在最大連邊數之比.一個網絡中的邊聚類系數越大，網絡中節點越接近，節點間的聯系越緊密.在局部社團網絡中，邊聚類系數p則具體化為式(3).

(4)

(5)

如果兩個節點之間的路徑長度越小，說明這兩個節點更接近，節點間的聯系更緊密.對于一個網絡，如果平均最短路徑長度越小，那么LCN節點越接近，而邊聚類系數p如果越大，則LCN越接近，故LCC在綜合兩者后能準確地反映LCN的聚散程度.如果LCC的值越大，說明網絡節點越緊密，反之，越松散.另外，真實網絡一般有同配和異配之分，同配是指度值相近的節點傾向于互相連接，異配則相反.而同配系數[12]作為一個表征復雜網絡是同配還是異配的重要參數，也體現了網絡中節點間度值的整體關系.同配系數可表示為

(6)

其中：M為網絡中的總邊數；j和k分別為第i條連邊的兩個節點.同配系數r∈[-1,1].如果r>0，則網絡是同配的；如果r<0，則網絡是異配的.|r|的大小反映了網絡同配或異配的強弱程度.因此，LCII中的DU指標可表示為

(7)

如果整個網絡的同配系數r<0，表示網絡中的節點更傾向與度大的節點相連，DU指標能表征出兩個未連接的節點度相乘得到的值越大，兩者越容易在接下來的時間里相連；如果整個網絡的同配系數r>0，表示網絡中的節點更傾向與度小的節點相連，DU指標也能表征出兩個未連接的節點度相乘得到的值越小，兩者越容易在接下來的時間里相連.

2 仿真結果與分析

為了檢驗我們提出的算法，我們在幾個現實網絡上進行了實驗.實驗選用的網絡分別為：Jazz musicians network[13]，Florida bay trophic exchange food web[14]，American college football[15]和Zachary’s karate club[16]四個網絡.Jazz musicians網絡中節點是198個Jazz俱樂部成員，連邊是成員之間的交往關系；karate club網絡中節點是34個空手道俱樂部成員，連邊是成員之間交往頻繁的朋友關系；football網絡中節點是115個美國橄欖球俱樂部成員，連邊是成員之間交往的朋友關系；Food網絡中節點是128個生態系統中的生物，連邊是生物之間的捕食關系.表1展示了這幾個不同網絡之間的基本數據對比.

表1 不同真實網絡的基本數據比較

Table 1 The comparison of basic information using different networks in the simulation

真實網絡節點總數/個連邊總數/個同配系數Food1282106-0．111730Football1156150．173184Karate3478-0．476098Jazz19854840．020237

由于網絡數據的局限性，我們將采用一種斷邊后再進行連邊預測的方式來檢驗我們的算法.而這個方法在實驗仿真中是以如下的方式進行：首先，將特定的網絡數據集加載進來，并以此構建網絡圖；接

著，記錄網絡圖中隨機選擇的連邊列表，并刪除這些連邊列表中的連邊；然后，將對應的鏈路預測算法(如LCII，CAR和CN算法)應用到已經刪除連邊的網絡圖中去，每個算法針對各自預測產生的新連邊都有一個相似性分數；最后，將新產生的連邊列表降序排列，并與之前刪除的連邊列表進行對比(每個預測算法都有一個新連邊列表)，計算各個預測算法的命中率.

如果刪除第一層鄰居網絡的連邊超過50%，整個網絡就會出現孤立節點，從而導致局部社團的消失.因此，此處將刪除的比例保持在50%以下，取2%～20%，間隔2%，即2%,4%,6%,8%,…,20%.對于每一個網絡，都將以同一刪除比例重復1 000次仿真，以降低隨機性對仿真的影響.

采用Precision[17]來表征刪除連邊前后網絡的接近程度，即鏈路預測算法的命中率.其表達式為

(8)

其中：Dq為刪除前網絡圖中隨機選擇的連邊列表斷邊列表；Lq為預測算法新產生的連邊列表；Lq為Nq連邊總數；q為刪除的比例，q=0.02,0.04,…,0.2.

為了證明LCII這個想法的正確性，我們把LCII算法與之前提到過的經典的算法CN進行比較.圖2展示了分別對每個網絡進行1 000次迭代后達到穩定狀態時Precision與刪邊比例之間的變化圖(Precision為縱坐標，刪邊比例為橫坐標).

在圖2(a)中，LCII算法的效果明顯優于CAR算法，也明顯優于經典算法，最后在18%的斷邊比例開始效果趨于相近；在圖2(b)中，LCII算法的效果明顯優于CAR算法，而CAR算法略微優于經典算法；在圖2(c)中，LCII算法的效果明顯優于CAR算法，也明顯優于經典算法，三者的增長幅度在18%的斷邊比例后趨于平緩；在圖2(d)中，LCII算法在12%的斷邊比例之前的效果明顯優于CAR算法和經典算法，且LCII算法預測的結果都保持在14%的命中率以上，盡管在12%的斷邊比例之后呈現了一定的下降趨勢.

從以上仿真結果可以看出：LCII算法的效果明顯優于CAR和CN算法，LCC和DU可以在加入CAR指標后起到加強預測的作用，因為LCC和DU可以挖掘出候選節點間更多的信息，在一定程度上可以提升預測的命中率.

圖2 LCII，CAR和CN指標的仿真結果Fig.2 The image of simulation results among LCII, CAR and CN

3 結 論

傳統的鏈路預測大多僅考慮基于一種公共鄰居節點關系的網絡.充分挖掘和利用網絡中更深層次的局部信息，是提高鏈路預測算法精度的一個很好的角度，并提出了一種考慮同配性與度值大小和局部社團網絡中的平均最短路徑長度和邊聚類系數的LCII算法.從對幾個具有局部社團的真實網絡的仿真結果中發現，LCII算法的預測效果明顯優于經典的算法，同時與CAR算法相比也有較好的預測效果.然而，LCII算法沒有考慮有向網絡以及有權網絡，用有向網絡以及有權網絡來描述網絡中節點間的關系將是我們下一步的工作方向.

[1] 龍勝春，龍軍.一種應用于無線傳感器網絡的數據壓縮方法[J].浙江工業大學學報，2014,42(2):210-213.

[2] 楊旭華，李傳告，陳光.基于K-最短路徑的交通網絡傳輸性能分析[J].浙江工業大學學報，2014，42(3):249-256.

[3]WANGWQ,ZHANGQM,ZHOUT.Evaluatingnetworkmodels:alikelihoodanalysis[J].Europhysicsletters,2012,98(2):28004.

[4]WUZ,LINY,WANGJ,etal.Linkpredictionwithnodeclusteringcoefficient[J].PhysicaA,2016,452:1-8.

[5]LIUYY,SLOTINEJJ,BARABSIAL.Controllabilityofcomplexnetworks[J].Nature,2011,473(7346):167-173.

[6]KAYAB,POYRAZM.Supervisedlinkpredictioninsymptomnetworkswithevolvingcase[J].Measurement,2014,56:231-238.

[7]WANGX,XUEZ,XIEZ,etal.MiningtheevolutionofnetworksusingLocal-Cross-Communities-Paradigm[J].Europhysicsletters,2014,104(5):58003.

[8]DAMINELLIS,THOMASJM,DURNC,etal.Commonneighboursandthelocal-community-paradigmfortopologicallinkpredictioninbipartitenetworks[J].Newjournalofphysics,2015,17(11):113037.

[9]ZHAOC,WANGWX,LIUYY,etal.Intrinsicdynamicsinduceglobalsymmetryinnetworkcontrollability[J].Scientificreports,2015,5:8422.

[10] 張霓，陳天天，何熊熊.基于數據場和單次劃分的聚類算法[J].浙江工業大學學報，2016,44(1):52-57.

[11] RAO C R, SHI X, WU Y. Approximation of the expected value of the harmonic mean and some applications[J]. Proceedings of the national academy of sciences,2014,111(44):15681-15686.

[12] 汪小帆,李翔,陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社,2006.

[13] GLEISER P M, DANON L. Community structure in jazz[J]. Advances in complex systems,2003,6(4):565-573.

[14] ARENAS A, DANON L, DIAZ-GUILERA A, et al. Community analysis in social networks[J]. European physical journal B,2004,38(2):373-380.

[15] STOUFFER D B, SALES-PARDO M, SIRER M I, et al. Evolutionary conservation of species’ roles in food webs[J]. Science,2012,335(6075):1489-1492.

[16] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research,1977,33:452-473.

[17] FORTUNATO S. Community detection in graphs[J]. Physics reports,2010,486(3):75-174.

A link prediction algorithm based on local community and global information

YANG Xuhua, LING Fei

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

The common neighbors index is often used in the study of link prediction in the past research. Based on the topological information of local community networks, global information such as co-ordination coefficients is also introduced into the prediction algorithm, but the LCII prediction algorithm is proposed based on local community and global information. Several real networks are employed to simulate the link prediction. It is found that LCII gets better effectiveness of prediction compared with CAR and CN. The results denote that the new contents of LCII index, which consist of local community and global information, can provide more information between candidate nodes. Therefore the LCII index has better link prediction performance.

complex network; link prediction; local community; global information

(責任編輯：劉 巖)

2016-03-25

國家自然科學基金資助項目(61374152)

楊旭華(1974—)，男，浙江余姚人，教授，研究方向為復雜網絡和交通網絡，E-mail：xhyang@zjut.edu.en.

TP391

A

1006-4303(2017)01-0010-04