郭 靜，孟昱煜

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

現(xiàn)實中許多復(fù)雜系統(tǒng)都可以被復(fù)雜網(wǎng)絡(luò)刻畫表示，比如因特網(wǎng)［1］、萬維網(wǎng)［2］、社交網(wǎng)絡(luò)［3］和蛋白質(zhì)網(wǎng)絡(luò)［4］等等.通過研究復(fù)雜網(wǎng)絡(luò)的信息傳播、社團結(jié)構(gòu)以及鏈路預(yù)測等特性來挖掘真實復(fù)雜系統(tǒng)存在的信息、相互關(guān)系和結(jié)構(gòu)特性等等［5］.對于任何一種網(wǎng)絡(luò)都可以用點和邊組成的圖表示，這樣的圖定義為G（V，E），其中：V是頂點集合；E是連邊集合.在復(fù)雜網(wǎng)絡(luò)研究與應(yīng)用中，鏈路預(yù)測是指通過已知的網(wǎng)絡(luò)拓撲結(jié)構(gòu)以及網(wǎng)絡(luò)節(jié)點屬性等信息，預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個節(jié)點之間產(chǎn)生鏈接的可能性或者推斷網(wǎng)絡(luò)中缺失的連邊［6］.它的一些應(yīng)用包括在社交網(wǎng)絡(luò)中的朋友推薦［7］、預(yù)測蛋白質(zhì)之間的相互作用［8］、推斷網(wǎng)絡(luò)演化機制［9］等.

目前，已提出的鏈路預(yù)測方法主要有基于局部信息、全局信息和準局部3種相似性度量.基于局部信息的算法是根據(jù)節(jié)點間的相似性選擇鄰居節(jié)點并進行預(yù)測，此類算法可以非常有效地計算相似性指數(shù)，并且在許多情況下可以很好地執(zhí)行并且適合大規(guī)模的網(wǎng)絡(luò)應(yīng)用，如：共同鄰居指標（common neighbor index，CN）［10］關(guān)注兩個節(jié)點是否處于同一個環(huán)境；Jaccard相似性指標［10］是在任意兩點之間的共同鄰居數(shù)量的基礎(chǔ)上引入節(jié)點度來刻畫相似性；AA（adamic-adar index，AA）指標［10］的思想是度小的共同鄰居節(jié)點的貢獻大于度大的共同鄰居節(jié)點；資源分配（resource allocation，RA）指標［10］考慮網(wǎng)絡(luò)中沒有直接相連的節(jié)點通過共同鄰居傳遞資源；優(yōu)先鏈接指標（preferential attachment，PA）算法［10］定義為新鏈接連接節(jié)點的概率正比于兩節(jié)點度的乘積；文獻［11］考慮到預(yù)測節(jié)點和鄰居節(jié)點的全面影響構(gòu)建新算法（ZHA），此方法需要隨機實驗分別進行10次、100次，以確定其適用性和精度并不適用于大規(guī)模網(wǎng)絡(luò).基于全局信息的算法是根據(jù)整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)度量相似性，如Katz索引［10］考慮了節(jié)點的全路徑信息，預(yù)測效果有所提高但復(fù)雜度較高，在大規(guī)模網(wǎng)絡(luò)中表現(xiàn)不佳.基于準局部信息的方法，它比局部索引考慮更多的信息，同時放棄了對預(yù)測準確性沒有貢獻或貢獻很小的多余信息，如：局部路徑相似性（local path，LP）指標［10］在共同鄰居基礎(chǔ)上，考慮了三階路徑的影響，同時以長度為2和3的路徑數(shù)目作為聯(lián)合貢獻來計算節(jié)點間相似性，并不適用于平均最短距離較大的網(wǎng)絡(luò)；文獻［12］根據(jù)源節(jié)點的影響選擇下一個節(jié)點，并使用互信息計算節(jié)點的不對稱相互影響性提出了一種偏好隨機游走算法（mutual influence random walk，MIRW），此方法中隨機游走的最佳長度的指定存在難度.文獻［13］研究發(fā)現(xiàn)具有不同相似性參數(shù)的網(wǎng)絡(luò)可以采用不同的方法來提高鏈路預(yù)測的準確性，不同節(jié)點所攜帶標簽重要性也不同，并通過偏好鏈接機制來提升鏈路預(yù)測的準確性.隨之還提出了大多數(shù)基于最大似然方法的替代方法［14］.基于最大似然的方法以網(wǎng)絡(luò)結(jié)構(gòu)的某些組織原則為前提計算任何未觀察到的鏈接的可能性，如隨機塊模型，它將節(jié)點分為幾組，兩個節(jié)點連接的可能性僅取決于它們所屬的組.近幾年，此領(lǐng)域的研究引入融合的思想，將已有指標集成來達到更好的效果，例如：文獻［15］提出的OWA（ordered weighted averaging，OWA）算法的核心思想是使用三種OWA運算符，即最大熵方法、最小方差方法和卡方方法，以獲得各種相似性指標權(quán)重，此方法需要大量實驗確定最佳參數(shù)；文獻［16］提出了一種線性模型來集成各種單一指標，并采用兩個典型的模型平均方法（S-AIC和S-BIC）用于鏈路預(yù)測，此方法僅使用連接的節(jié)點對提出了線性回歸模型，而忽略了間接連接的節(jié)點對的影響；文獻［17］提出的信息熵改進主成分分析（PCA）模型的鏈路預(yù)測算法是根據(jù)組合的思想將7個相似性指標組合在一起并對特征信息賦予權(quán)重，此算法很好地校驗了單機制算法.這些方法都是集成許多從不同角度提出的不同單機制方法來達成更好的效果，本文旨在研究單機制方法.

上述方法中：基于節(jié)點局部信息的方法運算復(fù)雜度最低，且預(yù)測準確度較高，因此常被用作基準指標，這些指標考慮的是節(jié)點的共同鄰居數(shù)量以及節(jié)點度，對于大規(guī)模網(wǎng)絡(luò)，節(jié)點的拓撲結(jié)構(gòu)信息少之又少，尤其忽略了節(jié)點自身和鄰居節(jié)點的結(jié)構(gòu)信息對鏈路連接的影響；基于節(jié)點全局信息的方法不適用于大型網(wǎng)絡(luò)，這些指標雖然考慮到了很多信息，但存在對預(yù)測準確性沒有貢獻或貢獻很小的多余信息使得計算耗時；基于準局部信息的指標，在對已有指標的研究中［18］指出Katz指標受曲線下面積（the area under the curve，AUC）值的影響最佳并高于LP指標；從實際應(yīng)用的角度來看，最大似然法的一個明顯的缺點是非常耗時，而且適用的網(wǎng)絡(luò)需要具有特殊的組織結(jié)構(gòu).針對上述問題，本文研究算法主要從局部信息出發(fā)，引入本地網(wǎng)絡(luò)的概念，在一階和二階鄰居信息共同作用下通過相對熵度量節(jié)點間的相似性.這里使用本地網(wǎng)絡(luò)的結(jié)構(gòu)特征來表示復(fù)雜網(wǎng)絡(luò)中節(jié)點的結(jié)構(gòu)特征，換句話說，節(jié)點對整個網(wǎng)絡(luò)上的影響被圍繞它的本地網(wǎng)絡(luò)的結(jié)構(gòu)特征替換，例如：在社交網(wǎng)絡(luò)中，一個重要的人總是有一些重要的朋友；另一方面，節(jié)點對整個網(wǎng)絡(luò)的影響不僅由他的朋友的數(shù)量決定，而且還由他的本地網(wǎng)絡(luò)決定，節(jié)點本身對整個網(wǎng)絡(luò)沒有直接影響，產(chǎn)生影響的是該節(jié)點構(gòu)建的本地網(wǎng)絡(luò)［19］.為了更好地刻畫節(jié)點的信息，引入一階和二階鄰居信息定義二階本地網(wǎng)絡(luò)，利用其結(jié)構(gòu)的差異來量化節(jié)點的結(jié)構(gòu)相似度，基于此提出了一種基于相對熵和節(jié)點局部結(jié)構(gòu)的節(jié)點結(jié)構(gòu)相似性鏈路預(yù)測方法，將本文算法與ZHA、MIRW、OWA、Jaccard、PA和Katz等6種算法作對比，利用在7個實際網(wǎng)絡(luò)數(shù)據(jù)集上的仿真實驗測試所提算法的性能.

1 相對熵

相對熵（relative entropy）［20］，也稱KL散度（Kullback-Leibler divergence），可以用來衡量兩個概率分布之間的差異.假設(shè)p（x）、q（x）是關(guān)于離散隨機變量x的兩個概率分布，則p對q的相對熵為

在實際應(yīng)用中相對熵可以有效衡量兩個概率分布之間的差異，但由于相對熵不具有對稱性，即DKL（p‖q）≠DKL（q‖p），本文需要根據(jù)這個性質(zhì)對其進行重新定義，來有效地衡量兩個離散型變量概率分布的差異程度，重新定義公式為

2 算法概述

本文首先定義節(jié)點的本地網(wǎng)絡(luò)，以獲取節(jié)點的鄰居結(jié)構(gòu)信息，再計算兩個節(jié)點的概率分布的相對熵，進而得到該節(jié)點對的結(jié)構(gòu)相似性.

2.1 本地網(wǎng)絡(luò)

在復(fù)雜網(wǎng)絡(luò)的研究中，局部結(jié)構(gòu)起著重要作用.在早期的社區(qū)發(fā)現(xiàn)算法中，真實網(wǎng)絡(luò)因為其規(guī)模太大或動態(tài)變化的特點使得全局結(jié)構(gòu)信息很難被識別，從而引入了局部信息的概念處理這一問題.而在鏈路預(yù)測的研究中最早期的研究主要是應(yīng)用節(jié)點的屬性信息的馬爾科夫鏈和機器學(xué)習(xí)思路而展開的方法，但這類方法中節(jié)點屬性信息的獲取難度較大.由此，研究更傾向于基于網(wǎng)絡(luò)結(jié)構(gòu)，此類算法僅利用節(jié)點的局域信息表征節(jié)點的結(jié)構(gòu)特征，節(jié)點本身對整個網(wǎng)絡(luò)沒有直接影響，影響是由圍繞該節(jié)點的局域網(wǎng)構(gòu)建的［18］.局部網(wǎng)絡(luò)就是由節(jié)點和節(jié)點的鄰居構(gòu)建的，每個節(jié)點本身也包含在局部網(wǎng)絡(luò)中，如圖1所示，圖1（a）中顯示了節(jié)點1的一階本地網(wǎng)絡(luò)，包含了節(jié)點的一階鄰居信息.一階本地網(wǎng)絡(luò)包含節(jié)點本身和節(jié)點的一階鄰居節(jié)點信息，但由于真實網(wǎng)絡(luò)數(shù)據(jù)規(guī)模太大的特點，一階本地網(wǎng)絡(luò)所考慮到的節(jié)點信息并不全面，因此本文重新定義了二階本地網(wǎng)絡(luò)，它包含節(jié)點鄰居的鄰居信息，圖1（b）顯示了節(jié)點1的二階本地網(wǎng)絡(luò)，二階本地網(wǎng)絡(luò)包含節(jié)點本身和節(jié)點的一階鄰居、二階鄰居信息.

圖1 本地網(wǎng)絡(luò)定義Fig．1 Local network definition

2.2 基于二階本地網(wǎng)絡(luò)相對熵的相似度指標

相似性度量可以看作其結(jié)構(gòu)差異信息的計算，換句話說，測量節(jié)點的相似度是在局部結(jié)構(gòu)信息之間找到差異，因此，可以用相對熵量化每對節(jié)點之間的差異，如果兩個節(jié)點的差異很小，那么它們具有很大的相似性，反之亦然.

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

節(jié)點x的局域網(wǎng)由Lx（N，D）表示，其中：N代表局域網(wǎng)中的節(jié)點集；D代表N中每個節(jié)點的度．首先獲取節(jié)點的結(jié)構(gòu)信息，然后通過計算每個節(jié)點的局部相對熵［21］來確定每對節(jié)點的相似度．在整個網(wǎng)絡(luò)中，將網(wǎng)絡(luò)的最大節(jié)點度定義為m=Dmax，也是概率集的標度．節(jié)點x的概率集被定義為

概率集中的元素基于本地網(wǎng)絡(luò)Lx（N，D）中的度集D和本地網(wǎng)絡(luò)的總程度m來定義．節(jié)點x本地網(wǎng)絡(luò)Lx（N，D）中的總程度DL（x）被定義為

其中：D（k）表示節(jié)點x的程度集．

在復(fù)雜網(wǎng)絡(luò)中，絕大多數(shù)節(jié)點的度小于Dmax，因此當度小于Dmax時，概率集中剩余元素的值等于0，則p（x，k）定義為：

其中：Degree（x）表示節(jié)點x的度．

在信息理論中，使用相對熵來量化兩個概率分布的差異．相對熵的值顯示兩個概率分布之間的統(tǒng)計差異．概率集中每個元素的順序?qū)⒂绊懴鄬氐闹岛拖嗨贫葴y量的準確性．在計算它們的相對熵之前，應(yīng)處理概率集中的每個元素的順序，在該方法中，每個概率集都以減小的順序排序．節(jié)點x的新排序概率集被定義為

基于新排序的概率集來計算每對節(jié)點的相對熵，從而得到網(wǎng)絡(luò)的相似性矩陣Sxy．節(jié)點x相對節(jié)點y的局部相對熵定義為

在定量分析網(wǎng)絡(luò)中節(jié)點x與y之間的互異程度后，接下來利用局部相對熵刻畫節(jié)點間的相似性．

定義1［21］節(jié)點間基于局部相對熵的相似度（local relative entropy，RE）．對于一個網(wǎng)絡(luò)G（V，E），x和y為任意2個未連接的節(jié)點，其相似度可以通過x和y相互之間局部相對熵的和與單位量的差值來定義，如式（8）所示．

其中：H（x，y）表示節(jié)點x和y相互之間的局部相對熵，但是相對熵不具對稱性，而每對節(jié)點的相似性值應(yīng)該彼此等于，因此，每對節(jié)點的局部相對熵定義為H（x，y）=1／（2×（DKL（x‖y）+DKL（y‖x）））；max（H）表示一個網(wǎng)絡(luò)中所有節(jié)點對局部相對熵的最大值，因為相對熵代表的含義是兩個節(jié)點之間的差異程度，因此式（8）可以計算節(jié)點間基于局部相對熵的相似度．

對于節(jié)點和節(jié)點鄰居構(gòu)成的一階本地網(wǎng)絡(luò)，本文考慮了節(jié)點更多的結(jié)構(gòu)信息，對一階本地網(wǎng)絡(luò)進行擴展，進一步考慮二階本地網(wǎng)絡(luò)，即引入節(jié)點、節(jié)點的鄰居信息和節(jié)點鄰居的鄰居信息．注意，針對二階本地網(wǎng)絡(luò)求取相似度時，需要排除網(wǎng)絡(luò)一階鄰居．網(wǎng)絡(luò)二階鄰居生成概率集時，由于節(jié)點鄰居的鄰居數(shù)量大多數(shù)大于網(wǎng)絡(luò)中最大的度數(shù)，所以概率集的標度重新定義為m=N，N為二階本地網(wǎng)絡(luò)中的節(jié)點數(shù)．基于一階本地網(wǎng)絡(luò)的節(jié)點相似性的產(chǎn)生規(guī)則，利用式（7）計算二階本地網(wǎng)絡(luò)中節(jié)點對的局部相對熵，根據(jù)式（8）得到基于二階本地網(wǎng)絡(luò)的節(jié)點相似度．

2．2．2 基于本地網(wǎng)絡(luò)相對熵的相似度指標

本文在一階本地網(wǎng)絡(luò)的基礎(chǔ)上引入二階本地網(wǎng)絡(luò)，考慮更多的節(jié)點結(jié)構(gòu)信息以便利用相對熵更好地度量節(jié)點相似性，綜合節(jié)點的結(jié)構(gòu)信息和節(jié)點鄰居的結(jié)構(gòu)信息，將基于本地網(wǎng)絡(luò)的節(jié)點相似度重新定義為

其中：Sxy是一階本地網(wǎng)絡(luò)的相似度矩陣；α為調(diào)節(jié)參數(shù)，表示二階鄰居節(jié)點對節(jié)點結(jié)構(gòu)相似度的影響程度，可以根據(jù)具體的網(wǎng)絡(luò)選取最合適的值，當α=0時，S′xy表示RE算法一階本地網(wǎng)絡(luò)的相似度矩陣；是RE算法二階本地網(wǎng)絡(luò)的相似度矩陣．

2．3 算法復(fù)雜度分析

對于一個具有n個頂點、e條邊的無向網(wǎng)絡(luò)G（n，e），網(wǎng)絡(luò)以鄰接矩陣的格式存儲．首先，計算7個索引指標得到相似度矩陣，該過程的時間復(fù)雜度為O（n）；然后，計算二階鄰居結(jié)構(gòu)對相似性的貢獻程度，該過程的時間復(fù)雜度為O（n）；最后，計算一階相對熵所用時間O（m′），即整個網(wǎng)絡(luò)的最小度數(shù)加1，此時計算一階相似度的時間復(fù)雜度為O（n+m′），隨著網(wǎng)絡(luò)規(guī)模的增長，m′遠遠小于n，即該過程的時間復(fù)雜度為O（n）；同理可知，二階相似度的時間復(fù)雜度為O（n），運行一次的算法復(fù)雜度是O（2n）．

3 仿真實驗驗證

3.1 實驗數(shù)據(jù)

實驗使用7個公開的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集進行算法測試：爵士音樂家合作網(wǎng)絡(luò)Jazz；代謝網(wǎng)絡(luò)Celegans，此網(wǎng)絡(luò)中節(jié)點表示線蟲的神經(jīng)元，邊表示神經(jīng)元突出或間隙鏈接；路由器層次網(wǎng)絡(luò)Router，節(jié)點代表路由器，節(jié)點相連則表示路由器之間通過光纜等方式直接交換數(shù)據(jù)包；蛋白質(zhì)相互作用網(wǎng)絡(luò)Yeast，節(jié)點代表蛋白質(zhì)，邊代表蛋白質(zhì)相互作用關(guān)系；Net-Science（NS），此網(wǎng)絡(luò)中節(jié)點代表科學(xué)家，邊則表示相連的科學(xué)家之間存在合作關(guān)系；有向政治博客數(shù)據(jù)集Political blogs（PB），數(shù)據(jù)集中的每個結(jié)點都有一個屬性描述（用0或者1表示），表示民主或者保守；維基百科投票網(wǎng)絡(luò)（wiki-vote），邊A-B意味著用戶A給用戶B投票，原網(wǎng)絡(luò)為有向網(wǎng)絡(luò)，文中忽略了方向信息，將其當作無向網(wǎng)絡(luò)處理.表1總結(jié)了它們的網(wǎng)絡(luò)拓撲特性，其中：｜V｜為網(wǎng)絡(luò)中節(jié)點數(shù)量；｜E｜表示邊的數(shù)量；〈K〉表示網(wǎng)絡(luò)的平均度；C表示網(wǎng)絡(luò)平均聚集系數(shù)；D表示網(wǎng)絡(luò)直徑.

表1 數(shù)據(jù)集拓撲特征參數(shù)Tab．1 Topological characteristic parameters of dataset

在實驗中，首先根據(jù)式（9）確定了RE算法在各個數(shù)據(jù)集中所需要的參數(shù)大小，并根據(jù)式（10）計算AUC精確度，確定最佳的AUC精度；然后為了測試本文算法的性能，設(shè)置訓(xùn)練集合ET中邊數(shù)占比為99%，90%和80%，測試集合EP中邊數(shù)占比為1%，10%和20%，分別與基于組合各種局部相似性指標的OWA算法和基于局部信息的ZHA、MIRW、Jaccard、PA和Katz0.01算法對比AUC精度值，每個實際測試結(jié)果均為20次結(jié)果的均值；最后在訓(xùn)練集占90%的情況下比較算法的AUC精確度，并用三個占比之間的AUC精度的差值來衡量算法的穩(wěn)定性.

3.2 評價指標

衡量鏈路預(yù)測算法好壞的主要指標有AUC［19］、精確度［19］和排序分［19］.精確度指標首先取出測試中分數(shù)最靠前的L個連邊，然后找出這L個連邊實際存在的概率；排序分是測試集中正確邊的得分在所有排列中的位置；而AUC是應(yīng)用最廣泛的一種衡量鏈路預(yù)測結(jié)果的方法.因此本文選擇AUC作為評價指標，它考慮了精確度的同時也考慮了排序分，綜合考慮了所有已存在邊的得分順序與不存在邊的差距，AUC值越大，則算法越有效.

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

其中：n（n=10 000）表示獨立比較的次數(shù)；n′表示測試集中邊的相似值大于不存在邊的相似值的次數(shù)；n″表示測試集中邊的相似值等于不存在邊的相似值的次數(shù)．

3.3 仿真實驗及結(jié)果分析

3.3.1 參數(shù)α對算法的影響及確定

本文提出的基于本地網(wǎng)絡(luò)相對熵的相似度指標綜合考慮了一階和二階鄰居信息對節(jié)點相似性的影響，對于基于半局部路徑的相似性度量方法，認為更長路徑對預(yù)測性能提升的空間有限，甚至某些情況下會引入過多的噪音信息，導(dǎo)致預(yù)測準確率下降，通常僅考慮二階、三階路徑，最多到四階路徑［22］.因此本文考慮了節(jié)點的三階路徑，即忽略三階鄰居信息的影響，因為二階鄰居信息對節(jié)點相似度的影響小于一階鄰居信息，并且通過實驗發(fā)現(xiàn)α在［0，1］的范圍內(nèi)，預(yù)測性能有一個高點，因此確定α∈（0，1）．α值直接影響RE的預(yù)測準確率，為確定合適的α值，在（0，1）范圍內(nèi)，以0.001作為步長，選取不同的α值，以RE指標進行預(yù)測，并計算相應(yīng)預(yù)測評價標準AUC平均值.

圖2表示在數(shù)據(jù)集分為90%訓(xùn)練集和10%測試集的情況下RE指標在各數(shù)據(jù)集中的預(yù)測性能，AUC預(yù)測精度越高，準確率越高，算法更優(yōu).α=0時只考慮了一階本地網(wǎng)絡(luò)的信息，由圖2可知：α=0時的AUC精度值小于α＞0的精度值．隨著α的增大，二階本地網(wǎng)絡(luò)的信息在指標中越發(fā)重要，但隨著α繼續(xù)上升，不同的網(wǎng)絡(luò)在預(yù)測性能上發(fā)生了不同程度的變化：Jazz，Celegans，Yeast和PB網(wǎng)絡(luò)平均聚集系數(shù)較大，導(dǎo)致可調(diào)參數(shù)α波動明顯，這是因為這些網(wǎng)絡(luò)本身的特性使得二階本地網(wǎng)絡(luò)信息成為了預(yù)測的重要影響信息，網(wǎng)絡(luò)越密集二階本地網(wǎng)絡(luò)信息對其影響越大，但是圖2的曲線波動程度并不與網(wǎng)絡(luò)平均聚集系數(shù)成正比，對于NS網(wǎng)絡(luò)和Jazz網(wǎng)絡(luò)，雖然平均聚集系數(shù)很大，但二階本地網(wǎng)絡(luò)對它影響不明顯，這說明二階本地網(wǎng)絡(luò)對于部分網(wǎng)絡(luò)考慮的信息是有局限的，并不能涵蓋全部信息，考慮到算法的復(fù)雜度問題將不再對三階本地網(wǎng)絡(luò)進行實驗；對于Router網(wǎng)絡(luò)和wiki-vote網(wǎng)絡(luò)，由于平均聚集系數(shù)很小，使得一階本地網(wǎng)絡(luò)基本涵蓋了全部信息，從而導(dǎo)致二階本地網(wǎng)絡(luò)對節(jié)點相似性的影響并不大.α值決定了二階本地網(wǎng)絡(luò)的重要程度，因此需要根據(jù)不同的數(shù)據(jù)集確定最佳的α值，在真實數(shù)據(jù)集上通過做大量的參數(shù)調(diào)優(yōu)實驗確定了不同網(wǎng)絡(luò)的最佳α值，具體值見表2.

表2 不同網(wǎng)絡(luò)中α的最佳值（90%訓(xùn)練集）Tab．2 Optimal value ofαin different networks（90% training sets）

圖2 不同參數(shù)下的AUC預(yù)測精度（90%訓(xùn)練集）Fig．2 Prediction accuracy of AUC under different parameters（90% training sets）

3.3.2 算法性能對比

將網(wǎng)絡(luò)中90%的鏈路作為訓(xùn)練集，其余10%作為測試集，按照上述介紹的實驗流程得到各個算法的預(yù)測結(jié)果，其中α取表2中的值，并計算相應(yīng)的AUC預(yù)測精度，以用來衡量本文算法的性能.表3表示各數(shù)據(jù)集在不同指標下的平均AUC預(yù)測精度，在Celegans數(shù)據(jù)集中除MIRW算法外，本文算法RE均優(yōu)于其他的對比算法，較ZHA，Jaccard，OWA，PA和Katz0.01算法分別提高了9.93%，8.48%，1.84%，12.36%，1.89%；在Yeast數(shù)據(jù)集中較Jaccard，PA，Katz0.01，ZHA算法分別提高了1.58%，6.66%，1.09%，1.6%；PB數(shù)據(jù)集中本文算法RE均優(yōu)于其他的對比算法，本文算法分別平均提高6.42%，3.14%，0.96%，2.88%，1.76%，5.74%，表現(xiàn)出了很好的效果；wikivote數(shù)據(jù)集中本文算法RE較ZHA，Jaccard，MIRW，PA和Katz0.01分別提高了0.45%，1.89%，1.36%，0.08%，55.61%；Jazz網(wǎng)絡(luò)中RE指標相較于PA指標提高了9.1%，相較于MIRW指標提高了6.2%；Router網(wǎng)絡(luò)中相較于PA提高了9.2%，與Jaccard相比提高了13.2%，與MIRW相比提高了1.71%；NS網(wǎng)絡(luò)中相較于PA算法提高了5.19%.雖然本文算法RE在個別網(wǎng)絡(luò)中性能表現(xiàn)不佳，但與個別算法作對比時性能還是有所提升，綜合考慮本文算法在各網(wǎng)絡(luò)中達到的鏈路預(yù)測性能，說明利用相對熵理論并綜合考慮二階本地網(wǎng)絡(luò)節(jié)點信息的相似性指標在預(yù)測時能獲得更加全面的網(wǎng)絡(luò)結(jié)構(gòu)信息，從而有效地提高了預(yù)測精度.通過觀察所選數(shù)據(jù)集的網(wǎng)絡(luò)特性，本文所提算法并不適用于平均聚集系數(shù)很大的網(wǎng)絡(luò)，比如Jazz網(wǎng)絡(luò)和Net-Science網(wǎng)絡(luò)；而對于連接密度低的網(wǎng)絡(luò)有非常好的表現(xiàn)，比如wikivote網(wǎng)絡(luò)、Celegans網(wǎng)絡(luò)、Yeast網(wǎng)絡(luò)和PB網(wǎng)絡(luò)；對于特定網(wǎng)絡(luò)Router，本文算法精度也有較好的表現(xiàn).由此說明本文算法適用于連接密度低、簇系數(shù)小的網(wǎng)絡(luò)，并且在大規(guī)模網(wǎng)絡(luò)上也有較好的表現(xiàn).

表3 各數(shù)據(jù)集中平均AUC預(yù)測精度（90%訓(xùn)練集）Tab．3 Average AUC prediction accuracy of each data set（90% training sets）

為了綜合評估算法的性能，在訓(xùn)練集ET分別為99%，90%和80%的比例下進行實驗，由于在訓(xùn)練集比例降低的情況下，節(jié)點間將失去良好的連通性，預(yù)測時缺少更多的鏈路信息，因此不再考慮更小的訓(xùn)練集比例.重復(fù)上述實驗過程，獲得每種預(yù)測算法的平均預(yù)測精度AUC的值，測試結(jié)果見圖3.柱狀圖從左到右分別為ZHA，MIRW，Jaccard，OWA，PA，Katz0.01和本文算法RE.仿真實驗發(fā)現(xiàn)：當訓(xùn)練集從99%減少到80%時，所有預(yù)測算法的AUC都降低，這是因為訓(xùn)練集比例減小，導(dǎo)致預(yù)測時獲取的網(wǎng)絡(luò)信息減少［23］，但無論訓(xùn)練集比例怎么變化，本文算法在Celegans網(wǎng)絡(luò)、Yeast網(wǎng)絡(luò)、PB網(wǎng)絡(luò)和wiki-vote網(wǎng)絡(luò)中都有很好的預(yù)測精度，并且隨著測試集比例的降低其受影響程度較小.

圖3 不同數(shù)據(jù)集中的AUC評估值Fig．3 AUC evaluation values in different data sets

表4和表5表示各算法在不同比例訓(xùn)練集的AUC差值的具體值.從表4～5可以看出：在PB和Router網(wǎng)絡(luò)中，本文算法比ZHA，MIRW，OWA和Jaccard算法的AUC差值要小，算法性能更穩(wěn)定；在wiki-vote網(wǎng)絡(luò)中本文算法比Katz0.01算法性能要更穩(wěn)定；而在Jazz，Celegans，NS和Yeast網(wǎng)絡(luò)中，基于二階本地網(wǎng)絡(luò)相對熵的算法對比于其他算法，AUC的差值很小.由此說明本文算法預(yù)測結(jié)果隨著訓(xùn)練集降低沒有顯著變化，算法更能適應(yīng)復(fù)雜環(huán)境.

表4 在99%和90%比例的訓(xùn)練集中各算法的AUC差值Tab．4 AUC difference of each algorithm in 99% and 90% proportion of training sets

表5 在90%和80%比例的訓(xùn)練集中各算法的AUC差值Tab．5 AUC difference of each algorithm in 90% and 80% proportion of training sets

4 結(jié)論

基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性方法具有簡單、復(fù)雜度低且效果好的特點，受到該領(lǐng)域?qū)W者普遍關(guān)注.在網(wǎng)絡(luò)中，針對節(jié)點的結(jié)構(gòu)信息對度量相似性存在影響的問題，從信息論角度出發(fā)，提出了一種基于相對熵和節(jié)點局部結(jié)構(gòu)的節(jié)點結(jié)構(gòu)相似性鏈路預(yù)測方法.首先，為了刻畫節(jié)點的局部結(jié)構(gòu)，引入了二階本地網(wǎng)絡(luò)的概念；然后，為了刻畫節(jié)點對之間的結(jié)構(gòu)相似性，重新定義了相對熵；最后，基于相對熵度量節(jié)點結(jié)構(gòu)相似性，考慮節(jié)點鄰居的鄰居結(jié)構(gòu)信息，提出相對熵度量節(jié)點結(jié)構(gòu)相似性指標.在7個實際網(wǎng)絡(luò)數(shù)據(jù)集上的仿真實驗測試表明：相比其他基于局部和全局信息的相似指標，所提方法在AUC衡量標準下能夠取得更好的效果，并且在訓(xùn)練集比例下降的情況下，算法的性能依然穩(wěn)定；通過觀察所選數(shù)據(jù)集的網(wǎng)絡(luò)特性，本文所提算法更適用于連接密度低、簇系數(shù)小的網(wǎng)絡(luò)；考慮了節(jié)點鄰居的結(jié)構(gòu)信息后，其預(yù)測效果有了明顯提升，這也證實了從信息論角度出發(fā)可以有效解決復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測問題，并且節(jié)點鄰居的結(jié)構(gòu)信息對網(wǎng)絡(luò)中節(jié)點建立連邊的過程影響較大.本文的主要貢獻是將信息論引入到鏈路預(yù)測問題中并考慮到了節(jié)點鄰居的結(jié)構(gòu)信息，下一步，將考慮引進其他的相似性指標進行混合鏈路預(yù)測并提升精度的相關(guān)研究.