鄒 列,張月霞,b,c

(北京信息科技大學(xué) a.信息與通信工程學(xué)院；b.現(xiàn)代測控技術(shù)教育部重點實驗室；c.高動態(tài)導(dǎo)航北京市實驗室,北京 100101)

0 引 言

現(xiàn)實生活中，許多復(fù)雜系統(tǒng)都可以用節(jié)點和連線的方式表示成復(fù)雜網(wǎng)絡(luò)，通過科學(xué)的方式研究復(fù)雜網(wǎng)絡(luò)可以更好地認識和理解復(fù)雜系統(tǒng)的內(nèi)部結(jié)構(gòu)信息。鏈路預(yù)測是研究復(fù)雜網(wǎng)絡(luò)的方式之一，是指通過已知的各種信息(網(wǎng)絡(luò)拓撲結(jié)構(gòu)、節(jié)點屬性等)預(yù)測網(wǎng)絡(luò)中尚不存在連邊的兩個節(jié)點之間產(chǎn)生連接的可能性。這種預(yù)測既包含了對未知鏈接的預(yù)測，也包含對未來鏈接的預(yù)測[1]。目前，鏈路預(yù)測在網(wǎng)絡(luò)演化規(guī)律的研究中被廣泛應(yīng)用，具有巨大的實際應(yīng)用價值。如：在微博和博客的社交網(wǎng)絡(luò)[2-3]中，根據(jù)用戶在社交平臺上的社交關(guān)系信息，預(yù)測兩個陌生好友進行交互的可能；在商品購買系統(tǒng)以及新聞、音樂、直播類娛樂系統(tǒng)中，通過用戶的個人需求和動作行為，預(yù)測用戶所需的信息，從而推薦相應(yīng)的商品和相關(guān)喜好內(nèi)容[4-5]。因此，對復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測問題的研究有著現(xiàn)實意義。

鏈路預(yù)測方法主要分為基于機器學(xué)習(xí)的方法[6]、基于最大似然概率的方法[7]和基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的方法[8]?；跈C器學(xué)習(xí)、最大似然概率的方法雖然能得到較高的精確度，但是其復(fù)雜度很高，應(yīng)用范圍受到了限制?；诰W(wǎng)絡(luò)拓撲結(jié)構(gòu)的方法利用拓撲結(jié)構(gòu)使得鏈路預(yù)測更容易實現(xiàn)，備受多數(shù)研究人員的關(guān)注?，F(xiàn)有的基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的相似性預(yù)測算法分為局部、全局和準局部相似性算法[9]。文獻[10-15]基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的相似性算法更多的是關(guān)注共同鄰居節(jié)點數(shù)目、節(jié)點的度、共同鄰居節(jié)點的度以及節(jié)點間傳輸路徑能力，而忽略了鄰居節(jié)點的度的影響，不能夠相對全面地獲取網(wǎng)絡(luò)的拓撲信息，以至于鏈路預(yù)測的精度不夠高。

針對基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的相似性算法的問題，本文提出了一種基于復(fù)雜網(wǎng)絡(luò)的Psor鏈路預(yù)測算法，并通過5個真實網(wǎng)絡(luò)數(shù)據(jù)驗證了所提算法的有效性。

1 Psor算法原理

1.1 網(wǎng)絡(luò)描述

假設(shè)網(wǎng)絡(luò)是簡單無向無權(quán)網(wǎng)路G(V,E)，其中V是網(wǎng)絡(luò)中節(jié)點的集合，E是網(wǎng)路中邊的集合。網(wǎng)絡(luò)中有N個節(jié)點，M條邊，即|V|=N，|E|=M。網(wǎng)絡(luò)中任意兩個節(jié)點可能產(chǎn)生邊的情況有N×(N-1)/2種。令U為節(jié)點對組成邊的全集，那么節(jié)點對沒有連接邊的集合為U-E。假設(shè)集合U-E中有丟失的連接或者將來會出現(xiàn)的連接，鏈路預(yù)測就是找出這些連接。

無向無權(quán)網(wǎng)絡(luò)G(V,E)可以用鄰接矩陣A表示。如果節(jié)點i和節(jié)點j之間有邊連接，則aij=1；否則aij=0。通過鄰接矩陣可以計算網(wǎng)絡(luò)每個節(jié)點的度，節(jié)點i的度可以表示成

(1)

根據(jù)特定的相似性鏈路預(yù)測算法，為網(wǎng)絡(luò)中兩個節(jié)點之間沒有連邊的節(jié)點對(x,y)賦予一個分數(shù)Sxy，以估計它們未來連接的可能性。將所有未觀察到的連接均根據(jù)其得分進行排名，分數(shù)值越大，這兩個節(jié)點連接的可能性就越大。

1.2 Psor算法

2010年印度學(xué)者Prathap提出的一種新型綜合性學(xué)術(shù)評價指標，稱為P指數(shù)[16]，其計算公式為

p=(C2/N)1/3。

(2)

式中：C為學(xué)者發(fā)表的文章被引頻的總次數(shù)，N為學(xué)者發(fā)表的文章數(shù)。由此可以看出，P指數(shù)在學(xué)術(shù)評價中體現(xiàn)了數(shù)量(發(fā)文量)與質(zhì)量(被引頻的次數(shù))的平衡，使得評價一個學(xué)者的科研水平更有效。

以此類推，將P指數(shù)的概念擴展到復(fù)雜網(wǎng)絡(luò)中。在復(fù)雜網(wǎng)絡(luò)中，一個節(jié)點的鄰居相當于學(xué)者的發(fā)文數(shù)，其節(jié)點鄰居的鄰居相當于學(xué)者發(fā)表的文章被引用的次數(shù)。本文綜合節(jié)點自身的度和鄰居節(jié)點的度定義了節(jié)點的Psor指數(shù)，其計算公式為

Psorx=((∑ki)2/kx)1/3。

(3)

式中：i為節(jié)點x的鄰居，kx和ki分別表示節(jié)點x和節(jié)點i的度。由此可以看出，式(3)中節(jié)點的Psor指數(shù)大小由節(jié)點的度和其鄰居節(jié)點的度共同決定。當節(jié)點的度一定時，其鄰居節(jié)點的度越大，節(jié)點的Psor指數(shù)越大，即該節(jié)點的影響力就越大。與現(xiàn)有的鏈路預(yù)測指標僅將節(jié)點度視為節(jié)點的影響資源相比，節(jié)點的Psor指數(shù)可以更廣泛地量化節(jié)點的影響。

下面舉例說明節(jié)點的Psor指數(shù)對鏈路預(yù)測的精度的影響。如圖1所示，(a)和(b)是兩個復(fù)雜網(wǎng)絡(luò)，被預(yù)測節(jié)點為x和y，節(jié)點x和節(jié)點y的度都為4，它們的共同鄰居都是節(jié)點A和節(jié)點G。

圖1 兩個復(fù)雜網(wǎng)絡(luò)

根據(jù)基于節(jié)點的度和共同鄰居數(shù)量的Salton、Sorensen、HDI、LHN和PA等局部相似性算法對節(jié)點對(x,y)的相似性進行計算。圖1中節(jié)點對(x,y)的相似性分數(shù)是相同的，使用Salton算法計算節(jié)點對(x,y)的相似性分數(shù)都為0.5。這些算法無法預(yù)測圖1中的節(jié)點x和節(jié)點y之間誰最有可能連接。

然而，根據(jù)公式(3)，可以得到圖1(a)中被預(yù)測節(jié)點x和y的Psor指數(shù)為Psorx=Psory=2.08，圖1(b)中節(jié)點x和y的Psor指數(shù)為Psorx=Psory=2.52。因此，圖1(b)中被預(yù)測節(jié)點x和y的Psor指數(shù)要比圖1(a)中被預(yù)測節(jié)點x和y的Psor指數(shù)大。可以看出，圖1(b)中節(jié)點對(x,y)相比圖1(a)節(jié)點對(x,y)更有可能連接。

綜合考慮復(fù)雜網(wǎng)絡(luò)的局部結(jié)構(gòu)信息，本文提出了一種預(yù)測網(wǎng)絡(luò)相似性的Psor相似性指標，其定義如下：

(4)

下面通過圖1所示的兩個復(fù)雜網(wǎng)絡(luò)來驗證Psor算法的可行性。根據(jù)公式(4)，分別計算圖1(a)和圖1(b)中節(jié)點x和節(jié)點y之間的相似性分數(shù)。

因此，按照本文提出的算法，圖1(b)節(jié)點對(x,y)之間的相似性分數(shù)高于圖1(a)節(jié)點對(x,y)之間的相似性分數(shù)，所以圖1(b)中節(jié)點x和節(jié)點y更有可能連接，與事實吻合，說明本文提出的算法是可行的。

1.3 評價方法

(5)

顯然，當所有相似性分數(shù)都是隨機獨立生成時，那么AUC值應(yīng)為0.5。AUC值超過0.5的部分說明了鏈路預(yù)測算法在多數(shù)水平程度上比隨機選擇準確，也表明AUC的值越大，鏈路預(yù)測算法的預(yù)測效果越好。

1.4 Psor算法流程

Psor算法流程如圖2所示。

圖2 Psor算法流程圖

具體描述如下：

輸入：無權(quán)無向預(yù)測網(wǎng)絡(luò)邊的列表linklist。

輸出：相似性矩陣SIM，評價指標AUC的值。

開始：

(1)通過將導(dǎo)入的邊轉(zhuǎn)換成稀疏矩陣，然后刪除自環(huán)，使得矩陣對角元為0，然后將矩陣轉(zhuǎn)化成三角陣，最后再將三角陣通過轉(zhuǎn)置轉(zhuǎn)化成對稱矩陣，轉(zhuǎn)換結(jié)束后得到網(wǎng)絡(luò)的鄰接矩陣；

(2)然后確定測試集邊的數(shù)目，將網(wǎng)絡(luò)(鄰接矩陣)中所有的邊找出來，為每條邊設(shè)置標志位，判斷是否能刪除，若選擇的邊可刪除，則將之放入測試集中，依次將測試集中的邊選取完畢，最終返回訓(xùn)練集和測試集；

(3)由鄰接矩陣，獲取預(yù)測節(jié)點的度、共同鄰居數(shù)量以及其鄰居節(jié)點的度，然后根據(jù)公式(3)計算預(yù)測節(jié)點的Psor指數(shù)；

(4)根據(jù)Psor相似性指標公式，求得最終的相似性矩陣SIM；

(5)根據(jù)相似性矩陣，取出測試集和不存在邊集合的相似性度值進行比較，最終使用AUC計算公式(5)得到Psor算法的AUC值。

結(jié)束

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

本文運用Matlab工具實現(xiàn)對鏈路預(yù)測算法的仿真，選取常用的評價指標AUC作為預(yù)測效果。實驗時，獨立重復(fù)實驗100次，計算100次AUC的平均值作為實驗的最終結(jié)果。

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

為了驗證所提算法的有效性，本文通過選取不同領(lǐng)域的網(wǎng)絡(luò)作為測試數(shù)據(jù)集，所涉及的實驗數(shù)據(jù)都來源于真實網(wǎng)絡(luò)，真實網(wǎng)絡(luò)的實驗數(shù)據(jù)可以從www.linkprediction.org網(wǎng)站下載。下載的數(shù)據(jù)集首先要經(jīng)過預(yù)處理，將有向鏈接更改為無向鏈接，并刪除自循環(huán)和多鏈接來確保網(wǎng)絡(luò)的不加權(quán)和無向。本文采用的5個典型的真實網(wǎng)絡(luò)數(shù)據(jù)如下:

(1)金融市場網(wǎng)絡(luò)(FINC)，節(jié)點表示金融中心名稱，邊表示各金融中心的交易，該網(wǎng)絡(luò)共有89個節(jié)點和150條邊；

(2)美國航空交通網(wǎng)絡(luò)(USAir)，網(wǎng)絡(luò)中的節(jié)點表示不同的機場，邊表示機場之間有直飛航線，該網(wǎng)絡(luò)共有332個節(jié)點和2 126條邊;

(3)蛋白質(zhì)相互作用網(wǎng)絡(luò)(Yeast)，節(jié)點代表蛋白質(zhì)，邊代表兩種蛋白質(zhì)之間的代謝相互作用，該網(wǎng)絡(luò)共有2 735個節(jié)點和11 693條邊；

(4)政治家博客網(wǎng)絡(luò)(Political Blogs，PB)，節(jié)點代表不同政治家的博客，邊代表兩個博客之間的超鏈接，該網(wǎng)絡(luò)共有1 222個節(jié)點和16 714條邊；

(5)線蟲代謝網(wǎng)絡(luò)(Metabolite)，節(jié)點是代謝物(例如蛋白質(zhì))，邊緣是它們之間的相互作用，該網(wǎng)絡(luò)有453個節(jié)點和2 040條邊。

通過使用Gephi軟件可將以上5種網(wǎng)絡(luò)的數(shù)據(jù)集做簡單分析，可以得到網(wǎng)絡(luò)的平均度、網(wǎng)絡(luò)的平均聚類系數(shù)、網(wǎng)絡(luò)的平均路徑長度、網(wǎng)絡(luò)直徑D、網(wǎng)絡(luò)密度d(G)等網(wǎng)絡(luò)基本拓撲特征，如表1所示。

表1 數(shù)據(jù)集的網(wǎng)絡(luò)特征

2.2 經(jīng)典的相似性鏈路預(yù)測算法

為了說明本文所提算法的可行性，將選取幾種經(jīng)典的相似性鏈路預(yù)測算法作為基準算法。下面對幾種經(jīng)典的相似性鏈路預(yù)測算法進行介紹。

(1)Salton指標[18]?？紤]了共同鄰居和節(jié)點自身的度的影響，其定義為

(6)

(2)Sorensen指標[19]?？紤]了共同鄰居和節(jié)點自身的度的影響，認為節(jié)點間的相似性與這兩個節(jié)點的度之和成反比，其定義為

(7)

(3)HDI指標[13]?？紤]了共同鄰居和節(jié)點自身的度的影響，其定義為

(8)

(4)LHN指標[20]?？紤]了共同鄰居和節(jié)點自身的度的影響,認為節(jié)點間相似性與這兩個節(jié)點的度的乘積成反比，其定義為

(9)

(5)PA指標[21]。只考慮了節(jié)點自身的度，認為兩節(jié)點的度的乘積越大，這兩個節(jié)點越有可能連接，其定義為

(10)

(6)LHN-II指標[20]。它考慮的是所有的路徑數(shù)，其表達式如下：

(11)

式中：δxy為Kroneckerδ函數(shù)，φ為取值小于1的參數(shù)，A為鄰接矩陣，λ1為矩陣A的最大特征值，M為網(wǎng)絡(luò)中邊的總數(shù)。

(7)平均通勤時間(Average Commute Time，ACT)[22]。表示兩節(jié)點之間平均需要走的步數(shù)，節(jié)點和節(jié)點的平均通勤時間為

n(x,y)=m(x,y)+m(y,x)。

通過求網(wǎng)絡(luò)拉普拉斯矩陣L的偽逆L+獲得其數(shù)值解，即

(12)

(8)基于轉(zhuǎn)移偏好自洽相似性指標(Transferring Similarity Based on Preferential Attachment，TSPA)[23]。通過中間節(jié)點的傳遞特性，針對性克服了結(jié)構(gòu)信息利用不充分的缺點，其定義為

(13)

2.3 與其他典型相似性算法對比

實驗時，將網(wǎng)絡(luò)數(shù)據(jù)集隨機劃分成一定比例的訓(xùn)練集和測試集。第一次實驗將數(shù)據(jù)集劃分為90%的訓(xùn)練集和10%的測試集，第二次實驗將數(shù)據(jù)集劃分為80%的訓(xùn)練集和20%的測試集，實驗結(jié)果圖3所示。

(a)測試集的比例為10%

(b)測試集的比例為20%圖3 不同測試集比例下不同網(wǎng)絡(luò)中各相似性算法的AUC值

通過圖3可以看出，在FINC、USAir、PB和Metabolite這四種網(wǎng)絡(luò)中，Psor算法的AUC值明顯高于其他8種鏈路預(yù)測算法的AUC值，也就是說所提的Psor算法在預(yù)測精度上可以獲得更好的預(yù)測效果。在Yeast網(wǎng)絡(luò)中，LHN-II算法能夠獲得最優(yōu)的AUC值，而Psor算法的AUC值僅次于LHN-II算法，其他算法的AUC值都低于Psor算法的AUC值。此外還可以看出，在USAir、PB和Metabolite這三種網(wǎng)絡(luò)中，LHN-II算法的預(yù)測精度最低，尤其在Metabolite網(wǎng)絡(luò)中LHN-II算法的AUC低于0.5，這說明LHN-II算法不適合預(yù)測這個網(wǎng)絡(luò)。因此，總體來看，Psor算法考慮鄰居節(jié)點度的影響在網(wǎng)絡(luò)中獲取到的網(wǎng)絡(luò)結(jié)構(gòu)信息相對全面，鏈路預(yù)測性能與其他8種算法相比較優(yōu)，預(yù)測精度得到了一定的提高。

表2是數(shù)據(jù)集分為90%的訓(xùn)練集和10%的測試集時，各相似性算法在不同網(wǎng)絡(luò)中仿真出來的AUC結(jié)果。可以看出，在FINC、USAir、PB和Metabolite這四種網(wǎng)絡(luò)中，相比其他8種算法，Psor算法的AUC值是最高的。在FINC網(wǎng)絡(luò)中，Psor算法的AUC值相比其他8種算法至少提高了0.1%；在USAir網(wǎng)絡(luò)中，Psor算法的AUC值相比其他8種算法至少提高了1.96%；在PB網(wǎng)絡(luò)中，Psor算法的AUC值相比其他8種算法至少提高了0.47%；在Metabolite網(wǎng)絡(luò)中，Psor算法的AUC值相比其他8種算法至少提高了2.09%。這說明Psor算法通過考慮節(jié)點自身的影響力和鄰居節(jié)點的鏈接對預(yù)測的貢獻，克服了傳統(tǒng)算法只考慮共同鄰居節(jié)點數(shù)目、節(jié)點自身的度以及節(jié)點間路徑傳輸能力而未能完全挖掘路徑信息的缺陷，有效提高了預(yù)測的精度。

表2 訓(xùn)練集90%和測試集為10%時5個真實網(wǎng)絡(luò)在不同算法下的AUC值

為綜合衡量算法性能，將訓(xùn)練集的比例由90%改為80%，重新進行上述實驗流程，得到各預(yù)測算法的AUC值如表3所示。類似地，可以看出在FINC、USAir、PB和Metabolite這四種網(wǎng)絡(luò)中，相比其他8種算法，Psor算法的AUC值是最高的。以USAir網(wǎng)絡(luò)為例，Psor算法較局部相似性Salton、Sorensen、HDI、LHN、PA算法分別提高了2.47%、3.08%、3.54%、16%和2.65%，較全局相似性LHN-II、ACT、TSPA算法分別提高了32.73%、4.43%和5.55%，說明鄰居節(jié)點的度對節(jié)點對之間的相似性有一定的影響。Psor算法在預(yù)測時獲得了更加全面的網(wǎng)絡(luò)結(jié)構(gòu)信息，從而有效提高了預(yù)測精度。

表3 訓(xùn)練集80%和測試集為20%時5個真實網(wǎng)絡(luò)在不同算法下的AUC值

此外，在設(shè)計鏈路預(yù)測算法時，算法的效率也是必須考慮的。本文對比的算法中PA算法的時間復(fù)雜度為O(N2)；Salton、Sorensen、HDI、LHN算法都是基于共同鄰居進行鏈路預(yù)測的，其時間復(fù)雜度為O(N3)；LHN-II指標、ACT指標和TSPA指標的時間復(fù)雜度為O(N3)。本文提出的Psor算法也是在共同鄰居的基礎(chǔ)上考慮度信息進行鏈路預(yù)測的，其時間復(fù)雜度為O(N3)。因此，可以看出Psor算法的時間復(fù)雜度相對沒有增加。

綜上所述，與Salton、Sorensen、HDI、LHN、PA、LHN-II、ACT和TSPA這8種經(jīng)典鏈路預(yù)測算法相比較，本文所提的Psor算法在復(fù)雜度沒有增加的情況下具有更好的預(yù)測效果。

3 結(jié)束語

本文在分析現(xiàn)有的鏈路預(yù)測算法特性的基礎(chǔ)上提出了一種基于復(fù)雜網(wǎng)絡(luò)的Psor鏈路預(yù)測算法。該算法充分考慮了復(fù)雜網(wǎng)絡(luò)的局部結(jié)構(gòu)信息，利用節(jié)點對的共同鄰居、節(jié)點的度和節(jié)點的Psor指數(shù)等信息來對網(wǎng)絡(luò)鏈路進行預(yù)測。通過在5個真實數(shù)據(jù)集中比較Psor算法與其他8種經(jīng)典鏈路預(yù)測算法的AUC值來說明提出的算法對鏈接預(yù)測的效果。實驗結(jié)果表明，Psor算法在預(yù)測效果上明顯優(yōu)于其他8種經(jīng)典的鏈路預(yù)測相似性指標，可以提高鏈路預(yù)測的精確度，適用于一些網(wǎng)絡(luò)中的節(jié)點連接預(yù)測。接下來的工作將會考慮有權(quán)、有向網(wǎng)絡(luò)，將Psor算法應(yīng)用到這種網(wǎng)絡(luò)中。