李?yuàn)^華

摘要： 作為復(fù)雜網(wǎng)絡(luò)分析的一項(xiàng)重要任務(wù)，鏈接預(yù)測(cè)已經(jīng)被應(yīng)用到諸多領(lǐng)域，例如：個(gè)性化推薦、決策支持系統(tǒng)和犯罪調(diào)查等。常用的鏈接預(yù)測(cè)方法主要是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法，沒有考慮網(wǎng)絡(luò)的聚類信息因素。實(shí)際上，網(wǎng)絡(luò)的聚類結(jié)果包含了對(duì)鏈接預(yù)測(cè)很重要的信息。在此基礎(chǔ)上，一種基于聚類信息和網(wǎng)絡(luò)特征的鏈接預(yù)測(cè)模型被提出，并在人造和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了驗(yàn)證，具有較好的預(yù)測(cè)效果。

關(guān)鍵詞： 數(shù)據(jù)挖掘；鏈接預(yù)測(cè)；復(fù)雜網(wǎng)絡(luò)；無標(biāo)度；聚類信息

中圖分類號(hào)： TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）18-0032-03

A Novel Link Prediction in Complex Networks

LI Fen-hua

（Department of Computer Science and Technology， Yuncheng University， Yuncheng 044000， China）

Abstract： Link prediction is an important task of complex network analysis， which has been applied in various domains such as personal recommendation systems， decision support systems， crime investigation and so on. The classical link prediction methods are based on network topology structure and its features， in which the clustering information has not been considered. However， the clustering results of a network contain some vital information for link prediction. In this paper， a novel link prediction based on network clustering information and its features is proposed. Through experiments on the synthetic datasets and real world datasets， our proposed method has the good prediction accuracy.

Key words： data mining； link prediction； complex networks； scale free； clustering information

1 引言

現(xiàn)實(shí)世界的很多系統(tǒng)可以用網(wǎng)絡(luò)來描述，在網(wǎng)絡(luò)中節(jié)點(diǎn)表示對(duì)象，鏈接表示對(duì)象間的聯(lián)系[1]。近年來，復(fù)雜網(wǎng)絡(luò)的研究和分析已經(jīng)引起了很多學(xué)者的高度關(guān)注，逐漸成為諸多領(lǐng)域的一個(gè)研究熱點(diǎn)。然而，真實(shí)的復(fù)雜網(wǎng)絡(luò)是動(dòng)態(tài)變化的：隨著時(shí)間的推移，網(wǎng)絡(luò)中的節(jié)點(diǎn)或邊會(huì)快速的增長(zhǎng)和變化。如何能夠準(zhǔn)確地預(yù)測(cè)未來網(wǎng)絡(luò)中出現(xiàn)或消失的邊是一個(gè)既有趣又富有挑戰(zhàn)性的問題，例如：在朋友網(wǎng)絡(luò)中，預(yù)測(cè)未來朋友間可能存在的新關(guān)系并進(jìn)行推薦。上述問題就是所謂的鏈接預(yù)測(cè)問題，已經(jīng)成為很多領(lǐng)域亟待解決的一個(gè)問題。

作為鏈接挖掘的一個(gè)分支，鏈接預(yù)測(cè)是指根據(jù)已知的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)或節(jié)點(diǎn)屬性來預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)中未來存在鏈接的可能性[2，6]。傳統(tǒng)的數(shù)據(jù)挖掘方法無法解決這個(gè)問題，其原因在于：傳統(tǒng)的數(shù)據(jù)挖掘方法假定研究的對(duì)象實(shí)體之間是相互獨(dú)立的，不考慮對(duì)象實(shí)體之間的關(guān)系?，F(xiàn)有的鏈接預(yù)測(cè)方法主要是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法，沒有考慮復(fù)雜網(wǎng)絡(luò)聚類信息在預(yù)測(cè)中的作用[2]。實(shí)際上，復(fù)雜網(wǎng)絡(luò)的聚類結(jié)果中包含了很多對(duì)鏈接預(yù)測(cè)有用的信息，而這些信息對(duì)鏈接預(yù)測(cè)的效果能夠起到很好的輔助作用，這一點(diǎn)已經(jīng)被很多文獻(xiàn)所證明：馮旭等人通過在人造和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)，初步揭示了網(wǎng)絡(luò)的聚類信息對(duì)鏈接預(yù)測(cè)性能的提升有較好的輔助作用[3]；Soundarajan等人也通過實(shí)驗(yàn)證明了網(wǎng)絡(luò)聚類信息在鏈接預(yù)測(cè)中的重要性[4]。針對(duì)上述問題，結(jié)合大多數(shù)復(fù)雜網(wǎng)絡(luò)具有的無標(biāo)度特性，本文提出了一種基于聚類信息和網(wǎng)絡(luò)特征的鏈接預(yù)測(cè)方法，通過后續(xù)實(shí)驗(yàn)表明，該方法具有較好的鏈接預(yù)測(cè)效果。

2常用鏈接預(yù)測(cè)方法及其評(píng)估標(biāo)準(zhǔn)

2.1 常用鏈接預(yù)測(cè)方法

現(xiàn)有的鏈接預(yù)測(cè)方法主要分為如下三類[5]：

1）基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法：該類方法主要是根據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)信息來進(jìn)行鏈接預(yù)測(cè)。基于局部結(jié)構(gòu)信息的方法雖然計(jì)算復(fù)雜度低，但是它的預(yù)測(cè)精度低；基于全局結(jié)構(gòu)信息的方法雖然預(yù)測(cè)精度高，但是它的計(jì)算復(fù)雜度高[7，8]。

2）基于最大似然估計(jì)的方法：該類方法利用預(yù)先設(shè)定的一些規(guī)則和能夠使得已知網(wǎng)絡(luò)結(jié)構(gòu)的似然估計(jì)最大化的參數(shù)來進(jìn)行鏈接預(yù)測(cè)。雖然預(yù)測(cè)精度高，但是計(jì)算復(fù)雜度太高，不適合大規(guī)模的復(fù)雜網(wǎng)絡(luò)分析[9]。

3）基于機(jī)器學(xué)習(xí)的方法：該類方法首先提取已知網(wǎng)絡(luò)結(jié)構(gòu)中有用信息，然后利用機(jī)器學(xué)習(xí)的方法構(gòu)建學(xué)習(xí)模型來進(jìn)行鏈接預(yù)測(cè)。同樣，該方法雖然預(yù)測(cè)精度高，但是計(jì)算復(fù)雜度太高，不適合大規(guī)模的復(fù)雜網(wǎng)絡(luò)預(yù)測(cè)[10]。

2.2 預(yù)測(cè)精度評(píng)估標(biāo)準(zhǔn)

通常情況下，鏈接預(yù)測(cè)精度的評(píng)估指標(biāo)主要有下列2個(gè)：AUC和Precision[5]。

1） AUC （Area under the receiver operating characteristic curve）：該指標(biāo)從整體上來衡量一個(gè)算法的鏈接預(yù)測(cè)精度。如果AUC的值越大，那么說明預(yù)測(cè)算法的預(yù)測(cè)精度越高。假設(shè)每次從測(cè)試集中隨機(jī)選擇一條邊，用該邊的分值與不存在邊的分值做比較，S表示比較的總次數(shù)，M表示測(cè)試集中邊比不存在邊分值大的比較次數(shù)，L表示測(cè)試集中邊與不存在邊分值相等的比較次數(shù)，該評(píng)估指標(biāo)的計(jì)算公式如下：

2） Precision：該指標(biāo)從局部角度衡量一個(gè)算法的鏈接預(yù)測(cè)精度。假設(shè)在按照所有未知邊分值逆序排列的前S條邊中包含G條測(cè)試集中的邊，那么，該指標(biāo)的計(jì)算公式如下：

3 基于聚類信息和網(wǎng)絡(luò)特征的方法

針對(duì)傳統(tǒng)數(shù)據(jù)挖掘技術(shù)存在的問題，根據(jù)復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性和網(wǎng)絡(luò)的聚類信息，本文提出了一種融合網(wǎng)絡(luò)聚類信息和無標(biāo)度特性的鏈接預(yù)測(cè)方法。該方法的總體思想如下：首先，定義了一種融合網(wǎng)絡(luò)聚類信息及其無標(biāo)度特性的節(jié)點(diǎn)相似性度量新指標(biāo)，然后，利用Newman快速算法獲取復(fù)雜網(wǎng)絡(luò)的最佳聚類結(jié)構(gòu)[6，11-13]，在此基礎(chǔ)上，通過已定義的節(jié)點(diǎn)相似性度量新指標(biāo)進(jìn)行鏈接預(yù)測(cè)。

假設(shè)復(fù)雜網(wǎng)絡(luò)可以用圖G= （N， L）表示，在這里 N、 L分別表示網(wǎng)絡(luò)G中節(jié)點(diǎn)的集合和邊的集合； e=（x， y） ∈L 表示節(jié)點(diǎn)x 和y之間存在的關(guān)系；N（x）、CN（x， y） 分別表示節(jié)點(diǎn)x 的鄰居集合和節(jié)點(diǎn)對(duì)（x， y） 共同鄰居的集合。如果與節(jié)點(diǎn)對(duì)（x， y） 屬于同一社團(tuán)的共同鄰居的數(shù)量在該節(jié)點(diǎn)對(duì)共同鄰居集合中占的比重越大，那么節(jié)點(diǎn)對(duì)（x， y）之間存在鏈接的可能性就越大?；谏鲜黾僭O(shè)，在我們的方法中，網(wǎng)絡(luò)的聚類信息定義如下：

其中，表示與節(jié)點(diǎn)對(duì)（x， y） 屬于同一社區(qū)的共同鄰居的集合。僅依靠網(wǎng)絡(luò)的聚類信息提高預(yù)測(cè)的精度還不夠，在我們的方法中還融入了絕大多數(shù)網(wǎng)絡(luò)具有的無標(biāo)度特性，其定義如公式（4）所示：

其中，、分別表示節(jié)點(diǎn)和節(jié)點(diǎn)的度值，表示網(wǎng)絡(luò)G中的任一節(jié)點(diǎn)。根據(jù)公式（3）和（4），我們定義節(jié)點(diǎn)對(duì)（x， y） 的相似性度量新指標(biāo)如下：

其中，，是可調(diào)參數(shù)，它調(diào)節(jié)聚類信息和網(wǎng)絡(luò)特征信息在相似性度量中所占的比重。

基于聚類信息和網(wǎng)絡(luò)特征新方法的具體算法描述如算法1所示：

3）[Q， Cluster] = FastNewman（Trainset）； //采用Newman快速算法進(jìn)行網(wǎng)絡(luò)聚類。

4）Bestcluster = ChooseBestCluster（Q， Cluster）； //選擇當(dāng)Q最大時(shí)最佳的網(wǎng)絡(luò)聚類結(jié)果。

5）根據(jù)公式（5）和參數(shù)，計(jì)算訓(xùn)練集網(wǎng)絡(luò)中每個(gè)未連接節(jié)點(diǎn)對(duì)的相似性度值；

6）根據(jù)測(cè)試集Testset和第5）步獲得的所有的值，計(jì)算網(wǎng)絡(luò)的預(yù)測(cè)精度值A(chǔ)UC；

7）Return AUC； ]

上述算法1主要依賴4個(gè)基本操作：1、3、5和6，所以該算法的時(shí)間復(fù)雜度為，適合大規(guī)模復(fù)雜網(wǎng)絡(luò)分析。

4 實(shí)驗(yàn)分析

本節(jié)將針對(duì)BCFLP算法進(jìn)行實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)分析。

4.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

1） 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)的實(shí)驗(yàn)平臺(tái)采用的是一臺(tái)聯(lián)想Thinkpad T450筆記本電腦，該筆記本電腦的處理器為Intel（R） Core i5@ 2.2GHz、操作系統(tǒng)為64位的Windows 8、內(nèi)存為8.00GB，算法程序采用Matlab 2012a語言實(shí)現(xiàn)。

2） 實(shí)驗(yàn)數(shù)據(jù)集

本實(shí)驗(yàn)數(shù)據(jù)集分為兩類：人造數(shù)據(jù)集和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集。人造數(shù)據(jù)集由2個(gè)由BA模型生成的人造網(wǎng)絡(luò)BA（N， m）組成[14]，其中，N、m分別表示網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)和每加入一個(gè)新節(jié)點(diǎn)需要連接的邊數(shù)，具體的網(wǎng)絡(luò)拓?fù)涮匦匀绫?所示。

在表1中， 表示網(wǎng)絡(luò)的平均度，C 表示網(wǎng)絡(luò)的聚類系數(shù)，APL表示網(wǎng)絡(luò)的平均路徑長(zhǎng)度。

真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集如表2所示，其中，Karate表示由作者Wayne Zachary收集的一個(gè)美國(guó)大學(xué)karate俱樂部34個(gè)成員之間相互聯(lián)系的復(fù)雜網(wǎng)絡(luò)[15]；UST表示一個(gè)美國(guó)航空交通網(wǎng)絡(luò)[16]；PB表示一個(gè)美國(guó)政治博客復(fù)雜網(wǎng)路，原始網(wǎng)絡(luò)中邊的有向性和自連接性被忽略。上述這些真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集均可以從斯坦福大學(xué)官網(wǎng)獲得[17]。

4.2 實(shí)驗(yàn)結(jié)果及其分析

在實(shí)驗(yàn)中，我們把初始網(wǎng)絡(luò)隨機(jī)地劃分為訓(xùn)練集和測(cè)試集兩部分。其中，訓(xùn)練集包含初始網(wǎng)絡(luò)90%的邊，測(cè)試集包含初始網(wǎng)絡(luò)剩余90%的邊。為了驗(yàn)證新方法的預(yù)測(cè)精度，我們與下列典型的預(yù)測(cè)算法做了比較：CN、AA、RA、PA和Katz [2]。圖1描述了我們的新方法BCFLP與上述方法在人造數(shù)據(jù)集上的預(yù)測(cè)精度比較結(jié)果，其中，算法的參數(shù)θ=0.4，Katz方法的參數(shù)β=0.0005。類似，圖2描述了BCFLP方法與其他方法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的預(yù)測(cè)精度比較結(jié)果，其中，算法的參數(shù)θ=0.9，Katz方法的參數(shù)β=0.000。

從圖1中，我們有如下發(fā)現(xiàn)： 1）與其他方法相比，BCFLP方法在人造網(wǎng)絡(luò)數(shù)據(jù)集上具有最佳的鏈接預(yù)測(cè)精度。2）隨著網(wǎng)絡(luò)的聚類系數(shù)增加，上述這些方法的預(yù)測(cè)精度都得到了明顯的提升。3） 除了BCFLP方法之外，CN、AA、RA和PA方法也有不錯(cuò)的鏈接預(yù)測(cè)性能。為了進(jìn)一步驗(yàn)證BCFLP方法的預(yù)測(cè)性能，我們?cè)谡鎸?shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，如圖2所示，通過對(duì)實(shí)驗(yàn)結(jié)果分析，我們獲得了與圖1相同的結(jié)論。從上述分析表明，與現(xiàn)有典型的鏈接預(yù)測(cè)方法相比，我們的新方法BCFLP在鏈接預(yù)測(cè)性能方面具有明顯的優(yōu)勢(shì)，同時(shí)也進(jìn)一步驗(yàn)證了網(wǎng)絡(luò)的聚類信息對(duì)鏈接預(yù)測(cè)的重要作用。從計(jì)算復(fù)雜度和預(yù)測(cè)精度兩方面考慮，我們的新方法適合對(duì)規(guī)模較大的復(fù)雜網(wǎng)絡(luò)的分析。

5 結(jié)束語

為了獲得較高的鏈接預(yù)測(cè)精度，本文提出了一種簡(jiǎn)單而有效的復(fù)雜網(wǎng)絡(luò)鏈接預(yù)測(cè)方法，該方法在網(wǎng)絡(luò)無標(biāo)度特性的基礎(chǔ)上融入了網(wǎng)絡(luò)的聚類信息。在人造和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)表明：與其他預(yù)測(cè)方法相比，該方法具有較高的鏈接預(yù)測(cè)精度。

在未來的研究中，一方面，我們需要對(duì)更多的其他網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行測(cè)試。另一方面，我們把網(wǎng)絡(luò)節(jié)點(diǎn)的語義或內(nèi)容信息融入到我們的方法中，來進(jìn)一步提高我們方法的鏈接預(yù)測(cè)精度。

參考文獻(xiàn)：

[1]L. Getoor， C. P. Diehl. Link mining： a survey [J]. ACM SIGKDD Explorations Newsletter， 2005， 7（2）： 3-12.

[2]Liben-Nowell， J.Kleinberg. The link prediction problem for social networks[J]. Journal of the American society for information science and technology， 2007， 58 （7）： 1019-1031.

[3]Feng X.，Zhao J.，Xu K. Link prediction in complex networks： a clustering perspective[J]. the European Physical Journal B， 2012， 85： 1-9.

[4]Soundarajan S.，Hopcroft J.Using community information to improve the precision of link prediction methods[J]. in Proceedings of the 21st International Conference Companion on World Wide Web， 2012： 607-608.

[5]呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè) [J]. 電子科技大學(xué)學(xué)報(bào)， 2010， 39（5）： 651-661.

[6]Clauset A.， Newman M. E.，Moore C. Finding community structure in very large networks[J]. Physical Review E， 2004， 70（6）： 066111.

[7]Getoor L. Link mining： a new data mining challenge[J]. ACM SIGKDD Explorations Newsletter，2003（5）： 84-89.

[8]ieter B. T. M.-F. W.，Koller A. D. Link prediction in relational data[J].Learning Statistical Patterns in Relational Data Using Probabilistic Relational Models， 7， 2005.

[9]Liu W.，Lü L. Link prediction based on local random walk [J]. EPL （Europhysics Letters）， 2010， 89.

[10]Zhou T.，Lü L.，Zhang Y.-C. Predicting missing links via local information[J]. the European Physical Journal B， 2009， 71： 623-630.

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

[12]Guimerà R.，Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks[C]. Proceedings of the National Academy of Sciences， 2009， 106： 22073-22078.

[13]O'Madadhain J.，Hutchins J.，Smyth P. Prediction and ranking algorithms for event-based network data[J]. ACM SIGKDD Explorations Newsletter，2005，7： 23-30.

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

[15]Zachary W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research， 33： 452-473， 1977.

[16]Batagelj V.，Mrvar A. Pajek datasets [DB]. 2007.

[17]Ackland R. Mapping the US political blogosphere [EB]. Presentation to Blog Talk Downunder， 2005.