社交網絡中的鏈路預測方法改進

李旗旗，徐 敏

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

社交網絡中的鏈路預測方法改進

李旗旗，徐 敏

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

社交網絡在近些年得到了迅速發展，如今各個行業都在努力加入社交元素，如何提高鏈路預測方法在社交網絡中的預測準確度成為一個熱門研究方向。鏈路預測方法由于網絡結構的不同會表現出不同的預測效果，因此可以根據社交網絡的結構特性對鏈路預測方法進行改進，從而提高在社交網絡中的預測準確度。社交網絡是對人與人之間某種社會關系的描述，因此和其他復雜網絡相比，會表現出獨特的網絡性質和結構，其中最主要的是“小世界”特性和無標度特性。針對社交網絡的這種特性，對原有的鏈路預測方法進行改進，在共同鄰居方法的基礎上加入了優先連接對節點相似性的貢獻。真實社交網絡數據集的對比實驗結果表明，改進后的方法在沒有增加時間復雜度的情況下提高了預測準確度。

社交網絡；鏈路預測；網絡結構；無標度網絡

0 引 言

近年來蓬勃發展的互聯網技術，為社交網絡提供了一個優質的平臺，在線社交網絡應運而生。在線社交網絡不僅繼承了人們在線下的社會關系，而且突破了地區、領域的限制，使得不同的人之間交流更加方便。在線社交網絡出現以來，一直被人們所喜愛，社交網絡的規模也因此越來越大。如今人們對于在線社交網絡的依賴越來越強，同時對社交網絡的要求也越來越高[1]。因此，如果可以根據社交網絡已經存在的信息預測未來可能產生的連邊，從而用來向用戶推薦他們可能感興趣的人，將會是一項非常有價值的工作。

復雜網絡中的鏈路預測通過計算網絡中尚未連邊的兩個節點之間在未來產生連邊的概率達到預測的目的，其研究思路和方法主要基于馬爾可夫鏈和機器學習。Sarukkai使用馬爾可夫鏈對網絡進行了鏈路預測和路徑分析[2]。之后人們在此基礎上進行了擴展，并提出了一系列模型，但是這些模型大多結合了網絡中的節點屬性，然而很多網絡中節點屬性的可靠性并不能得到保證。因此，國內外學者越來越關注基于網絡結構的鏈路預測方法。相比于節點屬性信息，網絡的結構更加可靠，并且基于網絡結構的鏈路預測方法對于結構相似的網絡具有一定的普適性。

Liben-Nowell和Kleinberg[3]提出了基于網絡結構的鏈路預測方法，并在社會合作網絡中分析了一些鏈路預測方法的預測效果。之后，周濤等[4]在6種網絡中對9種鏈路預測方法的效果進行對比，發現同一種方法會隨著網絡結構的變化表現出不同的預測效果，同時也可以根據網絡的某些結構特點對鏈路預測方法進行改進[5]。

隨著社交網絡的快速發展，對社交網絡的研究也逐漸成為一個熱門方向，而如何預測社交網絡中的關系成為社交網絡研究的重要任務。各種社交網絡中的鏈路預測方法因此被提出，如針對微博網絡的鏈路預測研究[6]。社交網絡作為復雜網絡的一種典型表現形式，反映了社會成員之間復雜的社會關系。社交網絡具有復雜網絡的一般特征，又因其連邊存在的社會性，表現出獨特的結構特征[7-8]。根據社交網絡的結構特性對鏈路預測方法進行改進，可以在一定程度上提高鏈路預測方法在社交網絡中的預測效果。

1 鏈路預測方法

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

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

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

1.1共同鄰居(CN)

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

sxy=Γ(x)∩Γ(y)

(1)

在共同鄰居的基礎上，考慮兩個端點的度對節點相似性的影響，又產生了Salton[9]、Jaccard[10]和LNH-I[11]等方法。后來的研究表明，這些更復雜的變體在很多情況下都不如CN方法的預測效果好，所以選取CN作為基于共同鄰居的方法的代表。

1.2Adamic-Adar(AA)

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

(2)

周濤等根據網絡資源分配的啟發，提出了RA方法[4]。該方法和AA唯一不同的是將公共鄰居的權重賦值為度的倒數。

1.3局部路徑(LocalPath,LP)

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

(3)

1.4Katz

Katz方法考慮了兩個節點在網絡中的所有路徑對相似性的貢獻，其定義為[14]：

(4)

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

2 社交網絡的結構特性

2.1“小世界”特性

“小世界”現象最早出現在20世紀60年代Milgram的信件投遞實驗中。Milgram通過實驗發現每封信平均經過6個人就可以到達目標收件人手中，并據此提出了“六度分離”理論[15]。此后，又接連涌現了一些社交網絡上的“小世界”實驗，比較著名的是“Kevin Bacon”游戲，它的主要目的是計算電影演員Bacon與其他電影演員之間的距離。該實驗基于美國Virginia大學的電影演員數據庫，計算得到全世界60萬演員與Bacon的平均距離為2.944。2011年，Facebook網站與米蘭大學等共同進行的六度分離實驗[16]顯示，Facebook上兩個用戶之間的平均距離僅為4.74，實驗采用了包含Facebook中7億多用戶和687億條朋友關系的數據，是自2011為止最大規模的小世界實驗。有研究表明，不同種類的社交網絡都具有“小世界”現象[17]。

“小世界”現象引發人們對如何構造一個小世界網絡模型的思考，比較著名的小世界網絡模型是WS小世界模型[18]和NW小世界模型[19]。兩個網絡都從規則網絡開始。WS小世界模型以概率p進行隨機重連，而NW小世界模型以概率p隨機選擇一定數量的節點對，然后在這些節點對之間添加邊。研究表明，兩個模型都滿足“小世界”網絡的結構特性，但是在可搜索性角度沒有進行考慮。Kleinberg從可搜索性角度對NW小世界模型進行了修改。Kleinberg認為，在兩個節點之間增加連邊不應該是隨機的，而是要隨著兩個節點之間的網格距離的增加來降低產生連邊的概率[20]。Kleinberg模型在滿足“小世界”特性的基礎上增加了網絡的可搜索性，更加符合實際的網絡。

2.2無標度特性

無標度特性指網絡的度分布服從冪律分布，由于這類網絡中節點的度沒有比較明顯的特征長度，因此稱這類網絡為無標度網絡。無標度網路中的度分布為：

P(k)～k-λ

(5)

其中，λ為冪指數，取值通常在2～3之間。

最著名的無標度網絡模型是BA無標度網絡模型[21]。該模型的核心思想在于考慮了網絡的增加和優先連接。網絡的增長指的是節點和連邊的增加，優先連接指的是新加入的節點更容易與度數大的節點相連，也稱為“馬太效應”。

根據對BA無標度網絡模型構造的網絡研究，發現網絡中度為k的節點出現的概率P(k)近似與k-3成正比，滿足冪律分布。正是這個原因，文中認為同樣滿足度分布為冪律分布的社交網絡也存在優先連接的現象。隨后有研究表明，社交網絡確實具有無標度性，即網絡中大度數節點更傾向于與其他大度數節點建立連接，而小度數節點更傾向于與小度數節點相連。

3 鏈路預測方法的改進方案

針對社交網絡中鏈路預測方法的改進主要是基于社交網絡的小世界特性和無標度特性，因此改進方案的核心思想是在兩個節點共同鄰居的基礎上加入對優先連接特性的考慮。在具有無標度特性的網絡中，一個節點x與另一個節點y產生連邊的概率與y的度ky成正比[22]，同理，節點y與節點x產生連邊的概率與x的度kx成正比，因此節點x和節點y產生連邊的概率與kxky的乘積成正比。再根據“小世界”現象中兩個節點之間的連邊概率隨著距離的增加而衰減，需要對kxky設置一個衰減系數α，用于懲罰距離比較大的節點對。由于是在CN的基礎上進行改進，所以將改進的方法命名為ImprovedCN，其定義為：

(6)

4 實 驗

4.1實驗平臺

實驗平臺的硬件信息為：酷睿i5處理器，8 G內存，系統版本為Windows 7。

編程語言為Matlab，編程環境為Matlab2014b。

4.2數據集

實驗選取了5個具有不同功能的社交網絡，包括朋友網絡、信息網絡和通信網絡，介紹如下：

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

Youtube：一個以視頻分享為主的網站，用戶可以在該網站上分享和下載視頻，也可以通過朋友關系組成網絡社區進行互動。網絡節點和連邊分別表示用戶和朋友關系，其中包含8 500個節點和77 007條邊。

Facebook：該網絡包含了Facebook中的朋友列表，是通過其官方應用Facebook.app從調查參與者中收集到的，數據集通過將Facebook內部用戶的id用一個新的值代替對真實網絡進行了匿名化。其中包含4 039個節點和88 234條邊。

Email：數據集來自國外某公司員工的email通信記錄。網絡中每個節點對應一個電子郵箱地址，如果一個地址i發送給地址j至少一封電子郵件，網絡中就會包含一條從i到j的無向邊。不考慮公司內員工與公司外的電子郵箱地址之間的通信，其中包含1 133個節點和10 903條邊。

Gplus：數據集包含Google+中的“圈子”，Google+是Google的一個擴展功能，其中心要點是朋友和熟人組成的“圈子”(Circles)。用戶可以把聯系人按不同的圈子分組，如家庭成員、同事、大學同學等，并在“圈子”里分享照片、視頻及其他資訊。用戶之間的每一次互動都會在兩個用戶對應的節點之間出現一條連邊。其中包含6 600個節點和189 167條邊。

4.3實驗結果與分析

實驗中用4種常用鏈路預測方法和改進的方法ImprovedCN對五個網絡數據集進行了預測，預測準確度使用AUC來衡量。AUC從整體上衡量算法的準確度，它可以理解為測試集中的邊的分數值比隨機選取的一個不存在的邊的分數值高的概率。實驗結果見表1。

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

從表1可以看出，改進后的方法在預測準確度上相比CN有了一定的提高，并且在Wikivote、Facebook、Email和Gplus四個網絡上都優于AA方法，達到了與LP相當的預測水平，在Facebook網絡中雖然預測準確度不如其他四種方法，但仍然取得了比較理想的效果。

從ImprovedCN的表現來看，它在一定程度上彌補了CN、AA方法在聚類系數和平均度都較低的社交網絡中表現不佳的缺陷，使預測準確度不因網絡結構的變化而表現出較大的差別。在CN的基礎上增加優先連接的考慮確實取得了更好的效果。

從時間復雜度來分析，雖然ImproveCN在CN的基礎上加入了節點度的乘積，但是后者可以通過鄰接矩陣的列向量與自身的轉置矩陣相乘計算，而CN的實現是鄰接矩陣自身相乘求得，所以在時間復雜度上相比于CN沒有增加。相比于LP和Katz，在運行時間上有比較明顯的優勢。

5 結束語

研究了社交網絡的結構特性，并根據研究結果對鏈路預測方法進行了改進，在共同鄰居的基礎上考慮了優先連接對節點對的相似性貢獻。通過實驗對比發現，改進方法的預測準確度有了一定的提高，并且在效果上達到了局部路徑方法的水平，而且該方法在時間復雜度上沒有增加，比較適合于如今大型的社交網絡。

[1] 吳信東,李 毅,李 磊.在線社交網絡影響力分析[J].計算機學報,2014(4):735-752.

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

[3] Liben-Nowell D,Kleinberg J.The link-prediction problem for social networks[J].Journal of the American Society for Information Science and Technology,2007,58(7):1019-1031.

[4] Zhou T,Lü L,Zhang Y C.Predicting missing links via local information[J].European Physical Journal B,2009,71(4):623-630.

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

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

[7] 許 進,楊 揚,蔣 飛,等.社交網絡結構特性分析及建模研究進展[J].中國科學院院刊,2015,30(2):216-228.

[8] Lorrain F,White H C.Structural equivalence of individuals in social networks[J].Social Network,1971,1(1):67-98.

[9] Salton G,McGill M J.Inoduction to modern information retrieval[M].Auckland:McGraw-Hill,1983.

[10] Jaccard P.Etude comparative de la distribution florale dans une portion des Alpes et du Jura[J].Bulletin of the Torrey Botanical Club,1901,37:547.

[11] Leicht E A,Holme P,Newman M E.Vertex similarity in networks[J].Physical Review E,2006,73(2):026120.

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

[13] Lü L,Jin C H,Zhou T.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E,2009,80(4):046122.

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

[15] Milgram S.The small world problem[J].Psychology Today,1967,2(1):60-67.

[16] Backstrom L,Boldi P,Rosa M,et al.Four degrees of separation[C]//Proceedings of the 4th annual ACM web science conference.[s.l.]:ACM,2012.

[17] Mislove A,Marcon M,Gummadi K P,et al.Measurement and analysis of online social networks[C]//ACM SIGCOMM conference on internet measurement.San Diego,California,USA:ACM,2007.

[18] Watts D J,Strogatz S H.Collective dynamics of “small-world” networks[J].Nature,1998,393(6684):440-442.

[19] Newman M E J,Was D J.Renormalization group analysis of the small-world network model[J].Physics Letters A,1999,263(4-6):341-346.

[20] Kleinberg J.The small-world phenomenon: an algorithm perspective[C]//Proceedings of ACM symposium on theory of computing.[s.l.]:ACM,2010:163-170.

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

[22] 王 林,商 超.無標度網絡中的鏈路預測問題研究[J].計算機工程,2012,38(3):67-70.

ImprovementofLinkPredictionMethodinSocialNetworks

LI Qi-qi，XU Min

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

The social network has been developing rapidly in recent years.Various industries are now trying to integrate social elements,so how to improve the accuracy of link prediction methods in social networks has become a popular research.Due to the different network structures,the link prediction methods will be different in prediction performance so that it can be improved according to the characteristics of social network structure,improving of the accuracy of prediction.The social network is a description of certain social relations between people,so compared with other complex networks,it will exhibit its unique properties and network structure,of which the most important is the “small world” and scale-free characteristics.According to the characteristics of social network,the previous link prediction methods can be improved,adding the contribution of priority connection based on common neighbors.The experiments on real social network data sets show that the improved method can improve the accuracy of prediction without increasing time complexity.

social networks；link prediction；network structure；scale-free network

2016-12-30

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

時間：2017-08-01

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

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

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

TP393

A

1673-629X(2017)11-0037-04

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