利用相對熵度量節點結構相似性的鏈路預測算法

郭 靜，孟昱煜

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

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

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

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

1 相對熵

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

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

2 算法概述

本文首先定義節點的本地網絡，以獲取節點的鄰居結構信息，再計算兩個節點的概率分布的相對熵，進而得到該節點對的結構相似性.

2.1 本地網絡

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

圖1 本地網絡定義Fig．1 Local network definition

2.2 基于二階本地網絡相對熵的相似度指標

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

2.2.1 節點相似性度量

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

概率集中的元素基于本地網絡Lx（N，D）中的度集D和本地網絡的總程度m來定義．節點x本地網絡Lx（N，D）中的總程度DL（x）被定義為

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

在復雜網絡中，絕大多數節點的度小于Dmax，因此當度小于Dmax時，概率集中剩余元素的值等于0，則p（x，k）定義為：

其中：Degree（x）表示節點x的度．

在信息理論中，使用相對熵來量化兩個概率分布的差異．相對熵的值顯示兩個概率分布之間的統計差異．概率集中每個元素的順序將影響相對熵的值和相似度測量的準確性．在計算它們的相對熵之前，應處理概率集中的每個元素的順序，在該方法中，每個概率集都以減小的順序排序．節點x的新排序概率集被定義為

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

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

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

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

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

2．2．2 基于本地網絡相對熵的相似度指標

本文在一階本地網絡的基礎上引入二階本地網絡，考慮更多的節點結構信息以便利用相對熵更好地度量節點相似性，綜合節點的結構信息和節點鄰居的結構信息，將基于本地網絡的節點相似度重新定義為

其中：Sxy是一階本地網絡的相似度矩陣；α為調節參數，表示二階鄰居節點對節點結構相似度的影響程度，可以根據具體的網絡選取最合適的值，當α=0時，S′xy表示RE算法一階本地網絡的相似度矩陣；是RE算法二階本地網絡的相似度矩陣．

2．3 算法復雜度分析

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

3 仿真實驗驗證

3.1 實驗數據

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

表1 數據集拓撲特征參數Tab．1 Topological characteristic parameters of dataset

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

3.2 評價指標

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

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

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

3.3 仿真實驗及結果分析

3.3.1 參數α對算法的影響及確定

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

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

表2 不同網絡中α的最佳值（90%訓練集）Tab．2 Optimal value ofαin different networks（90% training sets）

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

3.3.2 算法性能對比

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

表3 各數據集中平均AUC預測精度（90%訓練集）Tab．3 Average AUC prediction accuracy of each data set（90% training sets）

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

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

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

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

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

4 結論

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