信息熵改進主成分分析模型的鏈路預測算法

孟昱煜，郭靜

（蘭州交通大學電子與信息工程學院，蘭州 730070）

0 引言

復雜網絡鏈路預測［1］指通過已知的各種信息預測給定網絡中尚不存在連邊的兩個節點發生鏈接的可能性。它的應用包括在社交網絡中的朋友推薦［2］、預測蛋白質之間的相互作用［3］、推斷網絡演化機制［4］。目前大多數研究都是基于節點相似性算法：共同鄰居（Common Neighbor，CN）指標［5］關注兩個節點是否處于同一個環境；Katz 指標［6］考慮了網絡的全部路徑；全局指標中ACT（Average Commute Time）［6］表現突出；LHNII（Leicht-Holme-Newman）指數［6］的基本思想是基于一般等效；MFI（Matrix Forest Index）［6］在協作推薦系統中取得了良好的結果；SRW（Superposed Random Walk）指數［6］使得目標節點與附近節點之間的相似性更高；局部路徑（Local Path index，LP）指標［7］在共同鄰居基礎上，考慮了三階路徑的影響來計算節點間相似性。基于相似性算法在不同結構特征的網絡中，計算結果不穩定且無法獲得魯棒性［8］，而且單機制算法存在局限性，故篩選并組合若干個簡單指標，即算法的集成在鏈路預測中是有效的算法［7］。鑒于上述問題，結合復雜網絡的特點，基于不同的相似性算法，引入融合集成的思想，研究混合鏈路預測。

混合鏈路預測是指能使用多維信息或直接定義多維信息之間關系的一種算法研究［9］。吳翼騰等［9］對組合算法進行理論極限研究得出組合算法的準確性一定大于或等于各個單機制算法的鏈路預測準確性；He 等［10］基于有序加權平均（Ordered Weighted Averaging aggregation operator，OWA）算法設計了鏈路預測中經典局部指標的集成算法；Ma 等［11］利用邏輯回歸設計的融合算法；吳祖峰等［12］利用機器學習中的AdaBoost 算法融合指標；Li 等［13］提出了基于Logistic 回歸算法和XGBoost 算法的集成模型鏈路預測算法（Ensemble-Model-based Link Prediction algorithm，EMLP）。近年隨著深度學習的發展，研究者提出了網絡表示學習法和圖神經網絡［14］。

根據現有研究，融合結構相似性指標的算法可以提高鏈路預測的效果。受OWA 算法的啟示，本文提出了一種組合模 型 PEW（information fusion model based on Principal component analysis and Entropy Weight method）用于鏈接預測。PEW 模型的主要思想是使用隨機森林（Random Forest，RF）算法［15］確定了代表網絡的不同特征的7 種鏈路預測相似性指標作為最佳特征集合（CN、LP、LHNII、ACT、Katz、SRW和MFI），利用信息熵改進主成分分析（Principal Component Analysis，PCA）實現了指標的非線性計算，并獲得了指標融合的特征權重。在此基礎上，使用所獲得的特征權重校驗經典相似性指標并在6 個真實數據集上測試模型，通過與混合鏈路預測算法對比進一步驗證了PEW 模型校驗單機制算法的有效性、可靠性和魯棒性。

1 算法概述

考慮到不同類型指標之間的錯分樣本集可能不同，從而不同的指標可以給出互補的信息，因此本文利用隨機森林選擇能夠代表網絡的不同特征和不同思想求解的指標作為最佳特征集合，通過基于信息熵改進PCA 的特征信息融合模型（PEW）集成特征獲得權重來衡量不同結構對連邊的貢獻程度，利用該模型對現有的相似性指標進行校驗，從而對提升預測性能產生積極的影響。

1.1 基于信息熵改進PCA的特征信息融合模型

信息融合是一種多層次多方面的處理過程，通過對多源數據的檢測、組合、相關和估計來決策所需完成的任務。本文利用隨機森林確定指標重要性指數確定了最佳指標（CN、Katz、LP、LHNI、ACT、SRW 和MFI）。詳細定義見1.2 節。

1.1.1 隨機森林特征選擇

機器學習中，隨機森林（RF）［15］是一個包含多個決策樹的分類器，輸出的類別由個別樹輸出的類別的眾數而定，可以很好地評估各個特征在分類問題上的重要性，篩選后的特征指標體系更具有代表性。生成隨機森林的步驟如下：

1）從訓練數據集中，應用bootstrat 有放回地隨機抽取K個新的樣本集，并由此構建K棵分類回歸樹，每次未被抽到的樣本組成了K個袋外數據。

2）設有n個特征，則在每一棵樹的每個節點處隨機抽取mtry個特征(mtry≤n)，通過計算每個特征蘊含的信息量，在mtry個特征中選擇一個最具有分類能力的特征進行節點分裂。

3）每棵樹最大限度地生長，不做任何剪裁。

4）將生成的多棵樹組成隨機森林，用隨機森林對新的數據進行分類，分類結果按樹分類器的投票多少而定。

通過上述步驟可以對指標進行篩選并確定指標的重要性，以此提供最優的特征集合。

1.1.2 PCA特征融合

主成分分析（PCA）是考察多個變量間相關性一種多元統計法，可以在信息丟失最小的前提下，實現多元數據的特征融合，在提取出主要特征的同時去除了多源數據間的線性相關［16］。近年來，PCA 在信號處理、模式識別、數字圖像處理等領域得到了廣泛應用［17］。在鏈路預測問題中，由于節點之間存在一定的相關關系，計算所得的多維節點相關特征也相應地存在一定的關系，為此利用PCA 對節點間相似性特征進行融合。PCA 特征融合的計算過程如下：

步驟1 對原始數據矩陣進行標準化處理，使各指標之間具有可比性，計算公式為：

其中：X表示原始矩陣，X*表示標準化后的矩陣，Xmax=max(X)，Xmin=min(X)。

步驟2 計算協方差矩陣，對于集成相似性矩陣Xm*n，m表示特征個數，n表示樣本個數，即節點對。計算協方差矩陣C來反映多變量之間的關系，計算公式為：

步驟3 對協方差矩陣分解，計算得到協方差矩陣的特征值λ1，λ2，…，λm（對特征值按降序排列）和對應的單位化特征向量u1，u2，…，um。計算公式為：

步驟4 按照累計貢獻率選擇主成分，構造映射矩陣P，取前m個主成分，計算第i（i≤m）個主成分的貢獻率及累積貢獻率。取前k個特征向量進行組合形成映射矩陣P，P=[u1，u2，…，uk]。貢獻率的計算公式為：

步驟5 利用映射矩陣，重構主相似性特征矩陣，計算公式為：

1.1.3 信息熵改進PCA

在信息論中，用熵值可以判斷指標的變異程度，可以計算出各指標的貢獻率，得到主相似性特征權重［18-19］。信息熵是衡量隨機變量分布的混亂程度，是隨機分布各事件發生的信息量的期望值，被定義為H(X)=是隨機變量x的概率分布，隨機變量的取值個數越多，狀態數也就越多，信息熵就越大，混亂程度就越大。信息熵改進PCA 從熵的角度，以相似性特征攜帶的節點相似性信息量為度量，計算相似性貢獻率進行相似性特征融合，從而得到融合相似性特征權重。假設節點具有m個相似性特征a1，a2，…，am，各相似性 指標特征 提供信息 的概率為q(x1)，q(x2)，…，q(xm)，則該數據集的相似性特征的信息結構為：

步 驟1 計算特征 值，即Q=[q1，q2，…，qm]，計算公式為：

步驟2 利用特征值qi計算各相似性特征的信息熵Ei，計算公式為：

步驟3 計算相似性特征加權系數wi，構造加權矩陣W=diag[w1，w2，…，wm]，計算公式為：

步驟4 利用加權矩陣W得到融合相似性特征權重，計算公式為：

步驟5 對融合相似性特征權重矩陣歸一化處理得到Y_F'，即特征信息融合權重。

1.2 PEW模型校驗單機制算法

本文通過信息熵改進PCA 提取待融合指標的融合特征指數，也就是各結構對連邊的貢獻程度。對已有的指標，需要將其與信息融合特征權重結合，并對其進行校驗來提升預測精度，即信息融合特征權重與單機制索引作哈達瑪積，哈達瑪積是維數相同的矩陣對應元素的乘積。這7 個單機制索引是從不同的角度和不同思想提出的，只有融合這樣的索引指標才能獲得更為全面的網絡結構信息。CN 指標考慮兩個節點的共同鄰居的數量，計算復雜度低，但預測精度稍低；Katz 指標考慮了所有的路徑，計算復雜度高；LP 指標是在CN的基礎上考慮了三階路徑，復雜度低于全局指標；LHNII 是在重新定義的相似性的基礎上考慮了共同鄰居；ACT 是從全局隨機游走的角度考慮，計算復雜度高；SRW 考慮的是局部隨機游走，計算復雜度低于全局隨機游走指標；MFI 指標在協同推薦系統中有較好的效果。根據它們各自的優勢和不足，用信息熵改進PCA 融合用于鏈路預測。

1）PEW-CN指標。

CN 指標是基于局部信息的最簡單的相似性指標，對于網絡中的節點x，定義它的鄰居集合為Γ(x)，如果兩個節點x和y有許多共同的鄰居，則x和y更有可能具有鏈接［5］，即=|Γ(x) ∩Γ(y)|，用PEW 模型對其進行校驗，即基于共同鄰居指標的PEW 模型見式（11）：

2）PEW-Katz指標。

3）PEW-LP指標。

4）PEW-LHNII指標。

5）PEW-ACT指標。

6）PEW-SRW指標。

SRW 指標是基于有疊加效應的局部隨機游走提出的，它將隨機步行者在起始點連續釋放，導致目標節點與附近節點之間的更高相似性［6］，即用PEW 模型對其進行校驗，即基于SRW 指標的PEW 模型見式（16）：

7）PEW-MFI指標。

MFI 指標是基于矩陣森林理論提出的，節點x和y之間的相似度可以被理解網絡所有含一個根節點的生成森林中，有多少比例的森林是節點x和y屬于同一個以節點x為根節點的樹［6］，即=(I+L)-1，L為網絡的拉普拉斯矩陣，用PEW 模型對其進行校驗，即基于MFI 指標的PEW 模型見式（17）：

1.3 算法步驟

本文提出的基于信息熵改進PCA 的PEW 模型用于混合鏈路預測的算法步驟如下（以PEW-CN 為例，訓練集Ep占比90%，測試集ET占比10%）：

1）計算CN、Katz、LHNII、SRW、LP、ACT、MFI 的相似性矩陣和特征重要性指數；

2）利用信息熵改進PCA 的算法確定信息融合特征指數；

4）計算AUC（Area Under the Curve）值；

5）循環步驟3）～4）共20 次將得到預測精度AUC 值求平均并輸出。

1.4 算法復雜度分析

對于一個具有n個頂點和e條邊的無向網絡G(n，e)，網絡以鄰接矩陣的格式存儲，對于局部指標，計算復雜度小于基于全局的指標，因此，O（CN）＜O（Katz）、O（LP）＜O（Katz）、和O（SRW）＜O（ACT），而LHNII 可以近似看成是Katz 指標的一個推廣，并且基于全局的指標的計算復雜度往往很高，則近似為O（LHNII）=O（Katz），而MFI 指標是全局指標計算復雜度也很高。本文算法的計算復雜度主要由第1）步產生，即7 個指標的并行運算，因此算法獲得各個指標的相似度矩陣的計算復雜度取最大指標的復雜度，所以本文算法的計算復雜度主要受Katz、MFI 和ACT 指標的影響。

2 實驗與分析

2.1 實驗數據

實驗使用來自6 個不同的領域的復雜網絡數據集進行算法測試，包括交通網絡、社會網絡、生物網絡、技術網絡等。1）美國航空網絡（USAir）（http：//linkprediction.org/index.php/link/ resource/data）；2）代謝網絡（Celegans）（http：//wwwpersonal.umich.edu/～mejn/netdata）；3）路由器層次網絡（Router）（http：//linkprediction.org/index.php/link/resource/data）；4）蛋白質相互作用網絡（Yeast）（http：//www-personal.umich.edu/～mejn/net data）；5）有向政治博客數據集（Political Blogs，PB）（http：//www-personal.umich.edu/～mejn/netdata）；6）維基百科投票晉升到管理人的職位（直到2008 年1 月）（wiki-vote）（https：//snap.stanford.edu/data/wiki-Vote.html）。表1 總結了它們的網絡拓撲特性，其中，|V|為網絡中節點數量，|E|表示邊的數量，〈k〉表示網絡的平均度，C表示網絡平均聚集系數，D表示網絡直徑。

表1 數據集拓撲特征參數Tab.1 Topological feature parameters of datasets

2.2 評價指標

衡量鏈路預測算法好壞的主要指標有AUC［10］、精確度［10］和排序分［10］。AUC 是應用最廣泛的一種衡量鏈路預測結果的方法，它考慮了精確度的同時也考慮了排序分，綜合考慮了所有已存在邊的得分順序與不存在邊的差距。AUC值越大則算法越有效，本文選取AUC 衡量預測準確度。

AUC 評價指標從整體上衡量算法的準確性，是基于測試集中邊的相似值和不存在的邊的相似值的比較，即：

其中：獨立比較n次（n=100 000），測試集中邊的相似值大于不存在的邊的相似值有n'次，測試集中邊的相似值等于不存在的邊的相似值有n″次，AUC＞0.5 的程度衡量了算法在多大程度上優于隨機選擇的算法。

2.3 實驗

隨機森林確定的最佳特征指標后，驗證PEW 模型的有效性。首先，在6 個數據集中與單機制算法作對比，驗證模型對單機制算法校驗的有效性；然后，為了說明所提出的基于PEW 模型的混合鏈路預測算法的可靠性和穩定性，將其與OWA 混合鏈接預測算法和集成模型EMLP 混合鏈路預測算法進行比較。OWA 算法的核心思想是使用三種OWA 運算符以獲得各種相似性指標權重。EMLP 模型的核心思想是基于Logistic 回歸算法和XGBoost 算法將4 個相似性指標作為模型要學習的4 個特征，并根據集合模型的思想結合邏輯回歸和堆疊技術提出的。

2.3.1 特征指標的選擇

為了驗證提取特征的重要性，通過對已有指標的分析，計算了隨機森林集成模型對應的特征重要性指數，通過篩選指標得到了最優的特征集合并將這些特征作為PEW 模型的基準。圖1 給出了每個相似性索引的重要性指數，其用隨機森林特征選擇算法計算的數據集中的每個特征的分數。其中，決策樹的個數為100，特征的個數為7，數據集的70%為訓練集，30%為測試集。

圖1 特征指標的重要性指數Fig.1 Importance indexes of feature indicators

2.3.2 基于信息熵改進PCA的特征信息融合模型

對網絡的多維相似性特征信息進行PCA 融合分析，以USAir 網絡為例，前3 個主相似性特征對應的特征值為λ=［0.007 7，0.001 1，0.000 5］，方差貢獻率為p_i=［83.49%，11.41%，5.1%］。經計算前3 個主相似性特征的累計貢獻率已達到100%，可以總體反映相似性特征的特征信息，因此選擇前3 個主相似性特征確定特征信息融合指數。各個數據集中各個主成分的貢獻率見表2，各個數據集中各個主成分的累計貢獻率見表3。PEW 模型對于選取的主相似性特征，利用信息熵改進PCA 計算多維信息的特征融合指數，最終得到網絡中多維信息對相似性的影響程度，即所占的權重。

表2 不同數據集中各個主成分的貢獻率Tab.2 Contribution rates of principal components in different datasets

表3 不同數據集中各個主成分的累計貢獻率Tab.3 Cumulative contribution rate of each principal component in different datasets

2.3.3 基于PEW模型的鏈路預測算法

將PEW 模型得到的特征信息融合指數用來校驗單機制算法，首先將網絡劃分為90%的訓練集和10%的測試集，求得單機制算法的節點相似性；然后，將多維特征信息融合指數與節點相似性結合，求得最終的節點相似性；最后，執行鏈路預測得到AUC 值并與單機制算法作對比。

為了說明所提出的PEW 模型校驗單機制算法的有效性，本文將其與CN、LP、LHNII、ACT、Katz、SRW 和MFI 這7 個單機制算法做比較，具體值如表4 所示，可以看出基于PEW模型的混合鏈路預測算法與單機制算法相比表現良好，并且AUC 值高于其他指標。

表4 單機制算法校驗中各個算法的AUC值Tab.4 AUC values of each algorithm in single mechanism algorithm verification

單機制算法校驗中所提算法相較對比算法的AUC 提升幅度如圖2 所示，其中PEW-CN →CN 表示PEW-CN 算法對比于CN 算法的提升幅度，其他類似。

圖2 單機制算法校驗中所提算法相較對比算法的AUC提升幅度Fig.2 AUC improvement rate of the proposed algorithm compared with comparison algorithm in single mechanism algorithm verification

從圖2 中可以看到（提升幅度為負數置為零），對本身就有很高的預測精度的單機制算法，基于PEW 模型的校驗效果并不明顯，比如LP 指標，這是因為算法在校驗前就對網絡的結構信息有很好的定義，提供了最好的預測精度，本文所提模型能補充的信息相對較少；對于預測精度較低的算法，PEW 模型能夠提供更多影響相似性度量的結構信息，它的校驗效果就更為突出，比如LHNII 指標。由此可見，這些單機制算法的預測精度在校驗后效果都有提升。對于不同規模的數據集，基于模型校驗后的算法均優于單機制相似性指標的預測精度且預測精度提升效果明顯。對AUC 提升幅度求均值發現，在網絡直徑很大的數據集（Router 和Yeast）中預測精度提升幅度很小，這是因為在這樣的網絡中一個節點的相關信息受更多節點的影響，去除網絡中少許幾條邊后可能會使原來的距離變得更長，說明基于PEW 模型獲得的結構信息存在缺陷，并不是非常全面。綜合來看，經PEW 模型校驗后的單機制算法在預測精度方面有很大的改進，也表明PEW 模型所獲取的網絡特征信息更為全面且能解決單個算法計算相似性時存在的問題，尤其在網絡直徑較小的復雜網絡中預測效果更突出。

整合各種相似性索引的鏈路預測研究仍處于初期階段，所以相關研究結果較少。為了說明所提出的PEW 模型的有效性和穩定性，本文將其與OWA 鏈接預測算法和集成模型EMLP 鏈路預測算法進行比較，主要在6 個真實網絡上進行驗證。如表5 所示，部分算法優于OWA 算法和EMLP 算法，其中PEW-Katz、PEW-MFI 和PEW-SRW 算法在預測精度方面表現更突出。對于平均聚集系數很大的USAir 網絡，本文算法雖然預測精度值優于組合算法OWA，但對于集成算法EMLP 并沒有表現得更優，對于平均聚集系數很小的wiki-vote 網絡亦是如此，而對于其他4 個網絡大部分基于PEW 算法的預測精度相較于對比算法都有一定程度的提升。這表明基于PEW 模型的混合鏈路預測算法在網絡中預測精度更加可靠和穩定。

表5 基于PEW模型的混合鏈路測算法以及OWA和EMLP算法在6個網絡上的AUC值Tab.5 AUC values of hybrid link prediction algorithms based on PEW model，OWA and EMLP algorithms on six networks

綜合而言，在預測精度方面，不論節點數量的多少，本文算法優勢明顯。利用信息熵改進PCA 將復雜網絡結構的多樣性融合得到對相似性影響最大的信息，并確定權重來校驗單機制算法的PEW 模型可以獲得高的預測精度。基于PEW模型的算法能夠補充單機制算法對結構信息度量的不足，特別是網絡直徑較小的網絡，在預測精度上也優于部分混合鏈路預算法。在算法有效性方面，在部分網絡中有良好的預測效果且在大規模網絡的鏈路預測中有較好的效果提升。

3 結語

與其他現有算法相比，本文提出的復雜網絡鏈路預測算法是一種改進。傳統的基于相似度的復雜網絡鏈路預測算法著重于節點的單個相似度指標。為了更好地整合現有的相似性指標，從而進一步提高鏈接預測的穩定性和準確性，本文通過隨機森林進行特征選擇確定了7 個相似性指標，利用信息熵改進PCA 模型將7 個相似性指標組合在一起進行混合鏈路預測。這7 個相似性指標代表了網絡的不同特征。所提的PEW 模型利用信息熵改進PCA 集成了指標并且對已有的單機制算法進行了有效的校驗。利用集成的思想，通過信息融合特征指數，提出了一種新的鏈路預測算法，該算法考慮了不同相似性指標的互補性，因此其穩定性更強。為了證明其有效性和可行性，本文最后在6 個真實網絡中與單一指標相比AUC 值，以驗證所提PEW 模型的有效性，與混合鏈路預測算法相比驗證模型的可靠性和穩定性。本文的主要貢獻是整合現有的相似性指標，利用模型集成的思想引入信息熵改進PCA 獲得了網絡較為全面的結構信息來表征節點相似性，并對單機制算法進行了有效的校驗。將來，本文工作一方面在大量的數據集中驗證算法的適用網絡，另一方面將采用其他算法，研究并提出更有效的模型集成算法，以設計新的鏈路預測框架，這對于復雜網絡的鏈路預測將具有重要的理論和實踐意義。