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

楊旭華，凌 非

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

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

楊旭華，凌 非

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

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

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

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

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

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

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

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

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

LCII=CN·LCL·LCC·DU

(1)

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

(2)

(3)

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

(4)

(5)

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

(6)

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

(7)

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

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

為了檢驗(yàn)我們提出的算法，我們?cè)趲讉€(gè)現(xiàn)實(shí)網(wǎng)絡(luò)上進(jìn)行了實(shí)驗(yàn).實(shí)驗(yà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]四個(gè)網(wǎng)絡(luò).Jazz musicians網(wǎng)絡(luò)中節(jié)點(diǎn)是198個(gè)Jazz俱樂(lè)部成員，連邊是成員之間的交往關(guān)系；karate club網(wǎng)絡(luò)中節(jié)點(diǎn)是34個(gè)空手道俱樂(lè)部成員，連邊是成員之間交往頻繁的朋友關(guān)系；football網(wǎng)絡(luò)中節(jié)點(diǎn)是115個(gè)美國(guó)橄欖球俱樂(lè)部成員，連邊是成員之間交往的朋友關(guān)系；Food網(wǎng)絡(luò)中節(jié)點(diǎn)是128個(gè)生態(tài)系統(tǒng)中的生物，連邊是生物之間的捕食關(guān)系.表1展示了這幾個(gè)不同網(wǎng)絡(luò)之間的基本數(shù)據(jù)對(duì)比.

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

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

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

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

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

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

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

(8)

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

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

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

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

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

3 結(jié) 論

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

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

[2] 楊旭華，李傳告，陳光.基于K-最短路徑的交通網(wǎng)絡(luò)傳輸性能分析[J].浙江工業(yè)大學(xué)學(xué)報(bào)，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ù)場(chǎng)和單次劃分的聚類算法[J].浙江工業(yè)大學(xué)學(xué)報(bào)，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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61374152)

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

TP391

A

1006-4303(2017)01-0010-04