復雜網絡中集聚系數對鏈路預測算法的影響

黃子軒 馬 超 徐瑾輝 黃江楠

（廣東外語外貿大學 思科信息學院，廣東 廣州 510006）

0 引言

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

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

如今多數工作都是針對新的鏈路預測算法的提出，較少工作揭示出研究不同的網絡結構與算法選擇之間的關系。本文基于真實網絡和模擬網絡上的實驗，對網絡的節點集聚系數、邊集聚系數與鏈路預測算法之間的關系進行分析，并研究何時需要考慮共同鄰居之間的相互關系[4]。

1 問題描述

定義G(V,E)為一個無向網絡，其中V為節點集合，E為邊集合。網絡的總節點數為N，邊數為M。該網絡共有N(N-1)/2個節點對，即全集U。這樣，鏈路預測問題可描述為：構建某種相似度指標，對沒有連邊的節點對(x,y)計算其相似度Sxy，Sxy越大，節點對(x,y)出現連邊的概率越大。

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

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

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

邊集聚系數刻畫了兩個節點之間聯系的緊密程度，而聚集效應是復雜網絡中的一個重要性質。網絡的平均邊集聚系數刻畫出網絡整體的緊密程度，因此，本文認為網絡的平均邊集聚系數能較好地區分出不同結構的網絡[5]。本文涉及到以下8種相似性指標：

CN指標：該指標定義為兩個節點的共同鄰居數量。對于節點i，定義i的鄰居集合為Г(i)，設節點x和y節點的相似性為Sxy，即Sxy=

CAR指標[7]：該指標以CN指標為基礎，加以考慮共同鄰居間的相互關系，定義如下：

其中，γ(z)為節點z與兩端節點以及其余共同鄰居之間的連接數。CAA指標：該指標以AA指標為基礎，加以考慮共同鄰居之間的相互關系，定義如下：

CRA指標：該指標以RA指標為基礎，加以考慮共同鄰居之間的相互關系，定義如下：

CCC指標：該指標以CC指標為基礎，加以考慮共同鄰居之間的相互關系，定義如下：

3 模擬網絡實驗

3.1 數據集

復雜網絡普遍存在于真實社會中，為了充分考慮不同類型的網絡，本文首先通過pajek生成的小世界網絡進行模擬。其中，本文通過軟件生成的小世界網絡的設置均為200個節點，節點平均度分別為20和30。表1為節點平均度為20的小世界網絡的拓撲信息和實驗結果，表2為節點平均度為30的小世界網絡的拓撲信息和實驗結果。將上述8種算法在小世界網絡中進行實驗，并比較準確率。在AUC測試正確率中，對原始數據集進行了隨機抽取分成了訓練集（含90%的連邊數）和測試集（含10%的連邊數）兩部分，隨后進行了105次的隨機抽樣比較。

3.2 實驗結果

表1 小世界網絡（K=20）的拓撲信息和實驗結果

表2 小世界網絡（K=30）的拓撲信息和實驗結果

3.3 實驗分析

由表1和表2可以看出，隨著網絡的平均節點集聚系數的增大，網絡的平均邊集聚系數也在增大，各個鏈路預測算法的準確性也在提高。小世界網絡的平均節點集聚系數與平均邊集聚系數較為接近。在小世界網絡中，當網絡的平均節點集聚系數較為低的時候，這四種改進后的算法比原算法有更好的表現，但隨著網絡的平均節點集聚系數的提高，突出程度則在降低。因此，本文認為對于有較低的平均節點集聚系數的網絡，考慮共同鄰居之間的相互關系能更好地表現出節點之間的連接緊密性。對于高平均節點集聚系數的網絡，因其網絡本身擁有較好的緊密性，再加以考慮共同鄰居之間的相互關系對于提高算法有效性的用處不大。

4 真實網絡實驗

4.1 數據集

本文使用了4個真實網絡：adjnoun網絡、football網絡、polbooks網絡、US power grid網絡進行實驗，對上一小節實驗分析進行驗證。這里，我們仍采用上述8種算法在各個網絡中進行實驗，并比較準確率。在AUC測試正確率中，對原始數據集進行了隨機抽取分成了訓練集（含90%的連邊數）和測試集（含10%的連邊數）兩部分，隨后進行了105次的隨機抽樣比較，表3為4個真實網絡的實驗結果。

4.2 實驗結果

表3 4個真實網絡的拓撲信息和實驗結果

4.3 實驗分析

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

5 總結

在復雜網絡的鏈路預測研究中，以前的工作主要集中提出新的鏈路預測算法。不同于此，為了更好地理解算法與網絡之間的聯系，本文以集聚系數為切入點，研究了其對鏈路預測算法的影響，加深理解影響算法準確性的因素，以及算法的適用范圍。本文工作綜合考慮了網絡結構的多樣性以及算法的適用性，對鏈路預測算法與網絡結構之間的聯系進行深入的研究。實驗表明：模擬實驗的結論同樣適用于真實網絡，對于鏈路預測的研究有重要的參考價值。

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

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

［3］東昱曉，柯慶，吳斌.基于節點相似性的鏈接預測[J].計算機科學,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］李敏，張含會，費耀平.融合PPI和基因表達數據的關鍵蛋白質識別方法[J].中南大學學報：自然科學版，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.