鏈路預測方法與網絡結構的相關性

李旗旗，徐 敏

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 211106)

鏈路預測方法與網絡結構的相關性

李旗旗，徐 敏

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 211106)

作為數據挖掘的一個分支，鏈路預測經過多年研究，已經提出了多種鏈路預測方法。基于網絡結構的鏈路預測方法因為在相似結構的網絡中具有普適性，在近年來得到了廣泛關注。然而，由于每個復雜網絡的結構不同，鏈路預測方法的預測準確度差別較大，同一種鏈路預測方法不可能在所有網絡中都獲得理想的預測效果。研究鏈路預測方法的準確度和網絡結構的相關性可以在已知一個復雜網絡結構的情況下，選擇合適的鏈路預測方法，也可以為鏈路預測的改進提供理論依據。通過實驗計算出常見鏈路預測方法在每個網絡上的預測準確度，發現鏈路預測方法的預測準確度在不同結構的網絡中是不同的，結合網絡的結構對實驗結果進行分析，并據此提出了一種簡單的鏈路預測方法選擇方案。

復雜網絡；鏈路預測；網絡結構；相似性

0 引 言

自然界中大量的復雜系統都可以通過各種各樣的網絡表現出來。一個典型的網絡包含了一定數量的節點和連接這些節點的邊，其中節點表示的是一個真實系統中的個體，而邊則代表了個體之間的某種關系。如果兩個個體中存在某種關系，那么對應的兩個節點之間就存在一條連邊。

今天，在生活中存在各種各樣的復雜網絡，比如社交網絡、生物網絡、技術網絡等，每一個網絡都有自己獨特的網絡結構和屬性。社交網絡中著名的“六度分離”就是社交網絡的一個獨特網絡結構。通過網絡的結構和屬性，可以嘗試去預測網絡在下一個時間段的變化，從而為實際生產提供正確的指導和建議。鏈路預測就是一個很好的選擇。

復雜網絡中的鏈路預測通過計算網絡中尚未連邊的兩個節點之間在未來產生連邊的概率達到預測的目的[1]。其研究思路和方法主要基于馬爾可夫鏈和機器學習。Sarukkai使用馬爾可夫鏈對網絡進行了鏈路預測和路徑分析[2]。之后學者對基于馬爾可夫鏈的鏈路預測方法進行了擴展，但是在這其中的很多方法都用到了網絡的節點信息。不少研究表明，使用節點信息進行鏈路預測可以獲得比較好的結果[3]，但是現實中很多網絡都難以獲得節點信息，而且即使獲得了節點信息，也不能保證信息的可靠性。因此，國內外學者越來越關注基于網絡結構的鏈路預測方法[4]。相比節點屬性信息，網絡的結構更加可靠。然而，鏈路預測方法在某種程度上都有自己的局限性，并不能在所有網絡上都有很好的預測準確度，所以對于一個已知網絡，如何尋找到一個合適的鏈路預測方法是很重要的。

1 鏈路預測方法

用G(V,E)表示一個無向網絡，其中V表示節點集，E表示邊集。G[t,t1]表示G在[t,t1]時間段的情況，那么在(t1,t2]時間段G的情況就是G(t1,t2]。鏈路預測關注的就是如何預測網絡G從[t,t1]到(t1,t2]的變化。

鏈路預測經過多年的研究，提出了各種各樣的方法。選擇其中常用的10種方法，為了能更好地介紹這些方法，首先介紹一些在文章中使用的符號。其中，x,y表示節點，N表示網絡中節點的數量。kx和ky表示節點x和y的度數，Γ(x)和Γ(y)分別表示節點x和y的鄰居節點集合。

基于局部信息的相似性方法是指僅通過節點的局部信息(如節點的度和最近鄰等)就可以計算出相似度的方法。這種方法的優勢在于時間復雜度低，適用于大型的網絡應用。

1.1 共同鄰居(CN)

共同鄰居是一種比較簡單的鏈路預測方法，其基本假設為：如果兩個尚未連邊的節點有更多的共同鄰居，那么它們更傾向于連邊。這種假設很容易理解，比如在社交網絡中，如果兩個陌生人有很多共同的朋友，那么他們將來成為朋友的概率也很大[5]。又比如，Newman等發現在科學家合作網絡中，如果兩個科學家的共同合作伙伴很多，那么他們將來也很有可能會合作[6]。其定義為：

sxy=Γ(x)∩Γ(y)

(1)

1.2 Salton

該方法是基于CN方法并且考慮連邊兩個端點節點度的影響[7]。它的定義為：

(2)

1.3 Jaccard

100多年前被提出，用于計算集合的相似度[8]。它的定義為：

(3)

1.4 大度節點有利(Hub Promoted Index,HPI)

HPI方法[9]的定義為：

(4)

由于分母只有度比較小的節點決定，所以度比較大的節點更容易和其他節點形成較高的相似性。

1.5 大度節點不利(Hub Depressed Index,HDI)

其定義與HPI相似，只是分母取節點度數的較大值[10]。

(5)

1.6 Adamic-Adar(AA)

其思想是度小的共同鄰居節點的貢獻大于度大的共同鄰居節點[11]。例如，在微博網絡中，受關注較多的人往往是某個領域的專家或者名人，因此共同關注他們的人之間可能并不擁有特別相似的興趣。相反，如果兩個人共同關注了一個粉絲很少的人(非專家)，那么說明這兩個人確實具有相同的興趣愛好或者重疊的社交圈，因此有更高概率相連。

(6)

1.7 Resource-Allocation(RA)

考慮網絡中沒有直接相連的兩個節點x和y，從x可以傳遞一些資源到y，而在此過程中，它們的共同鄰居就成為傳遞的媒介[12]。

假設每個媒介都有一個單位的資源并且平均分配傳給它的鄰居，則y可以接收到的資源就可以定義為節點x和y的相似度，即:

(7)

當網絡的平均度較小時，RA和AA區別不大；但是當平均度較大時，就有很大區別了。

1.8 局部路徑(Local Path,LP)

LP方法在CN方法的基礎上考慮了三階路徑的影響，其定義為：

(8)

1.9 Katz

Katz方法考慮了網絡的所有路徑[13]，其定義為：

(9)

其中，β用來調節高階路徑的貢獻。當β值很小時，高階路徑的貢獻也就很小了，此時Katz的預測結果接近于局部路徑方法。

2 實驗數據與評價方法

為了比較每一種方法的準確度，實驗中選取了7組提取自真實網絡的數據集，實驗結果通過AUC值進行評價。

2.1 數據集

USAir：網絡中的每個節點對應一個機場，如果在兩個機場之間存在一條直達航線，那么兩個機場之間存在一條連邊。

NS：這個網絡是由M.Newman在2006年收集的，其中包含了在網絡科學領域的科學家發表的論文。網絡中的節點表示科學家，兩個節點之間存在連邊說明兩個科學家合作發表過論文。

Power：美國西部電網，是由Watts和Strogatz收集的。節點表示變電站或者換流站，連邊表示它們之間有高壓線。

Router：Internet路由層次網絡，每個節點表示一個路由器，如果兩個路由器之間可以直接進行數據包交換，則它們之間存在一條連邊。

Yeast：蛋白質相互作用網絡，節點表示蛋白質，邊表示它們之間的相互作用。

Wiki-vote：維基百科中的活躍用戶可以被提名為管理員，當一個用戶被提名時，維基百科會組織選舉，獲得支持最多的用戶晉升為管理員。用戶表示節點，選舉行為對應于網絡中的邊，如果用戶A給用戶B投票，那么就有一條邊從A指向B。

Facebook：Facebook數據集是通過其應用從調查的參與者中收集到的，節點表示用戶，邊表示兩個用戶之間的好友關系。

2.2 評價方法

一個時間序列中的預測意味著要將數據集按照時間戳分為訓練集和測試集，其中訓練集視為已知的信息，測試集視為未知信息，這個集合中的所有信息都不能被用來預測[14]。為了保證在抽樣后訓練集仍然保持連通，實驗中采用的劃分策略是，在隨機抽樣的基礎上加入網絡連通性判斷機制，即首先在給定的網絡中選取一條邊，然后判斷這條邊的兩個節點在刪除這條邊之后是否仍然可以連通，如果可以則將該邊加入測試集，否則放棄，然后重新隨機抽取一條邊。

使用AUC來衡量鏈路預測方法的準確度。AUC是指ROC曲線下的面積，在信號探測理論中，ROC曲線用來評價某種分類器的分類效果[15]。這種方法同樣可以用來衡量鏈路預測方法的準確度。

對所有未觀察到的連邊進行排名，AUC的值可以理解為：在測試集中隨機選擇一條連邊的得分高于隨機選擇的一條不存在的邊的概率。在算法的實現中，通常是計算每個未觀察到的連邊的得分，而不是給出一個有序的列表，因為后者需要更大的時間復雜度。然后，每次從測試集中隨機選取一條連邊，再隨機從不存在的連邊中選取一條連邊，比較它們的得分。如果在n次實驗中，有n'次前者的分數更高，n''次兩者分數相同，那么AUC的值為：

(10)

從表達式中可以看出，隨機選擇法的AUC值約為0.5，所以一個鏈路預測算法的AUC值大于0.5的程度就是該算法比隨機算法精確的程度。在實驗中，為了減少隨機抽樣對結果的影響，AUC的計算采取多次計算求平均值的方法。

3 實驗結果與分析

實驗中計算了每個鏈路預測方法在所有7個網絡數據集上的預測準確度，結果顯示為AUC值。表1是每種鏈路預測方法的準確度。

表1 鏈路預測方法的準確度(AUC值)

可以看出，10種鏈路預測方法基本上都給出了好于隨機選擇方法的預測效果，并且基于共同鄰居的方法(CN、Salton、Jaccard、HPI、HDI、AA、RA)預測準確度相差不多，在CN基礎上考慮連邊的兩個端點度的影響整體表現不如CN，AA和RA方法的準確度相比于其他方法有較小的提升。

但是也可以看出一些特例，比如在Power和Router網絡中，除了Katz，其他方法的預測準確度都比較一般；在Facebook和Wiki-vote網絡中，Katz方法在β=0.01時AUC值很低，在β=0.001時預測效果很好。

針對實驗結果的一些現象，將根據網絡結構分析這些現象的原因。表2是在實驗中使用的網絡的一些結構信息。

表2 網絡結構信息

Salton、Jaccard等方法在USAir和Wiki-vote上的預測效果和CN有比較明顯的差距，可能的原因是這兩個網絡中存在比較明顯的“富人俱樂部現象”，即度數大的節點相對于度數小的節點更容易和其他度數大的節點形成連邊，而Salton等方法懲罰了連邊中兩個端點的度數，在一定程度上對預測結果起到了消極作用。

Power和Router網絡的聚類系數很小，說明節點之間的緊密程度很低，它們的平均度很小也說明了這一點。因此，這兩個網絡中的兩個節點之間的共同鄰居節點個數也很少，無法為這兩個節點是否相似提供足夠的證據，這也就是為什么基于共同鄰居的方法預測結果都不好的原因。基于路徑的預測算法受這個問題的影響較小，可以看到LP和Katz的預測結果都不錯。唯一值得注意的是，LocalP對于Power的預測結果不是很好，這是因為LP只是考慮了三階路徑，而Power網絡不僅稀疏而且直徑很大，僅考慮三階路徑性能提升有限。

Katz由于考慮了全路徑，所以它在所有的網絡上都有比較好的表現，當然這也意味著Katz方法的時間復雜度遠遠高于其他方法。在Wiki-vote和Facebook中，Katz在參數β=0.01時出現了比較明顯的異常情況，這恰好體現了Katz方法的一個明顯問題。根據Katz的公式可以看到，其時間復雜度相當高，這對于稍微大型的網絡都是無法接受的，但是在β小于鄰接矩陣最大特征值的倒數的情況下，Katz的公式可以根據級數收斂轉化為：

S=(I-βA)-1-I

(11)

而矩陣求逆的時間復雜度為O(N3)量級，從而大大減少了時間開支。Facebook和Wiki-vote的鄰接矩陣的最大特征值均小于0.01而大于0.001，而實驗中使用的是轉化之后的公式，因此導致Katz預測結果的異常。

另外，Yeast網絡的聚類系數同樣很小，但是CN、AA等方法也得到了比較不錯的預測效果，可能的原因有兩個：

(1)Yeast和Power、Router相比平均度較大，根據聚類系數的定義，節點的度數會在一定程度上抑制包含該節點的三角形的個數對聚類系數的貢獻。如果一個節點的度很大，即使包含它的三角形個數很多，也會表現出較低的聚類系數；

(2)Yeast網絡中度數較小的節點都有比較大的聚類系數，由于度數較大的節點聚類系數較小，導致整體的聚類系數較小，但是節點對之間有足夠的共同鄰居節點來證明它們之間的相似性。

根據上述分析，對于一個結構已知的網絡，一種簡單的鏈路預測方法推薦方案描述如下：

(1)對于聚類系數和平均度較小的網絡，采用基于路徑的方法，其中Katz方法在大多數情況下獲得了較好的效果。需要注意的是，Katz方法在使用之前要計算β的取值上限，LP方法雖然僅考慮了局部路徑，但是沒有參數的限制。

(2)對于聚類系數和平均度較大的網絡，基于共同鄰居的方法能夠獲得較好的結果，并且在時間復雜度上要優于基于路徑的方法。

(3)在基于共同鄰居的方法中，CN、AA和RA可以作為優先選擇的方法，AA和RA在異配性比較強的網絡中會顯示出比CN更好的預測效果。

4 結束語

文中介紹了10種鏈路預測方法，并且在7個真實網絡中比較了它們的預測準確度。實驗結果表明，對于平均度和聚類系數較小的網絡，基于共同鄰居的方法往往不能給出一個很好的預測效果，但是Katz可以獲得很好的預測準確度。

同時還發現，社交網絡的鄰接矩陣的最大特征值的倒數往往較小。在這種情況下，對Katz方法的參數值的選取有一定限制，此時可以考慮使用基于局部路徑的方法。可以看到，在鏈路預測中，獲得一個網絡的結構對于尋找一個合適的鏈路預測方法很有幫助。

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

[2] Sarukkai R R.Link prediction and path analysis using Markov chains[J].Computer Networks,2000,33(1-6):377-386.

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

[4] 傅穎斌,陳羽中.基于鏈路預測的微博用戶關系分析[J].計算機科學,2014,41(2):201-205.

[5] 丁兆云,賈 焰,周 斌,等.社交網絡影響力研究綜述[J].計算機科學,2014,41(1):48-53.

[6] Newman M E J. Clustering and preferential attachment in growing networks[J].Physical Review E,2001,64(2):025102.

[7] Salton G,Mcgill M J.Introduction to modern information retrieval[M].[s.l.]:McGraw-Hill,1983.

[8] Jaccard P.Etude de la distribution florale dans une portion des Alpes et du Jura[J].Bulletin De La Societe Vaudoise Des Sciences Naturelles,1901,37(142):547-579.

[9] Ravasz E,Somera A L,Mongru D A,et al.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1551.

[10] Zhou T,Lu L,Zhang Y C.Predicting missing links via local information[J].Physics of Condensed Matter,2009,71(4):623-630.

[11] Adamic L A,Adar E.Friends and neighbors on the web[J].Social Networks,2003,25(3):211-230.

[12] Ou Q,Jin Y D,Zhou T,et al.Power-law strength-degree correlation from resource-allocation dynamics on weighted networks[J].Physical Review E,2007,75:021102.

[13] Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.

[14] Lü L,Zhou T.Link prediction in complex networks:a survey[J].Physica A Statistical Mechanics & Its Applications,2011,390(6):1150-1170.

[15] Fawcett T.Introduction to ROC analysis[J].Pattern Recognition Letters,2006,27(8):861-874.

CorrelationbetweenLinkPredictionMethodandNetworkStructure

LI Qi-qi，XU Min

(School of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics,Nanjing 211106，China)

As a branch of data mining,link prediction has been studied many years in the computer field,and a variety of link prediction methods are proposed.The link prediction method based on network structure has been widely concerned in recent years,because it is common in the network with similar structure.However,due to the different structure of complex networks,the prediction accuracy of the link prediction method is different,and the same link prediction method can’t get the desired results in all networks.Analyzing the correlation of network structure and the accuracy of link prediction method can help to choose a right link prediction method for a given network,and provide the theoretical basis for improving link prediction.The prediction accuracy of the link prediction method is calculated by the experiment,and the results show that it exists difference in the different network structure.Analyzing experimental results combined with the network structure,a simple selection of link prediction method is proposed.

complex networks；link prediction；network structure；similarity

TP393

A

1673-629X(2017)12-0057-04

10.3969/j.issn.1673-629X.2017.12.013

2016-12-11

2017-04-19 < class="emphasis_bold">網絡出版時間

時間：2017-08-01

國家“973”重點基礎研究發展計劃項目(2014CB744900)

李旗旗(1991-)，男，碩士研究生，CCF會員(E200041166G)，研究方向為機器學習、鏈路預測；徐 敏，博士，副教授，研究方向為模式識別、機器學習。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1557.078.html