融合聚集系數的鏈接預測方法

劉昱陽，李龍杰，單 娜，陳曉云

(蘭州大學 信息科學與工程學院，蘭州 730000)

0 引言

鏈接預測[1]是復雜網絡分析中的重要研究方向，得到了越來越多的關注。鏈接預測根據網絡中已知信息預測網絡中丟失的鏈接或者未來可能出現的鏈接，在網絡分析中起著非常重要的作用，可以用于指導生物實驗、重建網絡結構以及模擬網絡演化等。鏈接預測在許多實際問題中都有很高的應用價值，不同領域的學者都可以利用其作為工具輔助本領域的研究。例如，在生物學領域，生物學家可以利用鏈接預測篩選潛在的蛋白質相互作用關系[2]和進行腦功能網絡研究[3]，能夠減少實際實驗的次數以及降低實驗成本。對于在線社交網絡[4]、電子商務網絡[5]和航空運輸網絡[6]，都可以利用鏈接預測來增加其商業價值。在在線社交網絡中，鏈接預測可以發現用戶的潛在朋友[7]，并通過把預測結果推薦給用戶的方式來增加用戶關聯，同時用于提高用戶的活躍度與忠誠度。

截至目前，學者們提出了大量基于相似性的鏈接預測方法，這些方法給節點對分配相似性分數，利用所分配的分數估計兩個節點間存在鏈接的可能性，節點間的相似性分數越高，它們之間存在鏈接的可能性就越大。基于網絡結構特征評估節點間的相似性是目前的一個主要研究方向。共同鄰居(Common Neighbors，CN)指標[8]是其中最簡單的一個，它基于兩個節點共同鄰居的數量進行預測，共同鄰居數量越多，這兩個節點間存在鏈接的可能性就越高。相關方法還有考慮對大度節點進行懲罰的資源分配(Resource Allocation, RA)指標[9]以及AA(Adamic-Adar)指標[10]等。上述方法基于節點的共同鄰居信息，而局部路徑(Local Path, LP)指標[9]、Katz指標[11]等考慮節點間的路徑信息。除此之外還有基于隨機游走的相似性指標，如平均通勤時間(Average Commute Time, ACT)指標[12]、基于隨機游走的余弦相似性(Cos+)指標[13]、有重啟的隨機游走(Random Walk with Restart, RWR)指標[14]和SimRank指標[15]等。以及基于網絡局部隨機游走的LRW(Local Random Walk)指標[16]和SRW(Superposed Random Walk)指標[16]。

節點的聚集系數是一種常用的網絡結構信息，用于度量節點的鄰居之間鏈接的密度。許多鏈接預測模型使用節點的聚集系數來評估該節點的兩個鄰居之間存在鏈接的概率。基于聚集系數的鏈接預測方法(Clustering Coefficient for Link Prediction，CCLP)[17]將兩個節點的共同鄰居的聚集系數之和作為這兩個節點的相似度值。局部樸素貝葉斯(Local Naive Bayes, LNB)模型[18]利用貝葉斯分類器理論計算節點間存在鏈接的可能性。該模型認為不同的鄰居對相似性的計算可能有不同的貢獻，并使用鄰居的聚集系數來表示其貢獻。中間概率(InterMediary Probability, IMP)模型[19]是一種廣義的概率評估模型，它可以根據節點間的不同特征來評估其存在概率的可能性。IMP_CN(InterMediate Probability model based on Common Neighbor)是基于IMP模型衍生的鏈接預測算法[19]，該算法將節點間的共同鄰居作為特征，鄰居的聚集系數作為中間概率。最近，Wu等[20]定義了非對稱鏈接聚集系數(Asymmetric Link Clustering Coefficient, ALCC)，該聚集系數計算經過一條鏈接的三角形的概率。與文獻[21]中提出的鏈接聚集系數不同，ALCC將鏈接的一個端點定義為要預測鏈接的節點，另一個端點為鄰居節點。用ALCC替換了CCLP方法、LNB模型中節點的聚集系數，提升了鏈接預測的精度[20]。

節點的聚集系數與非對稱鏈接聚集系數從不同的角度度量了兩個節點間存在鏈接的可能性。本文考慮將兩者進行結合以得到一個綜合的度量指標，并使用該指標評估節點間存在鏈接的可能性。本文方法使用Dempster-Shafer(DS)證據理論[22]將兩種聚集系數進行融合，并且將融合后的度量指標引入到IMP模型[19]中設計了一個新的鏈接預測方法。為驗證本文所提方法的性能，在多個網絡數據上進行了實驗，結果表明，與其他方法相比，本文提出的方法取得了較好的預測效果。

1 相關工作

1.1 IMP_CN算法

IMP算法是一種廣義的概率模型，可以利用不同的網絡特征評估節點間存在鏈接的可能性，IMP模型公式如式(1)：

(1)

(2)

(3)

1.2 CN指標

CN指標認為：兩個不連接的節點如果有更多的共同鄰居，則它們更傾向于連邊。CN指標定義兩個節點x和y的相似性為其共同鄰居的數量，即：

Sxy=|Oxy|

(4)

1.3 AA指標

AA(Adamic-Adar)指標認為度小的共同鄰居的貢獻大于度大的共同鄰居，因此為每個鄰居節點賦一個權重值。該權重等于該節點的度的對數的倒數，其定義為：

(5)

1.4 RA指標

RA(Resource Allocation)指標受網絡中資源分配過程的啟發。考慮網絡中不相連的兩個節點x和y，從x可以傳遞一些資源到y，在這個過程中，共同鄰居就成為資源傳遞的媒介。假設每個媒介將得到的資源平均分配給它的鄰居，則y可以接收到的資源數就定義為節點x和y的相似度，即：

(6)

2 Dempster-Shafer證據理論

Dempster-Shafer(DS)證據理論，以其表示和處理不確定信息的能力而聞名，DS融合規則可以使命題得到不同來源信息的綜合支持度。最早應用于專家系統中，用于根據多個信息源的不確定性信息[23]作出決策。例如，針對供應商選擇問題，Liu等[24]提出了一種模糊拓展分析網絡方法，該方法利用DS證據理論解決專家判斷中的認知不確定問題。DS證據理論還應用于處理傳感器信息融合系統中的不確定性，Ye等[25]提出了一種基于灰色關聯和DS證據理論的不確定性融合算法，解決了傳感器之間的不一致性和監測環境的復雜性帶來的不確定性問題。Jiang等[26]將Z-number模型與DS證據理論進行結合，對傳感器數據融合系統中的不確定性進行建模和處理，提高了故障檢測的可靠性。此外，DS證據理論還用于解決服務器集群負載不均衡的問題[27]。為了更好地解釋DS證據理論，本文接下來介紹一些相關概念。

定義1 識別框架(Frame Of Discernment, FOD)。給定一組基本的命題E1,E2,…,Ei,…,En，命題Ei是Φ的基本元素，表示如下：

Φ={E1,E2,…,Ei,…,En}

(7)

要求Φ中的元素是相互排斥的并且是完備的。在DS理論中，Φ被就稱為識別框架。符號2Φ表示Φ的冪集：

2Φ={?,{E1},{E2},…,{En},{E1,E2},…,Φ}

(8)

其中?表示空集。

定義2 基本概率分配函數。在識別框架Φ上的基本概率分配函數是一個從2Φ到[0,1]的映射函數，用于給各命題分配信任程度，記作m：

m:2Φ→[0,1]

(9)

此函數滿足如下性質:

其中m(A)反映對命題A的信任程度大小。

定義3 Dempster合成規則。給定兩個獨立的基本概率分配函數m1和m2，Dempster合成規則根據m1、m2產生一個新的基本概率分配函數，新的基本概率分配函數表示為m=m1⊕m2，具體公式如下：

(10)

(11)

Dempster合成規則既滿足結合律，又滿足交換律：

m1⊕m2=m2⊕m1

(12)

(m1⊕m2)⊕m3=m1⊕(m2⊕m3)

(13)

3 本文方法

在鏈接預測中，節點聚集系數和非對稱鏈接聚集系數分別從不同的角度定義了共同鄰居對兩個節點之間是否存在鏈接的評估。本文利用DS證據理論將兩者進行融合得到一個綜合性度量指標，利用該指標去評估節點間存在鏈接的概率。最后將融合后的度量指標與IMP模型相結合，設計了一個新的鏈接預測方法，記為IMP_DS。接下來，首先對兩種聚集系數進行介紹，然后給出IMP_DS方法的流程，并通過例子演示了IMP_DS方法的計算過程。

3.1 節點聚集系數

聚集系數用于衡量網絡中節點的聚集程度，其定義建立在網絡中的“三角形”結構之上。節點的聚集系數定義為該節點與其鄰居之間組成的三角形的個數與所有可能的三角形個數之比。給定節點z，其聚集系數的計算如式(12)所示：

(14)

其中：N△表示節點z與其鄰居之間的三角形個數；kz表示節點z的度，kz(kz-1)/2表示最大可能的三角形個數。

3.2 非對稱性鏈接聚集系數

非對稱鏈接聚集系數[20]的定義原理與節點的聚集系數相似，其定義為通過一條鏈接的三角形個數除以可能的最大三角形個數。這里，最大三角形個數只與節點對中的某一點相關，這個點為共同鄰居節點。給定節點x與y，z是它們的一個共同鄰居，鏈接(x,z)的非對稱聚集系數定義為：

(15)

其中：Oxz表示節點x和z的共同鄰居集合；|Oxz|表示集合Oxz中元素數量。

式(13)表明，LCx,z是非對稱的，只在節點x與節點z的度相同時LCx,z與LCz,x才相等。本文使用的鏈接聚集系數分別為LCx,z與LCy,z。

3.3 IMP_DS方法

給定節點x與y，z為它們的一個共同鄰居。Cz、LCx,z和LCy,z從不同的角度度量了x、y之間存在鏈接的概率。本文將三種聚集系數進行融合得到一個新的度量指標，然后將融合后的指標引入IMP模型中，設計一個新的鏈接預測方法。本文方法包含三步，具體的過程介紹如下。

1)首先，將鄰居z的兩個非對稱鏈接聚集系數相結合，得到z的平均鏈接聚集系數LCz，定義如下:

(16)

(17)

(18)

以及

(19)

(20)

定義mf為融合后的基本概率分配函數，則：

(21)

(22)

(23)

接下來通過一個例子描述IMP_DS方法的計算過程。

例1 利用IMP_DS算法計算節點的相似性。在圖1所示的網絡中，節點對(x,y)有4個共同鄰居，分別是z1,z2,z3,z4。使用IMP_DS算法評估x、y之間的相似性，首先計算4個鄰居的節點聚集系數和鏈接聚集系數，結果如下：

圖1 描述IMP_DS計算過程的示意網絡Fig. 1 Schematic network used to show computation process of IMP_DS

之后對每一個共同鄰居的節點聚集系數與鏈接聚集系數進行融合，得到相應的融合概率，結果如下：

將融合后的概率代入IMP_DS的計算公式中，得到節點對(x,y)相似性分數為：

4 實驗數據集與評價指標

4.1 數據集

本文選取了9個真實網絡進行實驗及分析，網絡的簡單介紹如下。

1)Florida[28]：弗洛里達海灣雨季的食物鏈網絡。

2)Word[29]：小說《大衛·科波菲爾》中常見形容詞和名詞的鄰接網絡。

3)Karate[30]：70年代美國一所大學空手道俱樂部34名成員之間的友誼網絡。

4)Cypwet[31]：賽普拉斯海灣雨季食物鏈網絡。

5)Jazz[32]：爵士樂音樂家之間的協作網絡。

6)Celegansneural(CE)[33]：線蟲Caenorhabditis elegans的神經網絡。

7)Polblogs(PB)[34]：政治博客網絡。

8)Yeast[29]：酵母蛋白質相互作用網絡。

9)Lesmis[35]：小說《悲慘世界》中人物的同時出現的網絡。

表1展示了9個網絡的基本拓撲結構，其中：|V|表示網絡的節點數量，|E|表示網絡中鏈接數量，C表示網絡的平均聚集系數，r表示網絡的同配系數，k表示節點的平均度，d表示平均最短距離，Nd表示網絡密度。

4.2 評價指標

本文采用受試者工作特征(Receiver Operating Characteristic, ROC)曲線下方面積(Area Under the ROC Curve, AUC)[36]與精度值(Precision)[37]兩種指標衡量鏈接預測算法的性能。實驗中，將網絡中的鏈接集合隨機劃分為訓練集Etr與測試集Ets，其滿足：

Etr∪Ets=E

(24)

Etr∩Ets=?

(25)

AUC是一種依靠整體排名結果的度量，類似于概率。具體定義如下：進行n次獨立比較，每次獨立比較都從測試集和不存在的鏈接中分別取一條鏈接，鏈接預測算法根據訓練集信息分別對兩條鏈接進行評分。如果一個算法有較好的預測性能，測試集中鏈接的對應指標分數應該比不存在的鏈接的分數要高。因此，假設在n次獨立比較中，測試集鏈接比不存在鏈接擁有更高分數n′次，兩者擁有相同分數n″次，則對應AUC的計算公式如下：

(26)

AUC值越高，鏈接預測算法的預測準確度越高。隨機預測的AUC值約等于0.5，因此AUC大于0.5的程度表明了相應算法在多大程度上比隨機預測的方法更精確。

Precision定義為將訓練集與網絡中所有不存在鏈接按照相似性分數進行降序排列，計算前L個鏈接中屬于訓練集的鏈接所占比例。如果排名前L的鏈接中有l個屬于測試集，則Precision計算公式為：

(27)

5 實驗結果及分析

以AUC與Precision為衡量指標，在9個真實網絡中測試IMP_DS算法的預測效果，具體結果分為兩部分：一是在不同網絡中IMP_DS與其他相似性指標的對比結果分析；二是IMP_DS性能提升的原因分析。

5.1 與其他相似性指標對比

表2給出了CN、AA、RA、IMP_CN以及IMP_DS 5種算法在各個網絡上的AUC與Precision的實驗結果，表中加粗字體表明效果最好。兩個表中的結果均為50次獨立實驗的平均值，每次實驗中，原始網絡被隨機地劃分為一個訓練集和一個測試集，其中訓練集占90%的鏈接，測試集占10%的鏈接。表2中的Precision是取L=10時的實驗結果。

從表2中可以看出，IMP_DS算法在Florida、Word、Cypwet、CE和PB 5個網絡上取得最好的AUC結果。在Karate上，RA的AUC值最高，IMP_DS第二。在其他3個網絡上，IMP_DS的性能與IMP_CN非常接近。結果表明融合兩種聚集系數的方法在IMP模型上是可行的，并且比單一的節點聚集系數的效果更好。特別地，在Florida和Cypwet兩個網絡上，與其他算法相比，IMP_DS的AUC結果提升非常明顯。從表1中可以看到：Florida和Cypwet兩個網絡的密度非常高，是兩個非常稠密的網絡，因此，兩個網絡的節點聚集系數和鏈接聚集系數都非常高，通過融合節點聚集系數和鏈接聚集系數能夠顯著提高鏈接預測的性能。相反地，在Yeast這個特別稀疏的網絡上，IMP_DS以及IMP_CN兩個方法的AUC值均低于CN、AA和RA三個方法。這是因為稀疏網絡上的節點間的共同鄰居數據很少，并且節點的聚集系數和鏈接聚集系數的值也變得非常低，降低了IMP模型的性能[19]。

表2中的Precision結果再次證明IMP_DS方法的預測精度高于對比算法。例如，在Florida網絡上，IMP_DS方法的預測精度相比CN、AA、RA和IMP_CN算法分別提高了130.9%、139.5%、169.4%和106.4%，因此本文認為融合共同鄰居的節點聚集系數與非對稱鏈接聚集系數能夠明顯提高IMP模型的預測精度。

接下來，在9個網絡上選取不同比例的訓練集進行實驗，觀察AUC的結果與變化趨勢。本實驗的結果也是50次獨立實驗的平均值。圖2描述了從E中選取不同比例訓練集Etr(從0.7到0.9)時各預測方法AUC的變化情況。從圖2中可以看出，在不同比例訓練集的情況下，IMP_DS在超過一半的網絡上都獲得了較高的AUC值。觀察AUC的變化趨勢發現，當訓練集的比例從0.7上升到0.9時，AUC值呈明顯上升趨勢。這是因為，訓練集Etr的比例越大，為訓練提供的信息越多，預測越準確；相反，低比例的Etr會增加鏈接預測的難度[38]。

圖2 不同比例訓練集時的AUC結果Fig. 2 AUC values under different proportions of training set

圖3描述訓練集Etr的比例從0.7增長到0.9時Precision的變化趨勢，L的值同樣設置為10。

從圖3中可以看出，與AUC相比，Precision隨著訓練集比例變化呈現相反的變化趨勢，即當比例從0.7上升到0.9時，Precision值呈現下降趨勢。這是因為訓練集Etr的減少會導致AUC定義中n′與n″變小，從而降低AUC的值[39]，但是，隨著測試集Ets的提高(訓練集Etr減小)，獲得相關信息的可能性增加，使得發現缺失鏈接更容易[39]。比較各個方法的Precision值，整體而言，IMP_DS在不同比例訓練集上的性能均優于對比方法。

圖3 不同比例訓練集時的Precision結果Fig. 3 Precision values under different proportions of training set

圖4顯示了在取不同L值時每個方法的Precision值及變化趨勢。圖4中，訓練集與測試集的比例為9∶1，結果仍然是50次獨立實驗的平均值。這里，只給出了在6個較大網絡上的實驗結果。從圖4中可以看出，在這6個網絡上，IMP_DS的性能具有明顯的優勢，尤其是在Flodria、Cypwet和PB 3個網絡中，其Precision值顯著高于對比方法。在不同的網絡上，其他方法的排序隨著L取值改變有較大變化。例如，在PB網絡上，隨著L的改變各種方法的排序基本不變，但是在Jazz與CE網絡上，4種對比方法的排序有很大波動。另外，在大多數網絡中，隨著L值的增大，Precision呈現逐漸下降的趨勢。這是因為L的增加，使得發現丟失鏈接的概率降低，從而導致精度值降低[38]。

5.2 IMP_DS性能提升原因分析

最后，通過實例分析的方式進一步研究IMP_DS性能提升的原因。參考文獻[19]中的分析方法，圖5選取了四個對比算法預測的前100條鏈接，并將這100條鏈接在不同算法的排名進行對比。本文實驗中，將PB隨機劃分成一個訓練集和一個測試集，訓練集和測試集的比例是9∶1。圖5中，使用半對數坐標繪制了每一對算法預測的前100條鏈接的相對排序。以圖5(c)(d)子圖為例，(c)子圖表示AA預測的前100條鏈接在IMP_DS結果中的排序，(d)子圖表示IMP_DS預測的前100條鏈接在AA結果中的排序。觀察圖中的結果可以發現，AA預測的前100條鏈接中，41條是正確的，59條是錯誤的，而IMP_DS將這些錯誤結果中的大部分排在了100～1 000。另一方面，IMP_DS預測的前100條鏈接中，52條是正確的，48條是錯誤的，而AA將正確預測結果中的20條排在了100以外，因此，IMP_DS能夠取得比AA更高的預測精度。其他三個子圖上的結果也與此類似。

圖5 各算法在PB網絡上預測的前100條鏈接的對比Fig. 5 Comparison of top- 100 predicted links of different algorithms on PB network

6 結語

針對許多基于網絡結構信息的鏈接預測算法只考慮節點的聚集系數，而忽略了預測節點與共同鄰居節點之間鏈接的聚集系數對鏈接預測影響的問題，本文提出了一種基于Dempster-Shafer證據理論，融合節點聚集系數和非對稱鏈接聚集系數的鏈接預測算法。首先，針對每個共同鄰居節點計算出對應的聚集系數和平均鏈接聚集系數；然后，將兩種聚集系數進行融合得到一個綜合性度量指標；最后將這個綜合性度量指標應用于中間概率模型，得到一個新的節點間相似性指標。在9個真實網絡數據上的實驗結果表明，IMP_DS方法具有較高的AUC與Precision值，可以用于復雜網絡鏈接預測。盡管本文設計的融合兩種聚集系數的鏈接預測算法取得了優秀的預測效果，但仍有許多問題待解決，例如可以進一步研究不同特征的融合以及具體融合過程對鏈接預測效果的影響。