楊旭華，凌 非

(浙江工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

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

楊旭華，凌 非

(浙江工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

以往復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測研究常常只考慮了公共鄰居等局部網(wǎng)絡(luò)的拓?fù)湫畔?，不能很好的反映網(wǎng)絡(luò)整體上的情況.在考慮局部社團網(wǎng)絡(luò)拓?fù)湫畔⒌幕A(chǔ)上，將同配系數(shù)等全局信息也引入預(yù)測算法中，提出了一種基于局部社團和全局信息的LCII預(yù)測算法.應(yīng)用該算法對多個真實網(wǎng)絡(luò)進(jìn)行了鏈路預(yù)測，發(fā)現(xiàn)與其他幾種經(jīng)典鏈路預(yù)測算法相比，LCII預(yù)測算法有較好的預(yù)測效果和準(zhǔn)確度.可見，綜合考慮局部社團和全局信息可以挖掘出候選節(jié)點間更多的信息，從而能在一定程度上提升預(yù)測的命中率.

復(fù)雜網(wǎng)絡(luò)；鏈路預(yù)測；局部社團；全局信息

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

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

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

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

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

LCII不僅考慮了整個網(wǎng)絡(luò)的同配系數(shù)以及無連邊節(jié)點對的節(jié)點度大小關(guān)系，還考慮了LCN中邊聚類系數(shù)p以及平均最短路徑長度對鏈路預(yù)測算法的影響，LCII算法定義為

LCII=CN·LCL·LCC·DU

(1)

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

(2)

(3)

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

(4)

(5)

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

(6)

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

(7)

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

2 仿真結(jié)果與分析

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

表1 不同真實網(wǎng)絡(luò)的基本數(shù)據(jù)比較

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

真實網(wǎng)絡(luò)節(jié)點總數(shù)/個連邊總數(shù)/個同配系數(shù)Food1282106-0．111730Football1156150．173184Karate3478-0．476098Jazz19854840．020237

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

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

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

采用Precision[17]來表征刪除連邊前后網(wǎng)絡(luò)的接近程度，即鏈路預(yù)測算法的命中率.其表達(dá)式為

(8)

其中：Dq為刪除前網(wǎng)絡(luò)圖中隨機選擇的連邊列表斷邊列表；Lq為預(yù)測算法新產(chǎn)生的連邊列表；Lq為Nq連邊總數(shù)；q為刪除的比例，q=0.02,0.04,…,0.2.

為了證明LCII這個想法的正確性，我們把LCII算法與之前提到過的經(jīng)典的算法CN進(jìn)行比較.圖2展示了分別對每個網(wǎng)絡(luò)進(jìn)行1 000次迭代后達(dá)到穩(wěn)定狀態(tài)時Precision與刪邊比例之間的變化圖(Precision為縱坐標(biāo)，刪邊比例為橫坐標(biāo)).

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

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

圖2 LCII，CAR和CN指標(biāo)的仿真結(jié)果Fig.2 The image of simulation results among LCII, CAR and CN

3 結(jié) 論

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

[1] 龍勝春，龍軍.一種應(yīng)用于無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)壓縮方法[J].浙江工業(yè)大學(xué)學(xué)報，2014,42(2):210-213.

[2] 楊旭華，李傳告，陳光.基于K-最短路徑的交通網(wǎng)絡(luò)傳輸性能分析[J].浙江工業(yè)大學(xué)學(xué)報，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] 張霓，陳天天，何熊熊.基于數(shù)據(jù)場和單次劃分的聚類算法[J].浙江工業(yè)大學(xué)學(xué)報，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] 汪小帆,李翔,陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社,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

(責(zé)任編輯：劉 巖)

2016-03-25

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

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

TP391

A

1006-4303(2017)01-0010-04