黃壽孟

（1.三亞學(xué)院 信息與智能工程學(xué)院，海南 三亞 572022；2.三亞學(xué)院 陳國良院士團(tuán)隊創(chuàng)新中心，海南 三亞 572022）

許多現(xiàn)實世界的復(fù)雜系統(tǒng)可以通過復(fù)雜網(wǎng)絡(luò)來表示，其節(jié)點表示實體，鏈路表示節(jié)點之間的交互[1]。因此復(fù)雜網(wǎng)絡(luò)被人們廣泛研究與應(yīng)用，其中研究復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測是學(xué)者們熱點問題之一，它的研究目標(biāo)是估計兩個尚未連接的節(jié)點之間存在鏈路的可能性[2]。目前，許多鏈路預(yù)測算法關(guān)注的都是基于節(jié)點相似性的思想[3]，利用節(jié)點的基本屬性定義節(jié)點相似性，也就是說如果兩個節(jié)點具有許多共同的拓?fù)涮卣鳎敲此鼈兙捅徽J(rèn)為是相似的[4]。比如共同鄰居算法[5]、Adamic Adar[6]、Jaccard系數(shù)[7]等局部相似度量算法可以非常有效地計算，并在許多情況下都有良好的性能；還有全局度量算法[8-9]、基于本地路徑信息算法[10]都有良好Katz指數(shù)、通勤時間、節(jié)點信息的預(yù)測性能。文獻(xiàn)[11]針對加權(quán)網(wǎng)絡(luò)綜合考慮網(wǎng)絡(luò)中邊的聚類和擴(kuò)散特性提出基于鏈接拓?fù)錂?quán)重的含權(quán)預(yù)測指標(biāo)的預(yù)測方法。文獻(xiàn)[12]提出一種基于社團(tuán)節(jié)點相關(guān)性的鏈路預(yù)測算法，把節(jié)點對擴(kuò)展到二階局部社團(tuán)獲取更多的網(wǎng)絡(luò)結(jié)構(gòu)信息。文獻(xiàn)[13]根據(jù)復(fù)雜網(wǎng)絡(luò)樣本鄰接矩陣化處理以及采用AdaBoost 算法進(jìn)行分類訓(xùn)練獲取權(quán)重投票預(yù)測結(jié)果。文獻(xiàn)[14]設(shè)計開發(fā)了結(jié)合網(wǎng)絡(luò)拓?fù)涮卣?、基本特征和附加特征的TNTlink模型，并結(jié)合物理學(xué)和計算機(jī)科學(xué)的領(lǐng)域知識，利用深度神經(jīng)網(wǎng)絡(luò)將這些特征集成到一個深度學(xué)習(xí)框架中從而解決鏈路預(yù)測問題。為了優(yōu)化現(xiàn)有的基于路徑預(yù)測方法，本文提出了兩個節(jié)點u和v之間的新相似性索引，該索引是根據(jù)距離u和v固定距離內(nèi)的節(jié)點的局部信息計算得出的。換句話說，索引信息不僅包含了直接連接到u與v的節(jié)點，還合并了位于u到v的所有可能長度較小的路徑上的節(jié)點信息，最后比較兩個使用最廣泛的相似性指標(biāo)，Adamic Adar和Katz Index的性能。

1 相關(guān)工作

網(wǎng)絡(luò)G=(V,E)由節(jié)點的有限非空集合V和無序頂點對（稱為鏈接）的有限集合E組成。網(wǎng)絡(luò)可以是有向的（在每個邊緣都分配有方向的地方），也可以是無向的（沒有為邊緣分配任何方向的地方）。本文只考慮無向簡單網(wǎng)絡(luò)，其中不允許多個鏈接和自環(huán)。頂點的度數(shù)v∈V是與v相連的鄰居數(shù)。網(wǎng)絡(luò)G=(V,E)中的行走w是一系列交替的頂點和邊v0,e1,v1,e2,v2,…,ek,vk。其中vi∈V和ei=(vi-1,vi)。該行走具有長度k，其定義為行走中的頂點數(shù)。無向簡單網(wǎng)絡(luò)G=(V,E)的鄰接矩陣類型是|V| × |V|。如果u和v有鏈接，則鄰接矩陣（u，v）值為1，否則為0。鄰接矩陣(A k)uv的第k次冪表示行走的次數(shù)，即從u到v的鏈接路徑的長度為k。目前常用的本地和準(zhǔn)本地/全局鏈接預(yù)測方法有：

1.1 公共鄰居(CN）

如果兩個節(jié)點存在許多公共鄰居，則它們最有可能具有鏈接，用這種方法計算兩個節(jié)點的公共鄰居數(shù)[5]，其計算公式為

CN算法在許多情況下是評估其他方法性能的基準(zhǔn)，CN也可以表示為CN(u,v) =(A2)uv，其中A是網(wǎng)絡(luò)的鄰接矩陣。

1.2 Adamic Adar（AA）

該算法目標(biāo)是在通過為較少聯(lián)系的鄰居分配更多權(quán)重來提高普通鄰居的準(zhǔn)確性[6]，計算公式為

其中w是u和v的共同鄰居。在社交網(wǎng)絡(luò)中，此算法可以計算不受歡迎的人（朋友數(shù)量較少的人）可能更容易將一對特定的朋友彼此介紹。

1.3 Jaccard（JC）

Jaccard算法是從兩個節(jié)點的公共鄰居計算出的另一種相似性度量[7]，它定義為

JC的值可以解釋為節(jié)點u和v的公共鄰居的概率。

1.4 Katz

該算法基于整個網(wǎng)絡(luò)的拓?fù)淇紤]節(jié)點對之間所有路徑的集合[10]。路徑的長度會以指數(shù)方式衰減，從而為較短的路徑賦予更大的權(quán)重，它計算公式為

其中0 <β< 1是控制不同長度路徑的權(quán)重的參數(shù)。β的值非常小將導(dǎo)致懲罰較長長度的路徑，并且在這種情況下將度量減小為CN。注意，相似度矩陣S也可以計算為(I-βA)-1-I，其中，I表示大小為|V|×|V|的單位矩陣。

1.5 局部路徑（LP）

為了在準(zhǔn)確性和復(fù)雜性之間取得良好的平衡，考慮較短長度的局部路徑的LP算法[15]，計算公式為

其中A是網(wǎng)絡(luò)的鄰接矩陣。與Katz 算法一樣，β設(shè)置為較小的值，以便較短的路徑獲得更大的權(quán)重。請注意，如果β= 0，則該算法會退化為公共鄰居。實際上，由于其計算較復(fù)雜，該度量通常在L = 3時使用，從而將其減小為LP(u,v) =A2+βA3。

1.6 優(yōu)先聯(lián)系PA

該算法表示在社交網(wǎng)絡(luò)中有很多朋友的用戶將來傾向于獲得更多的聯(lián)系[16-19]，其計算公式為

2 預(yù)測模型

2.1 設(shè)計背景

基于相似度的鏈接預(yù)測方法通常取決于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，這種方法的目的是基于節(jié)點的本地連接結(jié)構(gòu)預(yù)測一對節(jié)點之間的丟失鏈接。本地鏈路預(yù)測方法使用兩個節(jié)點的直接鄰居的節(jié)點信息來預(yù)測它們之間的鏈接。例如，AA算法將較高的權(quán)重分配給程度較小的公共鄰居。直覺是，度數(shù)較小的公共鄰居在預(yù)測兩個節(jié)點之間的鏈接時更為重要。雖然局部相似性算法僅考慮直接連接到查詢節(jié)點的那些節(jié)點，但是全局方法（例如Katz算法和LP算法）考慮整個網(wǎng)絡(luò)的拓?fù)洹５侨址椒ú豢紤]連接節(jié)點的程度。因此需要一種可以同時利用局部和全局相似性指標(biāo)來測量相似性的鏈路預(yù)測方法。

2.2 PSI預(yù)測方法

若未加權(quán)網(wǎng)絡(luò)G=(V,E)存在(u,v) ∈E'，如何預(yù)測兩個節(jié)點u和v之間的鏈接。為了估計節(jié)點u和v之間潛在連接的可能性，考慮到網(wǎng)絡(luò)中所有與節(jié)點u和v處于固定距離內(nèi)的節(jié)點，筆者提出一種相似性指數(shù)（簡稱為PSI）計算方法。

定義1 若Γk(u)代表與節(jié)點u的最短距離為k的所有節(jié)點的集合，即節(jié)點u和v之間的相似性指數(shù)PSI(u,v)定義為

其中β是權(quán)重系數(shù)，若距離大于1的節(jié)點的權(quán)重較小，則L是在計算PSI(u,v)時考慮的最長路徑的長度。此方法結(jié)合了Adamic Adar 和LP 算法的優(yōu)點，考慮水平范圍比AA 寬的本地路徑（AA 僅考慮兩個節(jié)點的直接鄰居），同時也考慮了每個節(jié)點的程度（LP算法僅計算本地路徑，而忽略程度）。

由于網(wǎng)絡(luò)中一對可達(dá)節(jié)點之間的最短距離始終是唯一的，因此建議在相似性指數(shù)PSI計算中每個節(jié)點僅被考慮一次，從而得出PSI的等效定義。

定義2 兩個節(jié)點u和v之間的相似性指數(shù)PSI(u,v)定義為

其中δ(u,v)表示節(jié)點u和v之間的最短距離。

2.3 PSI算法

對于L= 2，PSI簡化為AA，LP指數(shù)簡化為CN。因此假設(shè)L> 2，PSI(u,v)的值計算如下:

若節(jié)點u和v未連接，首先確定節(jié)點u和v的公共鄰居，并通過取其度的對數(shù)的倒數(shù)來計算其分?jǐn)?shù)。該分?jǐn)?shù)被添加到相似性指數(shù)PSI(u,v)。接著計算連接到兩個節(jié)點u和v中的一個但距另一個節(jié)點的最短路徑恰好是兩個的節(jié)點。它們的分?jǐn)?shù)是以類似的方式計算的，即取其度的對數(shù)的倒數(shù)。但是它們在預(yù)測得分的計算中分配的權(quán)重較小。這是通過將他們的分?jǐn)?shù)乘以β(0 <β< 1)來完成的，然后將其值添加到PSI(u,v)。該過程一直持續(xù)到計算出與節(jié)點u和v的距離小于或等于L的所有節(jié)點的分?jǐn)?shù)。

注意這時L的最大值可以是2d，其中d是網(wǎng)絡(luò)的直徑，其定義為網(wǎng)絡(luò)中所有節(jié)點對之間最短路徑中的路徑最大長度。

下面是計算相似性指數(shù)PSI的算法過程，其中GT表示用于訓(xùn)練學(xué)習(xí)的網(wǎng)絡(luò)集合，ET表示用于訓(xùn)練學(xué)習(xí)的鄰接節(jié)點對集合：

1：輸入：網(wǎng)絡(luò)GT=(V,ET)，具有鄰接矩陣A，距離長度L值和權(quán)重參數(shù)β。

影響消費者購買葉類蔬菜行為關(guān)鍵因素分析………………………………………………………… 張 標(biāo)，徐 娜，張領(lǐng)先（128）

2：輸出：相似度得分矩陣S。

3：s←0

（將相似矩陣初始化為0）

4：δ←All Pair Shortest Paths(GT)

（計算最短路徑）

5：for (u,v) ∈EETdo

6：forw∈V{u,v}do

8：ifd≤1 then

9：PSI(u,v) ←PSI(u,v) +βd-2(log|w|)-1（更新相似性得分）

10：end if

11：end for

12：end for

在PSI算法中，接受網(wǎng)絡(luò)GT的鄰接矩陣作為輸入，該矩陣是通過去除EP中的鏈接而獲得的。它還接受權(quán)重參數(shù)β和L（L的最大值為最大路徑的長度）。首先計算網(wǎng)絡(luò)中所有節(jié)點對之間的最短路徑，for循環(huán)（第5至12行）遍歷所有未連接的節(jié)點對，將來可能會鏈接起來。通過考慮網(wǎng)絡(luò)中所有節(jié)點的相似性得分，這些節(jié)點從兩個節(jié)點到最短路徑的總和小于L，而相似性得分根據(jù)等式在第11行中更新。

3 實驗結(jié)果

3.1 數(shù)據(jù)集

3.2 評估指標(biāo)

為了估計預(yù)測算法的準(zhǔn)確性，本文使用標(biāo)準(zhǔn)度量AUC精度指標(biāo)[1]。如果在n個獨立預(yù)測比較中，n'是缺失鏈接具有較高分?jǐn)?shù)的次數(shù)，n''是缺失鏈接和不存在具有相同分?jǐn)?shù)的鏈接的次數(shù)，則將精度AUC = (n' +0.5n'')/n如果所有鏈接分?jǐn)?shù)均根據(jù)獨立的概率相同分布隨機(jī)生成，則預(yù)測算法的AUC精度指標(biāo)應(yīng)約為0.5。因此，若AUC > 0.5，即表示該算法的預(yù)測性能效果好，且AUC值越接近1表示預(yù)測效果越好。

3.3 結(jié)果

本文將數(shù)據(jù)集網(wǎng)絡(luò)的鏈路集合E隨機(jī)分為兩組，即訓(xùn)練集ET和測試集EP。訓(xùn)練集包含90%的鏈接，而其余10%的鏈接用于測試目的，使用相同的集合ET和EP來評估各種預(yù)測方法的性能。同時在PSI，Katz 和LP算法中參數(shù)值β= 0.005，L= 3，每個數(shù)據(jù)集進(jìn)行100次實驗，從而得到每個算法平均精度AUC值見表2。

表1 數(shù)據(jù)集網(wǎng)絡(luò)的拓?fù)涮匦訲able 1 Topological characteristics of the data set network

表2 各算法在不同數(shù)據(jù)集下的預(yù)測精度AUCTable 2 AUC for each algorithm under different data sets

從表2中明顯得出，PSI算法在不同的數(shù)據(jù)集中的預(yù)測精度AUC 值均高于其他算法在同一數(shù)據(jù)集上所得到的AUC值，預(yù)測效果較好，其通過合并有關(guān)可達(dá)節(jié)點的信息使預(yù)測算法的準(zhǔn)確性大大提高。

4 結(jié)論

鏈路預(yù)測是復(fù)雜網(wǎng)絡(luò)分析中最重要和最具挑戰(zhàn)性的領(lǐng)域之一。鏈路預(yù)測算法的目標(biāo)是基于網(wǎng)絡(luò)中的現(xiàn)有鏈路來估計丟失鏈路的可能性。本文設(shè)計了一種基于本地路徑索引的鏈接預(yù)測方法，結(jié)合有關(guān)路徑上的節(jié)點信息預(yù)測網(wǎng)絡(luò)中兩個節(jié)點之間存在鏈路的可能性。與基于本地路徑的頻率來預(yù)測丟失鏈接的本地路徑索引不同，本文提出的方法合并了有關(guān)路徑上的節(jié)點信息，最后利用真實數(shù)據(jù)集進(jìn)行實驗分析，證明該方法比原有的方法具有更高的準(zhǔn)確性。