復(fù)雜網(wǎng)絡(luò)中集聚系數(shù)對鏈路預(yù)測算法的影響

黃子軒 馬 超 徐瑾輝 黃江楠

（廣東外語外貿(mào)大學(xué) 思科信息學(xué)院，廣東 廣州 510006）

0 引言

對于大規(guī)模的復(fù)雜網(wǎng)絡(luò)，受時(shí)間、空間和實(shí)驗(yàn)條件的限制，我們能探測到的節(jié)點(diǎn)間的鏈接是有限的，大量鏈接的實(shí)驗(yàn)探測是困難的甚至是不可能的。因此如何根據(jù)已知的網(wǎng)絡(luò)數(shù)據(jù)信息，通過設(shè)計(jì)合適的預(yù)測算法，預(yù)測節(jié)點(diǎn)間未知鏈接存在連邊的可能性，是當(dāng)前復(fù)雜網(wǎng)絡(luò)科學(xué)研究的重要課題之一，此即所謂的鏈路預(yù)測問題。實(shí)際上，鏈路預(yù)測問題作為數(shù)據(jù)挖掘領(lǐng)域的一個(gè)子問題，在信息科學(xué)領(lǐng)域早已展開了研究（如基于馬爾科夫鏈和機(jī)器學(xué)習(xí)的方法[1]）。但在現(xiàn)代大規(guī)模復(fù)雜網(wǎng)絡(luò)的框架下，傳統(tǒng)的鏈路預(yù)測算法遠(yuǎn)不能滿足人們對預(yù)測效率和預(yù)測精度的需求，因此有必要發(fā)展新的鏈路預(yù)測算法。

在鏈路預(yù)測算法研究中，由于節(jié)點(diǎn)的屬性信息難以獲取，所以基于局部信息的相似性指標(biāo)的鏈路預(yù)測算法受到了更大的關(guān)注[2]。近年來，基于局部信息的相似性指標(biāo)不再單一地考慮共同鄰居的數(shù)量或其度值，研究者們開始把共同鄰居之間的聯(lián)系也加以考慮[3]。但并不是所有的網(wǎng)絡(luò)都需要考慮共同鄰居的相互關(guān)系，甚至有時(shí)候會降低其準(zhǔn)確率。

如今多數(shù)工作都是針對新的鏈路預(yù)測算法的提出，較少工作揭示出研究不同的網(wǎng)絡(luò)結(jié)構(gòu)與算法選擇之間的關(guān)系。本文基于真實(shí)網(wǎng)絡(luò)和模擬網(wǎng)絡(luò)上的實(shí)驗(yàn)，對網(wǎng)絡(luò)的節(jié)點(diǎn)集聚系數(shù)、邊集聚系數(shù)與鏈路預(yù)測算法之間的關(guān)系進(jìn)行分析，并研究何時(shí)需要考慮共同鄰居之間的相互關(guān)系[4]。

1 問題描述

定義G(V,E)為一個(gè)無向網(wǎng)絡(luò)，其中V為節(jié)點(diǎn)集合，E為邊集合。網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)為N，邊數(shù)為M。該網(wǎng)絡(luò)共有N(N-1)/2個(gè)節(jié)點(diǎn)對，即全集U。這樣，鏈路預(yù)測問題可描述為：構(gòu)建某種相似度指標(biāo)，對沒有連邊的節(jié)點(diǎn)對(x,y)計(jì)算其相似度Sxy，Sxy越大，節(jié)點(diǎn)對(x,y)出現(xiàn)連邊的概率越大。

為了衡量算法的精確度，我們將已知連邊E分為訓(xùn)練集ET和測試集EP兩部分，其中EP為在E中隨機(jī)抽取的10%的邊，剩下的邊均勻分配至ET。 另外，將屬于U但不屬于E的邊定義為不存在的邊。本文使用AUC指標(biāo)來衡量算法的準(zhǔn)確性。AUC(area under the receiver operating characteristic curve)定義為隨機(jī)在測試集中選取的邊的分?jǐn)?shù)值比隨機(jī)選擇的一條不存在的邊的分?jǐn)?shù)值高的概率。即每次隨機(jī)從測試集中選取一條邊與隨機(jī)選擇的一條不存在的邊進(jìn)行比較，加分規(guī)則如下：若測試集的邊的分?jǐn)?shù)值大于不存在的邊的分?jǐn)?shù)值，則加1分；若兩個(gè)分?jǐn)?shù)值相等，則加0.5分；若測試集的邊的分?jǐn)?shù)值小于不存在的邊的分?jǐn)?shù)值，則加0分。重復(fù)以上步驟，獨(dú)立地比較n次，定義n1為測試集中邊的分?jǐn)?shù)值大于不存在的邊的分?jǐn)?shù)值的次數(shù)，定義n2為兩個(gè)分?jǐn)?shù)值相等的次數(shù)，則定義AUC為

節(jié)點(diǎn)集聚系數(shù)用來描述一個(gè)節(jié)點(diǎn)的鄰接點(diǎn)之間相互連接的程度，將該系數(shù)運(yùn)用在社交網(wǎng)絡(luò)中，其意義為該用戶的朋友之間也是朋友的概率。設(shè)網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)為vi，該節(jié)點(diǎn)的集聚系數(shù)C(i)等于其鄰接點(diǎn)之間連邊的數(shù)量除以鄰接點(diǎn)之間可以連出的最大邊數(shù)。設(shè)ei為節(jié)點(diǎn)vi的鄰接點(diǎn)之間連邊的數(shù)量，k(i)為節(jié)點(diǎn)vi的度值，則

邊集聚系數(shù)：在一個(gè)無向網(wǎng)絡(luò)G(V,E)中，設(shè)一條邊為E(u,v)，其端點(diǎn)分別為u和v，考慮u和v有多少個(gè)共同鄰居w，即存在另外兩條邊E(u,w)，E(v,w)與E(u,v)形成閉合三角形。所以，將E(u,v)的邊聚集系數(shù)ECC(u,v)定義為包含該邊的三角形與該邊最多可能構(gòu)成的三角形個(gè)數(shù)之比，即：

邊集聚系數(shù)刻畫了兩個(gè)節(jié)點(diǎn)之間聯(lián)系的緊密程度，而聚集效應(yīng)是復(fù)雜網(wǎng)絡(luò)中的一個(gè)重要性質(zhì)。網(wǎng)絡(luò)的平均邊集聚系數(shù)刻畫出網(wǎng)絡(luò)整體的緊密程度，因此，本文認(rèn)為網(wǎng)絡(luò)的平均邊集聚系數(shù)能較好地區(qū)分出不同結(jié)構(gòu)的網(wǎng)絡(luò)[5]。本文涉及到以下8種相似性指標(biāo)：

CN指標(biāo)：該指標(biāo)定義為兩個(gè)節(jié)點(diǎn)的共同鄰居數(shù)量。對于節(jié)點(diǎn)i，定義i的鄰居集合為Г(i)，設(shè)節(jié)點(diǎn)x和y節(jié)點(diǎn)的相似性為Sxy，即Sxy=

CAR指標(biāo)[7]：該指標(biāo)以CN指標(biāo)為基礎(chǔ)，加以考慮共同鄰居間的相互關(guān)系，定義如下：

其中，γ(z)為節(jié)點(diǎn)z與兩端節(jié)點(diǎn)以及其余共同鄰居之間的連接數(shù)。CAA指標(biāo)：該指標(biāo)以AA指標(biāo)為基礎(chǔ)，加以考慮共同鄰居之間的相互關(guān)系，定義如下：

CRA指標(biāo)：該指標(biāo)以RA指標(biāo)為基礎(chǔ)，加以考慮共同鄰居之間的相互關(guān)系，定義如下：

CCC指標(biāo)：該指標(biāo)以CC指標(biāo)為基礎(chǔ)，加以考慮共同鄰居之間的相互關(guān)系，定義如下：

3 模擬網(wǎng)絡(luò)實(shí)驗(yàn)

3.1 數(shù)據(jù)集

復(fù)雜網(wǎng)絡(luò)普遍存在于真實(shí)社會中，為了充分考慮不同類型的網(wǎng)絡(luò)，本文首先通過pajek生成的小世界網(wǎng)絡(luò)進(jìn)行模擬。其中，本文通過軟件生成的小世界網(wǎng)絡(luò)的設(shè)置均為200個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)平均度分別為20和30。表1為節(jié)點(diǎn)平均度為20的小世界網(wǎng)絡(luò)的拓?fù)湫畔⒑蛯?shí)驗(yàn)結(jié)果，表2為節(jié)點(diǎn)平均度為30的小世界網(wǎng)絡(luò)的拓?fù)湫畔⒑蛯?shí)驗(yàn)結(jié)果。將上述8種算法在小世界網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)，并比較準(zhǔn)確率。在AUC測試正確率中，對原始數(shù)據(jù)集進(jìn)行了隨機(jī)抽取分成了訓(xùn)練集（含90%的連邊數(shù)）和測試集（含10%的連邊數(shù)）兩部分，隨后進(jìn)行了105次的隨機(jī)抽樣比較。

3.2 實(shí)驗(yàn)結(jié)果

表1 小世界網(wǎng)絡(luò)（K=20）的拓?fù)湫畔⒑蛯?shí)驗(yàn)結(jié)果

表2 小世界網(wǎng)絡(luò)（K=30）的拓?fù)湫畔⒑蛯?shí)驗(yàn)結(jié)果

3.3 實(shí)驗(yàn)分析

由表1和表2可以看出，隨著網(wǎng)絡(luò)的平均節(jié)點(diǎn)集聚系數(shù)的增大，網(wǎng)絡(luò)的平均邊集聚系數(shù)也在增大，各個(gè)鏈路預(yù)測算法的準(zhǔn)確性也在提高。小世界網(wǎng)絡(luò)的平均節(jié)點(diǎn)集聚系數(shù)與平均邊集聚系數(shù)較為接近。在小世界網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)的平均節(jié)點(diǎn)集聚系數(shù)較為低的時(shí)候，這四種改進(jìn)后的算法比原算法有更好的表現(xiàn)，但隨著網(wǎng)絡(luò)的平均節(jié)點(diǎn)集聚系數(shù)的提高，突出程度則在降低。因此，本文認(rèn)為對于有較低的平均節(jié)點(diǎn)集聚系數(shù)的網(wǎng)絡(luò)，考慮共同鄰居之間的相互關(guān)系能更好地表現(xiàn)出節(jié)點(diǎn)之間的連接緊密性。對于高平均節(jié)點(diǎn)集聚系數(shù)的網(wǎng)絡(luò)，因其網(wǎng)絡(luò)本身擁有較好的緊密性，再加以考慮共同鄰居之間的相互關(guān)系對于提高算法有效性的用處不大。

4 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)

4.1 數(shù)據(jù)集

本文使用了4個(gè)真實(shí)網(wǎng)絡(luò)：adjnoun網(wǎng)絡(luò)、football網(wǎng)絡(luò)、polbooks網(wǎng)絡(luò)、US power grid網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，對上一小節(jié)實(shí)驗(yàn)分析進(jìn)行驗(yàn)證。這里，我們?nèi)圆捎蒙鲜?種算法在各個(gè)網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)，并比較準(zhǔn)確率。在AUC測試正確率中，對原始數(shù)據(jù)集進(jìn)行了隨機(jī)抽取分成了訓(xùn)練集（含90%的連邊數(shù)）和測試集（含10%的連邊數(shù)）兩部分，隨后進(jìn)行了105次的隨機(jī)抽樣比較，表3為4個(gè)真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果。

4.2 實(shí)驗(yàn)結(jié)果

表3 4個(gè)真實(shí)網(wǎng)絡(luò)的拓?fù)湫畔⒑蛯?shí)驗(yàn)結(jié)果

4.3 實(shí)驗(yàn)分析

通過表3，我們發(fā)現(xiàn)football網(wǎng)絡(luò)和polbooks網(wǎng)絡(luò)擁有較高的平均節(jié)點(diǎn)集聚系數(shù)，8種鏈路預(yù)測算法在這兩個(gè)網(wǎng)絡(luò)中表現(xiàn)出約為90%的正確率。而US power grid網(wǎng)絡(luò)的平均節(jié)點(diǎn)集聚系數(shù)極低，因此鏈路預(yù)測算法在該網(wǎng)絡(luò)上表現(xiàn)均不佳，不到60%的正確率。adjnoun網(wǎng)絡(luò)相對于football網(wǎng)絡(luò)和polbooks網(wǎng)絡(luò)擁有較低的平均節(jié)點(diǎn)集聚系數(shù)，且兩種平均集聚系數(shù)較為接近，相對于US power grid網(wǎng)絡(luò)更接近小世界網(wǎng)絡(luò)的特性，而4種改良算法的正確率對比原算法的正確率有一定的提高，反觀US power grid網(wǎng)絡(luò)的實(shí)驗(yàn)中，改良算法與原算法幾乎無異。整體來說，在真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果符合第三部分的實(shí)驗(yàn)分析。

5 總結(jié)

在復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測研究中，以前的工作主要集中提出新的鏈路預(yù)測算法。不同于此，為了更好地理解算法與網(wǎng)絡(luò)之間的聯(lián)系，本文以集聚系數(shù)為切入點(diǎn)，研究了其對鏈路預(yù)測算法的影響，加深理解影響算法準(zhǔn)確性的因素，以及算法的適用范圍。本文工作綜合考慮了網(wǎng)絡(luò)結(jié)構(gòu)的多樣性以及算法的適用性，對鏈路預(yù)測算法與網(wǎng)絡(luò)結(jié)構(gòu)之間的聯(lián)系進(jìn)行深入的研究。實(shí)驗(yàn)表明：模擬實(shí)驗(yàn)的結(jié)論同樣適用于真實(shí)網(wǎng)絡(luò)，對于鏈路預(yù)測的研究有重要的參考價(jià)值。

［1］Sarukkai RR.Link prediction and path analysis using Markov chains[J].Computer Networks,33(1-6)∶377－386,2000.

［2］呂琳媛，陸君安，張子柯，閆小勇，吳曄，史定華，周海平，方錦清，周濤.復(fù)雜網(wǎng)絡(luò)觀察[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2010,7（2-3）：173-186.

［3］東昱曉，柯慶，吳斌.基于節(jié)點(diǎn)相似性的鏈接預(yù)測[J].計(jì)算機(jī)科學(xué),2011，38(7)：162-164.

［4］Feng X,Zhao JC,Xu K.Link prediction in complex networks∶a clustering perspective[J].European Physical Journal B,2012,85∶3.

［5］李敏，張含會，費(fèi)耀平.融合PPI和基因表達(dá)數(shù)據(jù)的關(guān)鍵蛋白質(zhì)識別方法[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2013,44(3)：1024-1029.

［6］Zhou T,Lü L,Zhang Y-C.Predicting missing links via local information[J].European Physical Journal B,2009,71∶623-630.

［7］Cannistraci CV,Alanis-Lobato G,Ravasi T.From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J].Scientific Reports,2013,3∶1613.