非對稱信息在鏈接預(yù)測中的應(yīng)用

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

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

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

0 引言

鏈接預(yù)測是揭示網(wǎng)絡(luò)演化內(nèi)在規(guī)律的關(guān)鍵技術(shù)之一［1］。鏈接預(yù)測算法是基于觀察到的鏈接關(guān)系、節(jié)點的屬性和網(wǎng)絡(luò)的結(jié)構(gòu)屬性來估計節(jié)點之間存在鏈接關(guān)系的可能性。它可以分為兩類:一種是預(yù)測缺失的鏈接或者存在但未知的鏈接，另一種是預(yù)測可能存在或出現(xiàn)在進(jìn)化網(wǎng)絡(luò)中的未來的鏈接［2－3］。因此，理想的鏈接預(yù)測方法不僅可以應(yīng)用于現(xiàn)有的鏈接可靠性的分析，還可以對缺失的或?qū)砜赡艹霈F(xiàn)的鏈接進(jìn)行預(yù)測。近年來，由于其在現(xiàn)代科學(xué)中的理論價值和實踐意義，鏈接預(yù)測的研究引起了國內(nèi)外很多研究機構(gòu)和學(xué)者的關(guān)注［2－3］，提出了應(yīng)用于不同領(lǐng)域的鏈接預(yù)測方法，如用于社會基礎(chǔ)生活的社會網(wǎng)絡(luò)進(jìn)化［4］、用于廣告和朋友圈等的推薦系統(tǒng)［5］、虛假鏈接檢測［6］等。

在上述的各文獻(xiàn)中，鏈接預(yù)測算法主要分為兩大類:其中，一類是基于馬爾可夫鏈［7］和機器學(xué)習(xí)［8］原理的，這些算法一般先提出適當(dāng)?shù)钠眉僭O(shè)，然后設(shè)計相應(yīng)的損失函數(shù)或目標(biāo)函數(shù)，再對兩個節(jié)點進(jìn)行優(yōu)化;但此類算法計算量大，難用于大規(guī)模網(wǎng)絡(luò)的鏈接預(yù)測。另一類是基于節(jié)點相似性來判斷［9－12］，這類算法計算簡單，認(rèn)為如果兩個節(jié)點相似，則它們之間更可能存在鏈接關(guān)系。根據(jù)相似性進(jìn)行鏈接預(yù)測的基本問題是如何準(zhǔn)確計算節(jié)點之間的相似度［2－3］。

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

1 節(jié)點相似性度量

考慮一個無權(quán)無向的簡單網(wǎng)絡(luò)G(V，E)，不存在多鏈接和自我鏈接情形。V是節(jié)點集合，E是邊的集合。對于任意節(jié)點對x，y∈V，可以通過計算一個相似值來度量節(jié)點x和y之間是否存在邊的可能性。一般來說，如果兩個節(jié)點在拓?fù)浠蚱渌麑傩灾芯哂幸恍┕餐闹匾卣?，則認(rèn)為它們是相似的。

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

相似系數(shù)的概念常用來反映變量或?qū)ο蟮南嗨瞥潭?，在討論這些問題時認(rèn)為變量或?qū)ο蟮南嗨瞥潭仁菍ΨQ的，變量或?qū)ο笾g的相似系數(shù)是相同的。同樣，在基于節(jié)點對相似的方法中，均認(rèn)為兩個節(jié)點相似，則相似程度是相同的，但實際上，相似節(jié)點間彼此的相似程度不一定是相同的?？紤]如下甲和乙兩個對象的興趣愛好問題:甲的興趣為足球、籃球、乒乓球、羽毛球、音樂、美術(shù)、唱歌，相應(yīng)的分值分別為10、8、8、5、4、2、1;乙的興趣為美術(shù)、唱歌、閱讀、旅游、乒乓球，相應(yīng)的分值分別為 10、8、8、4、1。

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

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

2 非對稱相似系數(shù)

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

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

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

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

在網(wǎng)絡(luò)拓?fù)渲械暮x為:Z設(shè)定為節(jié)點集合V;t為V中的某一節(jié)點;Γ(Z)為節(jié)點集合的共同鄰居;kt為節(jié)點t的度。在如圖2所示的簡單網(wǎng)絡(luò)中，A節(jié)點的鄰居是Γ(A)={B，C，D}，E節(jié)點的鄰居是Γ(E)={B，C}，節(jié)點A和E的共同鄰居是Γ(A)∩Γ(B)={B，C}，根據(jù)相似系數(shù)的定義，節(jié)點A對節(jié)點E的相似系數(shù)則為2/3，而節(jié)點E對節(jié)點A的相似系數(shù)為1，即兩者之間的相似系數(shù)是不同的，反映了兩個節(jié)點間的相似程度是不同的。

一般認(rèn)為，無向無環(huán)圖中的相似性是對稱的。然而，從前面的分析來看，這種相似一般情況下相似程度是不同的，即相似中包含非對稱信息，只有當(dāng)這兩個節(jié)點的度相等時，相似程度才相等，即相似對稱性只是一個特例?？紤]到相似的非對稱信息，本文對一般的相似性度量方法進(jìn)行修正，以更符合實際情況，因此相似性的修正定義如下:

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

圖2 簡單網(wǎng)絡(luò)Fig.2 Simple network

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

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

3.1 CN 指標(biāo)修正

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

3.2 AA 指標(biāo)修正

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

3.3 RA 指標(biāo)修正

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

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

在傳統(tǒng)的對稱相似性度量中，變量或?qū)ο笾g的相似是對稱的，只有一個相似值;而考慮變量或?qū)ο笾g的非對稱信息后，相似是非對稱的，在這種情況下，變量或?qū)ο笾g的相似度量應(yīng)考慮方向性，因此，考慮非對稱信息后的相似性是具有方向性的。

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

4 實驗結(jié)果與分析

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

4.1 評價指標(biāo)

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

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

4.2 實驗數(shù)據(jù)集

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

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

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

3)蛋白質(zhì)相互作用網(wǎng)絡(luò) Yeast(http://vlado.fmf.uni-lj.si/pub/networks/data/bio/Yeast/Yeast.htm):節(jié) 點 表 示 蛋 白質(zhì)，邊表示相互作用關(guān)系。該網(wǎng)絡(luò)包含2617個節(jié)點和11855條邊。

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

4.3 實驗結(jié)果

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

4.3.1 訓(xùn)練集比例不同

首先，測試考慮非對稱信息后基于節(jié)點相似性的鏈接預(yù)測方法在數(shù)據(jù)集USAir中當(dāng)訓(xùn)練集比例不同時AUC的表現(xiàn)，實驗結(jié)果如圖3所示。

圖3 USAir數(shù)據(jù)集中AUC與訓(xùn)練集比例關(guān)系Fig.3 Relationship of AUC and training set ratio in dataset USAir

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

4.3.2 訓(xùn)練集比例恒定

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

表1 基于相似系數(shù)的鏈接預(yù)測準(zhǔn)確度AUCTab.1 AUC in link prediction accuracy based on similarity coefficient

從表1可以看出，本文所提方法在不同數(shù)據(jù)集中的鏈接預(yù)測準(zhǔn)確度可以達(dá)到90%，在科學(xué)家合作網(wǎng)絡(luò)NS數(shù)據(jù)集已經(jīng)達(dá)到99%以上，說明本文所提方法在在多個數(shù)據(jù)集上均可以達(dá)到理想的預(yù)測效果，表明該方法可以適用于各種不同的數(shù)據(jù)集，滿足各類應(yīng)用要求。

4.3.3 與其他算法的比較

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

從表2的實驗結(jié)果可以看出，同一方法在不同數(shù)據(jù)集上的預(yù)測準(zhǔn)確度有所不同，在NS數(shù)據(jù)集上的預(yù)測準(zhǔn)確度最高，達(dá)到99%以上，而在USAir數(shù)據(jù)集上不同方法的預(yù)測準(zhǔn)確度變化最大。本文提出的基于相似系數(shù)的方法在同一數(shù)據(jù)集上總體上均優(yōu)于其他方法的預(yù)測準(zhǔn)確度。

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

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

5 結(jié)語

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