非對稱信息在鏈接預測中的應用

謝 銳，郝志峰，劉 波，徐圣兵

(1.廣東工業大學自動化學院，廣州510006; 2.廣東工業大學計算機學院，廣州510006;3.佛山科學技術學院數學與大數據學院，廣東佛山528000)

(*通信作者電子郵箱25457855@qq.com)

0 引言

鏈接預測是揭示網絡演化內在規律的關鍵技術之一［1］。鏈接預測算法是基于觀察到的鏈接關系、節點的屬性和網絡的結構屬性來估計節點之間存在鏈接關系的可能性。它可以分為兩類:一種是預測缺失的鏈接或者存在但未知的鏈接，另一種是預測可能存在或出現在進化網絡中的未來的鏈接［2－3］。因此，理想的鏈接預測方法不僅可以應用于現有的鏈接可靠性的分析，還可以對缺失的或將來可能出現的鏈接進行預測。近年來，由于其在現代科學中的理論價值和實踐意義，鏈接預測的研究引起了國內外很多研究機構和學者的關注［2－3］，提出了應用于不同領域的鏈接預測方法，如用于社會基礎生活的社會網絡進化［4］、用于廣告和朋友圈等的推薦系統［5］、虛假鏈接檢測［6］等。

在上述的各文獻中，鏈接預測算法主要分為兩大類:其中，一類是基于馬爾可夫鏈［7］和機器學習［8］原理的，這些算法一般先提出適當的偏好假設，然后設計相應的損失函數或目標函數，再對兩個節點進行優化;但此類算法計算量大，難用于大規模網絡的鏈接預測。另一類是基于節點相似性來判斷［9－12］，這類算法計算簡單，認為如果兩個節點相似，則它們之間更可能存在鏈接關系。根據相似性進行鏈接預測的基本問題是如何準確計算節點之間的相似度［2－3］。

此外，還有基于矩陣分解的鏈接預測方法等，而基于節點相似的鏈接預測算法簡單、準確度高，是鏈接預測的重要方法，但目前的節點相似性度量算法中均認為節點之間的相似性是對稱的，并未充分考慮節點個體的所有鄰居與節點間共同鄰居(Common Neighbor，CN)之間的非對稱關系。本文在節點相似度的基礎上，充分考慮利用節點間的非對稱信息，對相似度算法進行改進，從而提高鏈接關系預測的準確度。

1 節點相似性度量

考慮一個無權無向的簡單網絡G(V，E)，不存在多鏈接和自我鏈接情形。V是節點集合，E是邊的集合。對于任意節點對x，y∈V，可以通過計算一個相似值來度量節點x和y之間是否存在邊的可能性。一般來說，如果兩個節點在拓撲或其他屬性中具有一些共同的重要特征，則認為它們是相似的。

目前，節點相似度的度量方法很多。最簡潔直接的方法是利用網絡結構相似信息進行度量，被稱為結構相似性［2－3］，它又可以分為節點相似性［10－15］、路徑相似性［16］和混合相似性［16］。其中，一些相似性度量方法是基于局部結構信息［10，13］，稱之為局部相似性，此類方法偏好度數大的節點，不利于度數小的節點。為了解決這個問題，研究者提出了諸如Jaccard指標［17］和 Salton 指標［18］等改進方法來克服這個缺點。另一些方法是基于全局結構信息進行相似性度量，包括Katz指標［16］、Simrank 指標［19］等，稱之為全局相似性，這些方法在估計節點相似度方面也具有較好的結果，但時間復雜度高，計算效率低，且獲取足夠節點的內容和屬性信息成本高、難度大，導致此類方法的相似性度量困難。此外，除了這些基于節點對相似性的預測方法外，還有基于似然分析的鏈接預測方法，包括層次結構模型［20］、隨機分塊模型［21］和閉路模型［22］等。

相似系數的概念常用來反映變量或對象的相似程度，在討論這些問題時認為變量或對象的相似程度是對稱的，變量或對象之間的相似系數是相同的。同樣，在基于節點對相似的方法中，均認為兩個節點相似，則相似程度是相同的，但實際上，相似節點間彼此的相似程度不一定是相同的。考慮如下甲和乙兩個對象的興趣愛好問題:甲的興趣為足球、籃球、乒乓球、羽毛球、音樂、美術、唱歌，相應的分值分別為10、8、8、5、4、2、1;乙的興趣為美術、唱歌、閱讀、旅游、乒乓球，相應的分值分別為 10、8、8、4、1。

基于共鄰的相似性度量方法建立在有共同鄰居(特征)的基礎上，認為兩者共同鄰居越多，兩者之間越相似。由于甲和乙都喜歡乒乓球、美術和唱歌，有3項相同的興趣愛好，則基于共鄰的方法認為甲和乙是相似的，這種相似信息是對稱的且只取決于相同興趣愛好的項目數，但它忽略了對象興趣愛好的廣泛性(興趣愛好數)、相同興趣愛好集合的總體喜歡程度(總分值)和每個興趣愛好的喜歡程度(分值)。例如，甲有7項興趣愛好，乙有5項興趣愛好，相同興趣愛好數與個體總興趣愛好數比值分別為3/7和3/5，即相同項目對于各自的興趣愛好的廣泛性的比值是不同的，它們是非對稱的;對于兩者之間的共同興趣愛好集合C={乒乓球、美術，唱歌}，甲的總的喜歡程度是11，乙的總的喜歡程度是19，表明甲、乙對于這個興趣愛好的集合的喜歡程度是不同的，是非對稱的;若考慮乒乓球這個興趣愛好，甲的喜歡程度是8，很喜歡;乙的喜歡程度是1，只是一般喜歡，。因此，他們對相同的一個興趣愛好的喜歡程度也是不同的，是非對稱的。從上述分析可以得到，基于共鄰的相似性度量認為相似程度是一樣的，即相似是對稱的，本質上只考慮了相同興趣愛好的項目數，沒有充分考慮個體這些非對稱信息，而這些非對稱信息可以更加細致刻畫兩者之間的相似程度。

本文提出了非對稱相似系數(Asymmetrical Similar Coefficient，ASC)概念來反映這種不同的相似信息，并結合傳統的相似性度量方法，修正相似度的計算方法，應用于基于節點相似性的鏈接預測方法中。在本文實驗中，將這種新方法與鏈接預測的常用方法進行了比較，包括共同鄰居(CN)［23］、Adamic Adar(AA)［4］、資源分配(Resource Allocation，RA)［13］等方法，發現新的方法可以提高鏈接預測準確度且具有運算速度快等特點。

2 非對稱相似系數

從前面的分析可以得到對象之間的相似可以認為是不同對象相對于共同特征的相似程度的反映。簡單起見，先考慮共同特征數(廣泛性)而不考慮每個特征的重要程度(分值)，則相似性可以表達為共同特征數與對象總特征數的比值，如圖1所示。

圖1 集合甲和集合乙特征分析Fig.1 Characteristic analysis of set A and set B

在圖1中，甲對象有8個特征，乙對象有4個特征，則甲對象對于共同的3個特征的相似值為3/8;而乙對象對于共同的3個特征的相似值為3/4，可以認為對于共同特征，乙比甲更相似;同理，相似性也可以表現為各個對象對共同特征的總體重要程度或者各個對象對每個特征的重要程度。據此，本文給出非對稱相似系數來刻畫對象之間的非對稱信息，非對稱相似系數(ASC)的定義如下:

非對稱相似系數(ASC)是指在不同集合中，所有集合的共同元素與某一集合的總元素的比值。即非對稱相似系數反映的是相對于具體集合而言，共同元素所占的比值。

在網絡拓撲中的含義為:Z設定為節點集合V;t為V中的某一節點;Γ(Z)為節點集合的共同鄰居;kt為節點t的度。在如圖2所示的簡單網絡中，A節點的鄰居是Γ(A)={B，C，D}，E節點的鄰居是Γ(E)={B，C}，節點A和E的共同鄰居是Γ(A)∩Γ(B)={B，C}，根據相似系數的定義，節點A對節點E的相似系數則為2/3，而節點E對節點A的相似系數為1，即兩者之間的相似系數是不同的，反映了兩個節點間的相似程度是不同的。

一般認為，無向無環圖中的相似性是對稱的。然而，從前面的分析來看，這種相似一般情況下相似程度是不同的，即相似中包含非對稱信息，只有當這兩個節點的度相等時，相似程度才相等，即相似對稱性只是一個特例。考慮到相似的非對稱信息，本文對一般的相似性度量方法進行修正，以更符合實際情況，因此相似性的修正定義如下:

其中:sxy是一般相似性度量方法得到的對稱相似值;是非對稱相似系數(ASC);是考慮相似的非對稱信息后得到的相似值。

圖2 簡單網絡Fig.2 Simple network

3 基于非對稱信息的相似度量

在基于網絡結構信息的相似算法中，共鄰指標(CN)、Adamic Adar(AA)指標和資源分配(RA)指標都是均勻地為所有鄰居節點分配權重，并將鄰居節點的數量視為鏈接相似性的因素。它們可以簡潔地度量節點之間存在鏈接的可能性，但是沒有充分考慮節點間的相似程度或其他因素;因此，可以對其進行修改，以更好地度量節點之間的相似度，進而更好地判斷節點之間是否存在鏈接關系。

3.1 CN 指標修正

式(5)的結果表明，傳統的相似對稱的情況是相似系數為1的特例，即不考慮相似程度的特例，而本文提出的非對稱相似程度的方法更能反映實際節點之間的相似性，此方法更進一步可以擴展到考慮節點及節點屬性的整體對象相似程度的度量。

3.2 AA 指標修正

AA指標對每個節點均勻分配權重，以共同鄰居節點度的對數的倒數為權重值，并以這個值定義為節點間的相似值。考慮到節點間的不同相似程度，本文方法對AA指標可以采用非對稱相似系數(ASC)進行修正，定義如下:

3.3 RA 指標修正

RA指標從資源的角度出發，將共同鄰居節點作為傳遞的媒介，以共同鄰居節點度的倒數為相似值，考慮到節點間的不同相似程度，本文方法對RA指標可以采用非對稱相似系數(ASC)進行修正，定義如下:

3.4 考慮非對稱信息的相似性

在傳統的對稱相似性度量中，變量或對象之間的相似是對稱的，只有一個相似值;而考慮變量或對象之間的非對稱信息后，相似是非對稱的，在這種情況下，變量或對象之間的相似度量應考慮方向性，因此，考慮非對稱信息后的相似性是具有方向性的。

在本文的討論中，判斷兩個節點之間的非對稱相似時，應指出節點之間的相對方向性。例如(x)x) 和(x)是考慮非對稱相似系數時節點x相對于節點y的相似值;(y)(y)和(y)是考慮非對稱相似系數時節點y相對于節點x的相似值。

4 實驗結果與分析

為了分析本文提出的算法的性能，本文在4個真實數據集上與參考文獻［25］中涉及的8種算法進行了比較。本文實驗環境為 Windowns 7 64 位、CPU i3-2350M@2.3 GHz、6 GB內存，Matlab 2014為實驗仿真工具。實驗中，將數據集E隨機劃分為訓練集ET和測試集EP兩部分，且E=ET∪EP，ET∩EP= 。對于節點對x，y∈V，采用本文提出的方法和現有方法分別計算相似值sxy，將所有不存在的鏈接根據其相似分數sxy按降序排列，則排在最前面的鏈接最有可能存在。

4.1 評價指標

衡量鏈接關系預測算法精度的常用指標主要包括3種:受試者工作特征曲線下的面積(Area Under the receiver operating characteristic Curve，AUC)［26］、精確度和排序分。AUC側重算法整體準確度，精確度指標側重前L位準確度，排序分側重所預測的邊。本文采用AUC衡量鏈接預測算法整體準確度。AUC定義如下:

其中:n表示獨立地比較了n次;n'表示在n次比較中測試集中的邊的分數值大于不存在的邊的分數出現的次數;n″表示在n次比較中測試集中的邊的分數值等于不存在的邊的分數出現的次數。式(10)的含義是，如果所有的鏈接預測分數都是從一個獨立同分布中產生的，其準確率應該是0.5左右，因此，若算法精確度超過0.5則表明該算法執行的效果比純粹的機會要好得多［26］。

4.2 實驗數據集

為了評價基于非對稱相似系數的鏈接預測算法的有效性，本文選擇了4種類型的代表性真實數據集，并根據實驗條件進行了簡單抽樣后進行實驗，數據特征描述如下:

1)美國航空網絡 USAir(http://vlado.fmf.uni-lj.si/pub/networks/data/mix/USAir97.net):該網絡中的每一個節點對應一個機場，若兩個節點之間有連邊則兩個機場之間有直飛的航班。包含332個機場和2126條航線，權重為航班頻次。

2)科學家合作網絡 NS(http://www-personal.umich.edu/～mejn/netdata/):網絡的節點表示科學家，連邊表示科學家之間的合作關系。該網絡包含379個節點和914條邊。

3)蛋白質相互作用網絡 Yeast(http://vlado.fmf.uni-lj.si/pub/networks/data/bio/Yeast/Yeast.htm):節 點 表 示 蛋 白質，邊表示相互作用關系。該網絡包含2617個節點和11855條邊。

4)爵士音樂家合作網絡 Jazz(http://deim.urv.cat/～aarenas/data/welcome.htm):網絡的節點表示音樂家，連邊表示音樂家之間的合作關系。該網絡包含198個節點和5 484條邊。

4.3 實驗結果

實驗測試了本文提出的考慮非對稱信息后節點相似性的鏈接預測算法在不同條件下的性能。在所有測試實驗過程中，每個實驗進行100次，AUC取平均值。

4.3.1 訓練集比例不同

首先，測試考慮非對稱信息后基于節點相似性的鏈接預測方法在數據集USAir中當訓練集比例不同時AUC的表現，實驗結果如圖3所示。

圖3 USAir數據集中AUC與訓練集比例關系Fig.3 Relationship of AUC and training set ratio in dataset USAir

從圖3可以看出，當訓練集合的比例為0.6時，ASCCN、ASCRA和ASCAA的鏈接預測準確度AUC超過90%，當訓練集比例0.9時，ASCCN、ASCRA和ASCAA的鏈接預測準確度AUC值已經達到95%以上。在另外3個數據集中也可以得到相近的結論。實驗結果表明，考慮非對稱信息后的基于節點相似性的鏈接預測算法準確性AUC的值隨著訓練集比例的增大而上升。

4.3.2 訓練集比例恒定

基于圖3所示的訓練集比例不同的實驗結果，選擇訓練集比例c=0.9，測試本文所提出的方法在不同數據集中的鏈接預測準確度AUC。實驗測試了ASCCN指標、ASCSalton指標、ASCJaccard指標、ASCSorenson指標、ASCHPI指標、ASCHDI指標、ASCAA指標、ASCRA指標等共8個指標，實驗結果如表1所示。

表1 基于相似系數的鏈接預測準確度AUCTab.1 AUC in link prediction accuracy based on similarity coefficient

從表1可以看出，本文所提方法在不同數據集中的鏈接預測準確度可以達到90%，在科學家合作網絡NS數據集已經達到99%以上，說明本文所提方法在在多個數據集上均可以達到理想的預測效果，表明該方法可以適用于各種不同的數據集，滿足各類應用要求。

4.3.3 與其他算法的比較

為了驗證本文提出方法的有效性，根據參考文獻［25］中基于共鄰相似性度量的8種不同鏈接預測算法分別進行改進，并在4個真實數據集中分別完成了8組對比實驗。實驗的結果如表2所示。

從表2的實驗結果可以看出，同一方法在不同數據集上的預測準確度有所不同，在NS數據集上的預測準確度最高，達到99%以上，而在USAir數據集上不同方法的預測準確度變化最大。本文提出的基于相似系數的方法在同一數據集上總體上均優于其他方法的預測準確度。

其中，相比CN算法，考慮非對稱信息后的算法SCCN的預測準確度在USAir數據集上提高了0.649 8%，在NS數據集上提高了0.0202%，在Yeast數據集上提高了0.0109%，在Jazz數據集上提高了1.129 5%。在考慮非對稱信息后的算法SCAA相比現有AA算法的預測準確度在USAir數據集上提升了0.2173%，而在 NS數據集和Yeast數據集上與現有AA算法相同，在Jazz數據集上預測準確度提升了0.6954%;在考慮非對稱信息后的算法SCRA相比現有RA算法的預測準確度在USAir數據集上提升了0.113 1%，在NS數據集上與現有RA算法相同，在Yeast數據集和Jazz數據集上預測準確度分別提升了0.0109%和0.2572%。此外，表2所示的實驗結果表明改進后算法在不同數據集上的預測準確度均獲得了不同幅度的提升，排除了算法在不同數據集上準確度隨機提升的可能，說明本文提出的考慮非常對稱信息的鏈接預測算法具有穩定的準確度提高效果。

表2 算法改進前后的AUC比較Tab.2 AUC comparison before and after algorithm improvement

5 結語

本文分析了節點之間的相似程度的問題，發現節點相似性具有非對稱信息，提出了考慮非對稱信息后的相似性度量方法，在此基礎上，設計了一種新的相似性度量方法，給出了考慮非對稱信息后的基于節點相似性的鏈接預測新方法。在真實數據集的實驗表明，所提方法可以一定程度上提高鏈接預測的準確性。此外，非對稱信息思想也可以進一步擴展到節點重要程度、節點之間的傳播等因應用中。本文所提方法的算法復雜度基于原算法復雜度O(n2)，對于大規模網絡處理效率不夠高，后續將重點關注相似系數，探討特征的重要程度對相似性度量的影響，并尋找降低算法復雜度的方法。