信息熵改進(jìn)主成分分析模型的鏈路預(yù)測(cè)算法

孟昱煜，郭靜

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

0 引言

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

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

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

1 算法概述

考慮到不同類型指標(biāo)之間的錯(cuò)分樣本集可能不同，從而不同的指標(biāo)可以給出互補(bǔ)的信息，因此本文利用隨機(jī)森林選擇能夠代表網(wǎng)絡(luò)的不同特征和不同思想求解的指標(biāo)作為最佳特征集合，通過基于信息熵改進(jìn)PCA 的特征信息融合模型（PEW）集成特征獲得權(quán)重來衡量不同結(jié)構(gòu)對(duì)連邊的貢獻(xiàn)程度，利用該模型對(duì)現(xiàn)有的相似性指標(biāo)進(jìn)行校驗(yàn)，從而對(duì)提升預(yù)測(cè)性能產(chǎn)生積極的影響。

1.1 基于信息熵改進(jìn)PCA的特征信息融合模型

信息融合是一種多層次多方面的處理過程，通過對(duì)多源數(shù)據(jù)的檢測(cè)、組合、相關(guān)和估計(jì)來決策所需完成的任務(wù)。本文利用隨機(jī)森林確定指標(biāo)重要性指數(shù)確定了最佳指標(biāo)（CN、Katz、LP、LHNI、ACT、SRW 和MFI）。詳細(xì)定義見1.2 節(jié)。

1.1.1 隨機(jī)森林特征選擇

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

1）從訓(xùn)練數(shù)據(jù)集中，應(yīng)用bootstrat 有放回地隨機(jī)抽取K個(gè)新的樣本集，并由此構(gòu)建K棵分類回歸樹，每次未被抽到的樣本組成了K個(gè)袋外數(shù)據(jù)。

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

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

4）將生成的多棵樹組成隨機(jī)森林，用隨機(jī)森林對(duì)新的數(shù)據(jù)進(jìn)行分類，分類結(jié)果按樹分類器的投票多少而定。

通過上述步驟可以對(duì)指標(biāo)進(jìn)行篩選并確定指標(biāo)的重要性，以此提供最優(yōu)的特征集合。

1.1.2 PCA特征融合

主成分分析（PCA）是考察多個(gè)變量間相關(guān)性一種多元統(tǒng)計(jì)法，可以在信息丟失最小的前提下，實(shí)現(xiàn)多元數(shù)據(jù)的特征融合，在提取出主要特征的同時(shí)去除了多源數(shù)據(jù)間的線性相關(guān)［16］。近年來，PCA 在信號(hào)處理、模式識(shí)別、數(shù)字圖像處理等領(lǐng)域得到了廣泛應(yīng)用［17］。在鏈路預(yù)測(cè)問題中，由于節(jié)點(diǎn)之間存在一定的相關(guān)關(guān)系，計(jì)算所得的多維節(jié)點(diǎn)相關(guān)特征也相應(yīng)地存在一定的關(guān)系，為此利用PCA 對(duì)節(jié)點(diǎn)間相似性特征進(jìn)行融合。PCA 特征融合的計(jì)算過程如下：

步驟1 對(duì)原始數(shù)據(jù)矩陣進(jìn)行標(biāo)準(zhǔn)化處理，使各指標(biāo)之間具有可比性，計(jì)算公式為：

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

步驟2 計(jì)算協(xié)方差矩陣，對(duì)于集成相似性矩陣Xm*n，m表示特征個(gè)數(shù)，n表示樣本個(gè)數(shù)，即節(jié)點(diǎn)對(duì)。計(jì)算協(xié)方差矩陣C來反映多變量之間的關(guān)系，計(jì)算公式為：

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

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

步驟5 利用映射矩陣，重構(gòu)主相似性特征矩陣，計(jì)算公式為：

1.1.3 信息熵改進(jìn)PCA

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

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

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

步驟3 計(jì)算相似性特征加權(quán)系數(shù)wi，構(gòu)造加權(quán)矩陣W=diag[w1，w2，…，wm]，計(jì)算公式為：

步驟4 利用加權(quán)矩陣W得到融合相似性特征權(quán)重，計(jì)算公式為：

步驟5 對(duì)融合相似性特征權(quán)重矩陣歸一化處理得到Y(jié)_F'，即特征信息融合權(quán)重。

1.2 PEW模型校驗(yàn)單機(jī)制算法

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

1）PEW-CN指標(biāo)。

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

2）PEW-Katz指標(biāo)。

3）PEW-LP指標(biāo)。

4）PEW-LHNII指標(biāo)。

5）PEW-ACT指標(biāo)。

6）PEW-SRW指標(biāo)。

SRW 指標(biāo)是基于有疊加效應(yīng)的局部隨機(jī)游走提出的，它將隨機(jī)步行者在起始點(diǎn)連續(xù)釋放，導(dǎo)致目標(biāo)節(jié)點(diǎn)與附近節(jié)點(diǎn)之間的更高相似性［6］，即用PEW 模型對(duì)其進(jìn)行校驗(yàn)，即基于SRW 指標(biāo)的PEW 模型見式（16）：

7）PEW-MFI指標(biāo)。

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

1.3 算法步驟

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

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

2）利用信息熵改進(jìn)PCA 的算法確定信息融合特征指數(shù)；

4）計(jì)算AUC（Area Under the Curve）值；

5）循環(huán)步驟3）～4）共20 次將得到預(yù)測(cè)精度AUC 值求平均并輸出。

1.4 算法復(fù)雜度分析

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

2 實(shí)驗(yàn)與分析

2.1 實(shí)驗(yàn)數(shù)據(jù)

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

表1 數(shù)據(jù)集拓?fù)涮卣鲄?shù)Tab.1 Topological feature parameters of datasets

2.2 評(píng)價(jià)指標(biāo)

衡量鏈路預(yù)測(cè)算法好壞的主要指標(biāo)有AUC［10］、精確度［10］和排序分［10］。AUC 是應(yīng)用最廣泛的一種衡量鏈路預(yù)測(cè)結(jié)果的方法，它考慮了精確度的同時(shí)也考慮了排序分，綜合考慮了所有已存在邊的得分順序與不存在邊的差距。AUC值越大則算法越有效，本文選取AUC 衡量預(yù)測(cè)準(zhǔn)確度。

AUC 評(píng)價(jià)指標(biāo)從整體上衡量算法的準(zhǔn)確性，是基于測(cè)試集中邊的相似值和不存在的邊的相似值的比較，即：

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

2.3 實(shí)驗(yàn)

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

2.3.1 特征指標(biāo)的選擇

為了驗(yàn)證提取特征的重要性，通過對(duì)已有指標(biāo)的分析，計(jì)算了隨機(jī)森林集成模型對(duì)應(yīng)的特征重要性指數(shù)，通過篩選指標(biāo)得到了最優(yōu)的特征集合并將這些特征作為PEW 模型的基準(zhǔn)。圖1 給出了每個(gè)相似性索引的重要性指數(shù)，其用隨機(jī)森林特征選擇算法計(jì)算的數(shù)據(jù)集中的每個(gè)特征的分?jǐn)?shù)。其中，決策樹的個(gè)數(shù)為100，特征的個(gè)數(shù)為7，數(shù)據(jù)集的70%為訓(xùn)練集，30%為測(cè)試集。

圖1 特征指標(biāo)的重要性指數(shù)Fig.1 Importance indexes of feature indicators

2.3.2 基于信息熵改進(jìn)PCA的特征信息融合模型

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

表2 不同數(shù)據(jù)集中各個(gè)主成分的貢獻(xiàn)率Tab.2 Contribution rates of principal components in different datasets

表3 不同數(shù)據(jù)集中各個(gè)主成分的累計(jì)貢獻(xiàn)率Tab.3 Cumulative contribution rate of each principal component in different datasets

2.3.3 基于PEW模型的鏈路預(yù)測(cè)算法

將PEW 模型得到的特征信息融合指數(shù)用來校驗(yàn)單機(jī)制算法，首先將網(wǎng)絡(luò)劃分為90%的訓(xùn)練集和10%的測(cè)試集，求得單機(jī)制算法的節(jié)點(diǎn)相似性；然后，將多維特征信息融合指數(shù)與節(jié)點(diǎn)相似性結(jié)合，求得最終的節(jié)點(diǎn)相似性；最后，執(zhí)行鏈路預(yù)測(cè)得到AUC 值并與單機(jī)制算法作對(duì)比。

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

表4 單機(jī)制算法校驗(yàn)中各個(gè)算法的AUC值Tab.4 AUC values of each algorithm in single mechanism algorithm verification

單機(jī)制算法校驗(yàn)中所提算法相較對(duì)比算法的AUC 提升幅度如圖2 所示，其中PEW-CN →CN 表示PEW-CN 算法對(duì)比于CN 算法的提升幅度，其他類似。

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

從圖2 中可以看到（提升幅度為負(fù)數(shù)置為零），對(duì)本身就有很高的預(yù)測(cè)精度的單機(jī)制算法，基于PEW 模型的校驗(yàn)效果并不明顯，比如LP 指標(biāo)，這是因?yàn)樗惴ㄔ谛ｒ?yàn)前就對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)信息有很好的定義，提供了最好的預(yù)測(cè)精度，本文所提模型能補(bǔ)充的信息相對(duì)較少；對(duì)于預(yù)測(cè)精度較低的算法，PEW 模型能夠提供更多影響相似性度量的結(jié)構(gòu)信息，它的校驗(yàn)效果就更為突出，比如LHNII 指標(biāo)。由此可見，這些單機(jī)制算法的預(yù)測(cè)精度在校驗(yàn)后效果都有提升。對(duì)于不同規(guī)模的數(shù)據(jù)集，基于模型校驗(yàn)后的算法均優(yōu)于單機(jī)制相似性指標(biāo)的預(yù)測(cè)精度且預(yù)測(cè)精度提升效果明顯。對(duì)AUC 提升幅度求均值發(fā)現(xiàn)，在網(wǎng)絡(luò)直徑很大的數(shù)據(jù)集（Router 和Yeast）中預(yù)測(cè)精度提升幅度很小，這是因?yàn)樵谶@樣的網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的相關(guān)信息受更多節(jié)點(diǎn)的影響，去除網(wǎng)絡(luò)中少許幾條邊后可能會(huì)使原來的距離變得更長(zhǎng)，說明基于PEW 模型獲得的結(jié)構(gòu)信息存在缺陷，并不是非常全面。綜合來看，經(jīng)PEW 模型校驗(yàn)后的單機(jī)制算法在預(yù)測(cè)精度方面有很大的改進(jìn)，也表明PEW 模型所獲取的網(wǎng)絡(luò)特征信息更為全面且能解決單個(gè)算法計(jì)算相似性時(shí)存在的問題，尤其在網(wǎng)絡(luò)直徑較小的復(fù)雜網(wǎng)絡(luò)中預(yù)測(cè)效果更突出。

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

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

綜合而言，在預(yù)測(cè)精度方面，不論節(jié)點(diǎn)數(shù)量的多少，本文算法優(yōu)勢(shì)明顯。利用信息熵改進(jìn)PCA 將復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的多樣性融合得到對(duì)相似性影響最大的信息，并確定權(quán)重來校驗(yàn)單機(jī)制算法的PEW 模型可以獲得高的預(yù)測(cè)精度。基于PEW模型的算法能夠補(bǔ)充單機(jī)制算法對(duì)結(jié)構(gòu)信息度量的不足，特別是網(wǎng)絡(luò)直徑較小的網(wǎng)絡(luò)，在預(yù)測(cè)精度上也優(yōu)于部分混合鏈路預(yù)算法。在算法有效性方面，在部分網(wǎng)絡(luò)中有良好的預(yù)測(cè)效果且在大規(guī)模網(wǎng)絡(luò)的鏈路預(yù)測(cè)中有較好的效果提升。

3 結(jié)語(yǔ)

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