鏈路預測中的一種局部結構相似度算法

尹永超，徐 敏，傅皇麟，孫勝男

1(南京航空航天大學 計算機科學與技術學院，南京 211106) 2(軟件新技術與產業化協同創新中心，南京 210023) 3(云南師范大學 外國語學院，昆明 650500)

1 引 言

21世紀是復雜的世紀，隨著計算機技術的迅猛發展以及人們對現實世界的認識越來越深入，復雜網絡作為一種研究復雜化的網絡結構及其演化技術，越來越受到人們的重視.通過抽象化的網絡結構去模擬現實世界中人與人、人與物之間的相互關系，從而推動現實世界中各種理論及應用的不斷完善與進步.而鏈路預測[1]作為復雜網絡的一個重要應用，通過網絡中節點的結構以及屬性等信息建立網絡關系模型，然后結合復雜網絡的特性去預測還未產生連接的兩個節點之間產生連接的可能性.最后結合具體的應用對相似的節點進行推薦或加權，從而對提升網絡傳播效率，增加節點之間的互動以及進一步了解復雜網絡的傳播機制具有重要意義.例如我們通過對社交網絡中各好友之間關系的分析來預測尚未建立連接的兩個人之間進行交互的可能性，從而對其進行好友推薦[2].或者音樂、電影、新聞類的娛樂網站，通過用戶行為分析，預測不同用戶的喜好以及相互之間的愛好相似度，然后給不同用戶推薦其可能感興趣的物品，這樣對提高網站流量增加用戶依賴度具有很大作用.

當前的鏈路預測算法大都基于相似度指標，即兩個節點之間的相似度越大則節點之間連接的可能性就越大.而大多基于節點相似度指標的算法都以共同鄰居為依據，即兩個節點之間共同鄰居數量越多那么這兩個節點之間就越相似[3].如CN、Salton、Jaccard、HPI、HDI、AA、RA等，這些指標都是在共同鄰居的基礎上進行改進，以適應不同的網絡結構.一些較為復雜的方法，不僅考慮節點的屬性信息，同時利用馬爾科夫鏈[5]及機器學習算法，如隨機游走的相似性指標[4]、樸素貝葉斯[6]、神經網絡[7]、支持向量機、k近鄰等有監督的分類方法.這些方法往往具有較高的預測準確度，但由于計算復雜較高通常僅適用于小規模的網絡.針對不同網絡結構模型的研究也慢慢受到各學者的重視，對于一些比較規律的網絡我們可以針對特殊的網絡結構進行預測.如基于層次結構模型[8]的算法，這種算法認為網絡中的節點可以被聚類成若干群組，而每個群組中的節點又可以被聚類為下一級節點.這種類似于族譜樹的結構，可以很好的模仿新陳代謝以及大腦神經網絡，從而達到較好的預測效果.另一些應用較為廣泛的鏈路預測算法則將網絡中的一些影響因素以有向或者加權的形式進行組合，從而進一步區分不同關系下的預測效果，以達到提高預測精度的目的.近年來基于二部分網絡的鏈路預測算法得到廣泛應用[9]，其在電子商務網絡、在線娛樂、新陳代謝網絡中的應用都取得了很好的預測效果.目前對社交網絡的鏈路預測，逐漸從依賴于節點的屬性信息向只利用網絡結構信息轉移，而基于結構信息的有向加權網絡[10]也越來越受到更多學者的重視.

本文首先介紹了一些較常用的基于節點相似度的指標算法，然后對真實數據集中的網絡結構進行提取，選取了幾個比較常見的基本網絡模型，對以上各指標在不同網絡模型中的側重點進行分析.通過比較各算法的優劣，我們提出了一個較為新穎的基于鄰居節點結構相似度的LSCN指標算法.通過比較一個節點A與另一個節點B的所有鄰居節點的結構相似度來判斷節點A與節點B之間連接的可能性.并且由表2我們可以看出，算法的預測效果在個別網絡中有很大提升.之后我們通過進一步考慮二階鄰居節點的結構相似度，又提出了一個改進的LSCN-Ⅱ指標算法，并通過實驗選取其最佳的α參數，使得不同網絡中的最終的預測效果與LSCN指標相比得到進一步提升.

2 基于局部信息的相似度指標

相似度指標指的是節點之間的相似程度，相似度指標越大就指兩個節點之間越相似且越有可能產生連接.目前大多數的相似度指標算法大都依賴于共同鄰居，即兩個節點之間的共同鄰居數量越多那么這兩個節點越相似.

2.1 僅考慮共同鄰居數量的CN指標

CN指標即Common Neighbors，是基于局部信息的最簡單的相似性指標，如果兩個節點之間的共同鄰居數量越多那么這兩個節點就越相似.CN指標的定義是：對于網絡結構中的節點Vx，其鄰居節點的集合為Γ(x)，則連接節點Vx和Vy的相似度就是它們的共同鄰居數，即

Sxy=|Γ(x)∩Γ(y)|

(1)

2.2 考慮共同鄰居節點數量及終節點度數的指標

CN指標雖然具有比較低的算法復雜度，且具有較高的預測效果.但是僅僅考慮到了節點間共同鄰居的數量，而忽略了節點自身的影響.根據弱連接效應，并且考慮終節點自身的影響，以不同的形式又產生了以下不同的相似性指標：

Salton指標

(2)

LHN-I指標

(3)

以上公式中kx表示節點vx的度數，Γ(x)表示節點vx相連的鄰居節點集合.Salton[11]和LHN-I[12]指標都認為節點vx和vy之間的相似度與兩個節點度數的乘積成反比.

Sorenson指標

(4)

Sorenson[13]指標認為節點vx和節點vy之間的相似度與終節點度數之和成反比.

HPI指標

(5)

HPI[14]指標認為節點vx和節點vy的相似度與兩個節點中最小的節點度數成反比，通常用來對新陳代謝網絡中反應物的拓撲相似程度進行刻畫.

HDI指標

(6)

HDI[15]指標與HPI指標相對應，其將節點vx和節點vy之間的相似度定義為兩個節點中度數最大的節點倒數.

2.3 考慮弱連接效應的指標

計算節點間的相似度，如果僅僅考慮節點之間共同鄰居的數量，未免太過簡單.因為對于每個不同的共同鄰居節點來說，不同鄰居節點的度數也發揮著至關重要的作用.與以上其他節點相比，AA、RA指標不但考慮到了每個不同共有鄰居節點度數的影響，同時其將不同的鄰居節點度數起到的作用進行累加.其同樣考慮到了共有鄰居節點的數量，因此在許多網絡中，這兩個指標通常能起到更好的預測效果.

AA指標

(7)

AA[16]指標將不同共有鄰居節點的權重定義為該節點的度數的對數的倒數.并且將節點vx和vy之間的相似度定義為所有不同共有鄰居節點的權重之和.

RA指標

(8)

RA[15]指標與AA指標之間的最大區別是其對共同鄰居節點權重定義方式不同，前者認為權重以1/k的形式遞減，后者則定義為1/logk的形式.

2.4 僅考慮終節點度數的PA指標

Sxy=kxky

(9)

PA[17]指標僅僅考慮終節點自身度數的影響，且終節點度數越高那么這兩個節點之間的連接概率就越大.在一些特定的網絡中取得了很好的預測效果.如下頁表2所示在Router網絡中，PA指標的預測效果明顯好于其他算法.

2.5 基于局部路徑相似性的LP指標

基于共同鄰居的相似性指標往往計算復雜度較低，但是由于使用的信息非常有限，并且最終的計算結果區分度不大使得預測的精度很難有所提高.LP[18]指標則是在共同鄰居的基礎上，進一步考慮三階路徑的影響.雖然計算復雜較高，但是最終的預測效果幾乎都有所提升.

Sxy=A2+αA3

(10)

上式中A表示節點的鄰接矩陣，A2表示二階路徑的CN指標A3則表示三階路徑矩陣.

3 分析不同網絡結構特征

通過對第四章試驗中提到的8個真實網絡數據集進行篩選，對節點以及邊進行組合用python語言進行處理，然后將各真實網絡以二維圖的形式展示出來.通過對網絡結構圖的觀察，從中提取出了幾個比較典型的網絡模型.然后對以上各指標在各網絡模型中的表現分別進行分析，從而分析各算法的側重點以及優劣.

圖1 真實數據集得到的幾種基本網絡模型Fig.1 Several basic network models from real data sets

如圖1所示一共選取了四個比較典型的局部網絡結構模型，其中實線表示節點之間已經存在的關系，虛線表示各結構中比較常見的預測案例.我們主要分析各算法對虛線連邊的預測準確性.對于一些不規則的網絡結構，我們發現以上算法都未能達到一個較好的預測效果.如第四章中Power數據集代表的美國西部電力網絡，各節點之間沒有很規律的網絡結構.節點之間的連接可能跟人口數量或者地理位置相關，很難在單一的網絡結構中反映出來.

公式(1)-公式(8)提到的各相似度算法主要以鄰居節點數量為依據，即鄰居節點越多那么這兩個節點越相似其連接的可能性就越大.并考慮復雜網絡的弱連接效應，鄰居節點中度數大的節點對相似度的貢獻小于度數小的節點.以圖1(2)為例，節點3，5以及節點9，11之間由于沒有共同鄰居節點，因此以上各公式得出的連接概率都為零.而對于圖1(2)中節點2和3由于擁有較高的鄰居節點數量，導致其連接概率遠遠小于1，3，；1，2節點對的計算結果.對于圖1(4)中1，5節點對之間由于也沒有共同鄰居，因此其計算結果也為零.因此對于以共同鄰居為依據的算法來說，其預測效果主要依賴于網絡中模型(3)所占的比例，即節點的聚類系數比較高時，其預測效果較好.如表2所示在NS網絡中各公式都有較好的預測效果，而在NS網絡中大部分的局部網絡模型也都與圖1(3)類似.對于以(1)(2)(4)占比較高的Router網絡，各算法的預測效果都比較低.同時我們可以看到PA算法在Router網絡的預測效果要明顯好于其他網絡，通過對其網絡結構的分析我們可以看到其大多數的網絡模型為(1)(4).也即在Router網絡中，一個節點更傾向于連接度數大的節點，與節點之間的共同鄰居數量無關.

4 本文提出的新指標算法

由第二章中基本網絡模型的分析，我們可以發現對于基于共同鄰居數量的各相似度指標算法比較適用于圖1中(3)結構模型占比較多的網絡.即網絡的聚類系數越高，那么使用基于共同鄰居數量的相似度指標算法得到的預測效果越好.但是對于像Router、C.elegans那樣的包含圖1中(1)(2)(4)模型較多的網絡，很難達到一個較好的預測效果.針對以上特點以及文章[19]中提到的局部差異度，我們想到了一個基于鄰居節點結構相似度的LSCN指標算法，并且由實驗結果得出其在各個網絡中都能達到一個更好的預測效果.

4.1 LSCN指標

LSCN(Local Structure-Common neighbors)指標的思想即為：一個節點與另一個節點的連接概率，等比于此節點與另一個節點的所有鄰居節點的結構相似度.其中結構相似度可以定義為：

(11)

上式中Γ(x)表示節點x的鄰居節點集合；D(x)表示節點x的度數即鄰居節點數量；|D(x)-D(y)|+1則表示節點x和節點y之間鄰居節點數量的差異，為了避免數量相等結果為零導致計算結果不正確，我們將其絕對值進行加一處理.以上公式即表示兩個節點之間，度數越接近差值越少并且共同鄰居數量越多，那么這兩個節點的結構就越相似.由結構相似度的公式我們將LSCN指標定義為：

(12)

由表2中的實驗結果可以看出，與其他相似度指標相比LSCN指標得到的預測效果在多個數據集中都有所提高.

4.2 LSCN-Ⅱ指標

由2.5節中的LP指標啟發，我們想到了鄰居節點的二階路徑，即對LSCN指標進行擴展進一步考慮鄰居節點的下一級鄰居的結構相似度.從而提出了LSCN-Ⅱ指標：

(13)

上式中的Sxy即為公式12計算得出的節點x，y之間的LSCN指標.α表示二階鄰居節點結構相似度所占的重要性，當α為0時即表示LSCN指標.

圖2 不同網絡中AUC預測結果隨α變化圖Fig.2 AUC predicted results with the change of α in different networks

我們對α分別取0到1之間的不同值，然后通過實驗結果觀察期最終預測效果，從而選取最佳α值使得不同網絡中LSCN-Ⅱ指標可以達到最佳的預測效果.并且由表2可以看到，通過選取最佳的α值與LSCN指標相比，使得預測效果得到進一步提升.并且與其他相似度指標相比，最終其在Power、Router網絡中預測效果提升顯著.圖2為在當α取不同值時在不同網絡中根據LSCN-Ⅱ指標計算出的AUC預測結果.

表1 不同網絡中的最佳α取值Table 1 Best α value in different networks

表1為LSCN-Ⅱ指標下在不同網絡中的最佳α取值，α為0時即表示LSCN指標取得最佳結果：

5 實驗及結果

本文所涉及的實驗數據都來源于真實網絡，讀者可以到網站上進行下載*http://www.linkprediction.org/index.php/link/resource/data..其中Power表示美國西部電力網絡，節點代表變電站，邊則代表連接變電站之間的高壓線，共有6594條邊和4941個節點；Router表示的是路由器網絡，邊代表不同路由器之間有連線，共有6258條邊和5022個節點；email表示某一電子郵件網絡，邊代表不同個人之間有郵件往來，共有32709條邊和1133個節點；C.elegans表示線蟲神經網絡，節點代表線蟲的神經元突觸，邊則表示神經元突觸之間有鏈接，共有2148條邊和297個節點；Yeast表示某一蛋白質相互作用網絡，節點代表的就是蛋白質，邊則表示連接的兩個蛋白質之間有相互作用關系，共有11855條邊和2617個節點；PB表示政治家博客網絡，節點代表不同政客的博客地址，邊則表示這些網頁之間存在相互連接，共有19022條邊和1224個節點；USAir表示美國航空交通網絡，網絡中的不同節點代表不同的機場，邊表示機場之間有直飛航線，共2126條邊以及332個節點；NS表示科學家之間的相互合作網絡，節點代表不同的科學家，邊則表示不同的科學家之間存在合作關系，共有8226條邊以及1589個節點.

5.1 評價指標

衡量鏈路預測算法好壞的主要指標有AUC[19]、精確度和排序分，他們分別以不同的方法對各算法的預測效果進行計算.精確度指標首先取出測試集中，依據不同算法計算得到的，分數最靠前的L個連邊，然后找出這L個連邊實際存在的概率.排序分則是考慮，測試集中正確邊的得分在所有排列中的位置.AUC是應用最廣泛的一種衡量鏈路預測結果的方法，它在考慮測試集中所有已存在邊的得分順序同時，同樣考慮到了不存在邊的得分順序.根據所有已存在邊的得分順序與不存在邊的差距來判斷算法的好壞.如果所有已存在邊的得分越靠前，并且與不存在邊的排列順序越遠，說明算法的預測效果越好.在實際應用中，特別是當樣本非常多時，我們可以通過抽樣的方法來獲取結果的近似值.即每次隨機的從測試集中隨機的選取一條邊，然后再從不存在邊集合中隨機選取一條邊.如果測試集中邊的預測分數值大于不存在邊的預測分數值則加1，如果相等則加0.5.最終在n次獨立的比較后n′就意味著，測試集中存在邊的分數值大于不存在的邊的分數值的次數，n″表示雙方相等的次數.那么預測精度AUC就可以表示為：

表2 不同相似度指標下的AUC預測結果Table 2 AUC results for different similarity indexes

(14)

5.2 實驗結果

我們將不同的實驗數據集隨機分成兩部分，其中90%為訓練集，10%為測試集.然后在訓練集中根據各算法去計算不同節點之間的相似度得到所有節點間的相似度矩陣.然后拿相似度矩陣在測試集計算存在邊和不存在邊的連接概率，最后根據AUC公式去計算預測準確度.不斷重復以上步驟，依據平均結果去比較不同算法的預測效果.

實驗結果：

從表2中我們可以看出：與僅考慮鄰居數量的CN指標，或者考慮鄰節點數量及鄰居節點度數的AA、RA指標相比本文提出的LSCN指標算法，在考慮共同鄰節節點的基礎上通過節點之間的鄰居節點結構相似度，其得出的預測效果在多個真實網絡中都有不同程度的提高.并且通過進一步考慮二階鄰節點結構相似度我們可以看出在Power網絡中的預測效果明顯提升不少，并且通過選取最佳的α值使得算法的預測效果在不同網絡中進一步有所提升.

6 總結與展望

僅考慮鄰居節點數量及度數的指標在計算相似性的鏈路預測中雖然不能起到最好的預測效果，但是由于其計算復雜度低計算所需要的資源較少，因此在許多方面都得到了應用.本文選取8個真實的網絡數據集然后對其進行網絡化，從中提取出了4個比較典型的基本網絡模型數據.然后對各相似度算法在不同網絡模型中的表現進行分析，比較各相似度算法在不同網絡模型下的預測效果.然后在共同鄰居的基礎上提出了一個新的基于鄰居節點相似度的LSCN指標算法，由實驗結果我們可以看出其在多個不同網絡中的預測效果得到很大提升.同時我們對LSCN指標進行改進，進一步提出了基于二階鄰節點結構相似度的LSCN-Ⅱ指標.通過對不同的網絡數據集選取最佳α參數，從而使得最終結果與LSCN指標相比得到進一步提升.

但是僅考慮鄰居節點的相似度指標在鏈路預測中必定有一定的局限性，雖然計算復雜度低但是在預測準確度上不能有很大提高.并且通過第二章的介紹我們可以看出，各算法的預測效果很大程度上依賴于不同網絡模型在真實網絡中所占的比例.因此下一步我們希望通過進一步區分不同節點所屬的網絡模型，以及結合現在比較熱門的有向加權網絡結構特征，使得算法的預測效果得到進一步提升.

[1] Lv Lin-yuan.Link prediction on complex networks[J].Journal of University of Electronic Science and Technology of China，2010，39(5)：651-660.

[2] Xiao Han，Wang Le-ye，Son N.Han.Link prediction for new users in social networks[C].Proceeding of 2015 IEEE International Conference on Communications (ICC 2015)，London，2015：1250-1255.

[3] Lv L，Zhou T.Link prediction in complex networks：a survey[J].Physica A：Statistical Mechanics and its Applications，2011，390(6)：1150-1170 .

[4] Brin S，Page L.The anatomy of a large-scale hypertextual web search engine[J].Computer Networks and ISDN Systems，1998，30(1)：107-117.

[5] Saruukkai B R.Link prediction and path analysis using markov chains[J].Computer Networks，2010，33(1-6)：377-386.

[6] Liu Z，Zhang Q M，Lv L，et al.Link prediction in complex networks a local naive Bayes model[J].Europhysics Letters，2011，96(4)：48007-48012.

[7] Sharma D，Sharma U.Link prediction algorithm for coauthorship networks using neural network[C].Proceeding of the 3rd International Conference on Reliability，Infocom Technologies and Optimization (ICRITO 2014)，Noida：2014，1-4.

[8] Clauset A，Moore C，Newman M E J.Hierarchical structure and the prediction of missing links in networks[J].Nature，2008，80(4)：98-101.

[9] Shang M S，Lv L，Zhang Y C，et al.Empirical analysis of web-based user-object bipartite networks[J].Europhysics Letters，2010，90(4)：1303-1324.

[10] Zhang Yang-fu.Link prediction in directed and weighted networks[D].Xiangtan：Xiangtan University，2011.

[11] Salton G，Mcgill M J.Introduction to modern information retrieval[J].Auckland：MuGraw-Hill，1983，41(4)：305-306.

[12] Leicht E A，Holme P，Newman M E.Vertex similarity in network[J].Physical Review E Statistical Nonlinear and Soft Matter Physics，2006，73(2)：026120-026129.

[13] Sorensen T A.A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons[J].Biol Skr，1948，5(4)：1-34 .

[14] Ravasz E，Somera A L，Mongru D A，et al.Hierarchical organization of modularity in metabolic networks[J].Science，2002，297(5586)：1551-1555.

[15] Zhou T，Lv L，Zhang Y C.Predicting missing links via local information[J].The European Physical Journal B- Condensed Matter and Complex Systems，2009，71(4)：623-630.

[16] Adamic L A，Adar E.Freiends and neighbors on the web[J].Social Networks，2003，25(3)：211-230.

[17] Barabási A L，Albert R.Emergence of scaling in random networks[J].Science，1999，286(5439)：509-512.

[18] Lv L，Jin C H，Zhou T.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics，2009，80(2)：593-598.

[19] Liu Da-wei，Lv Yuan-na，Yu Zhi-hua.An improved link prediction algorithm for complex networks[J].Journal of Chinese Computer Systems，2016，37(5)：1071-1074.

[20] Hanley J A，McNeil B J.A method of comparing the areas under receiver operating characteristic curves derived from the same cases[J].Radiology，1983，148(3)：839-843.

附中文參考文獻：

[1] 呂琳媛.復雜網絡鏈路預測[J].電子科技大學學報，2010，39(5)：651-660.

[10] 張揚夫.有向與加權網絡的鏈路預測[D].湘潭：湘潭大學，2011.

[19] 劉大偉，呂元娜，余智華.一種改進的復雜網絡鏈路預測算法[J].小型微型計算機系統，2016，37(5)：1071-1074.