安琛，陳陽

南京郵電大學計算機學院，南京210046

基于集成學習的動態(tài)鏈接預測方法

安琛，陳陽

南京郵電大學計算機學院，南京210046

CNKI網(wǎng)絡出版：2017-03-04,http://kns.cnki.net/kcms/detail/11.2127.TP.20170304.1727.002.html

1 引言

隨著Web2.0的發(fā)展以及用戶生成內(nèi)容（User Generated Content）模式的推廣，網(wǎng)絡數(shù)據(jù)正以空前的速度不斷累積。為了從海量的動態(tài)數(shù)據(jù)中發(fā)現(xiàn)有價值的信息，社會網(wǎng)絡分析（Social Network Analysis）這一新興的研究領(lǐng)域應運而生。作為社會網(wǎng)絡分析的關(guān)鍵問題，鏈接預測近些年來得到越來越多研究者的關(guān)注。鏈接預測根據(jù)社會網(wǎng)絡現(xiàn)有的結(jié)構(gòu)，預測隱含的鏈接或是將來可能產(chǎn)生的鏈接。已有的鏈接預測方法主要分成三類：（1）基于節(jié)點相似度的方法；（2）基于網(wǎng)絡拓撲結(jié)構(gòu)特征的方法；（3）基于概率模型的方法[1]。其中，基于網(wǎng)絡拓撲結(jié)構(gòu)特征方法的使用較為廣泛，而其他兩種方法在網(wǎng)絡節(jié)點數(shù)目較多時會產(chǎn)生很大的時間開銷[2]。鏈接預測的應用領(lǐng)域非常廣泛。例如，利用鏈接預測方法，在線社交網(wǎng)站可以幫助用戶發(fā)現(xiàn)自己的朋友；電子商務網(wǎng)站可以給用戶推薦感興趣的商品；醫(yī)學研究者能夠更好地認識蛋白質(zhì)等復雜網(wǎng)絡的結(jié)構(gòu)[3]；而在安全領(lǐng)域，鏈接預測亦可實現(xiàn)對復雜超網(wǎng)絡結(jié)構(gòu)演化的建模和預測分析，在實際的輿情監(jiān)控系統(tǒng)中有著重要作用[4]。

傳統(tǒng)的鏈接預測方法主要分析網(wǎng)絡當前的靜態(tài)特征，忽略了網(wǎng)絡在演變過程中可能隱含的額外的時間信息[5]。目前，已有一些研究者嘗試引入網(wǎng)絡結(jié)構(gòu)隨時間變化的信息，研究動態(tài)網(wǎng)絡中的鏈接預測問題。在此背景下，本文提出了一種基于網(wǎng)絡特征動態(tài)變化的鏈接預測方法。該方法挖掘網(wǎng)絡結(jié)構(gòu)特征的變化數(shù)據(jù)，為每一個結(jié)構(gòu)的特征變化建立一個學習器，最后通過優(yōu)化算法為各個學習器分配權(quán)值，得到最終集成的預測模型。

2 動態(tài)網(wǎng)絡中的鏈接預測問題

鏈接預測問題通常被形式化為：給定一個社會網(wǎng)絡G=(V,E)（其中，V是網(wǎng)絡節(jié)點的集合，E是網(wǎng)絡目前能觀察到的邊的集合），對于一個尚未形成鏈接的節(jié)點對＜u,v＞，預測其形成鏈接的概率。

傳統(tǒng)的鏈接預測方法主要分析某一時刻的靜態(tài)網(wǎng)絡。例如，陳可佳等人[6]利用網(wǎng)絡中的未標記數(shù)據(jù)幫助學習，提出并使用兩種半監(jiān)督范式進行鏈接預測；伍杰華[7]嘗試引入“樹狀”結(jié)構(gòu)來描述合著者網(wǎng)絡中的鏈接關(guān)系，結(jié)合樸素貝葉斯分類器和節(jié)點相似度特征進行鏈接預測；張健沛和姜延良[8]提出了一種基于節(jié)點相似性的鄰居關(guān)系權(quán)值預測算法。在國外的研究者中，Liben-Nowell和Kleinberg[9]通過研究arXiv合著者網(wǎng)絡，發(fā)現(xiàn)了采用Jaccard、Adamic-Adar和Katz這些結(jié)構(gòu)特征的鏈接預測方法性能遠優(yōu)于隨機預測。然而，傳統(tǒng)的鏈接預測方法忽視了社會網(wǎng)絡在演化過程中產(chǎn)生的潛在信息，這些信息對于預測未來時刻的鏈接是有幫助的。

因此，動態(tài)鏈接預測問題得到了越來越多研究者的關(guān)注。張昱等人[10]基于節(jié)點在相近時間發(fā)布的內(nèi)容相似性更大的假設，在博客數(shù)據(jù)集上提出了一個比傳統(tǒng)方法更為有效的鏈接預測方法；Kumar等人[11]研究了Flickr和Yahoo!360的演化過程，根據(jù)社會網(wǎng)絡中的三種結(jié)構(gòu)（單獨節(jié)點、孤立社區(qū)和巨大連通分支），提出了一個簡單有效的社會網(wǎng)絡演化模型。Huang和Lin[12]綜合了靜態(tài)結(jié)構(gòu)特征和時間特征，提出了一個線性自回歸模型。Tylenda等人[13]在動態(tài)網(wǎng)絡中使用了時間特征和其他靜態(tài)特征實現(xiàn)節(jié)點對的排序。Sharan和Neville[14]使用靜態(tài)帶權(quán)圖來表示動態(tài)網(wǎng)絡，再用關(guān)系貝葉斯分類器進行預測。Potgieter等人[15]研究了用于鏈接預測的時間度量方法。Da Silva Soares等人[16]計算網(wǎng)絡結(jié)構(gòu)特征的時間序列，并訓練該數(shù)據(jù)得到分類器進行預測。

3 本文提出的方法

3.1 方法描述

本文在監(jiān)督學習框架中對網(wǎng)絡中節(jié)點對結(jié)構(gòu)特征的動態(tài)變化進行建模，根據(jù)學得的模型預測網(wǎng)絡下一時刻可能出現(xiàn)的鏈接。該方法命名為EnDLiP（Ensemble based Dynamic Link Prediction）。首先，根據(jù)時間軸得到網(wǎng)絡的演化序列，選取若干描述節(jié)點對樣本的結(jié)構(gòu)特征；然后記錄樣本的每個結(jié)構(gòu)特征在網(wǎng)絡演化過程中的變化情況，并訓練得到一個學習器；最后采用集成的方法，將每個學習器的預測結(jié)果加權(quán)得到最終的模型。

本文的集成學習框架采用Schapire提出的boosting方法，該算法采用加入輸入擾動，在訓練集樣本上抽取不同特征，訓練出多個弱分類器，之后通過集成得到預測性能更好的強分類器。在分類的過程中，每個樣本都設置不同的權(quán)值，權(quán)值隨著每次樣本的分類結(jié)果及整體分類結(jié)果改變，若該樣本分類正確，就降低其權(quán)值，否則，提高權(quán)值。將調(diào)整過后的樣本作為下一輪的新樣本繼續(xù)迭代訓練，最后進行融合。該模型的框架流程圖如圖1。

圖1 EnDlip算法流程圖

為了完整描述EnDLiP，需要引入下列符號。令一個社會網(wǎng)絡G在時刻t的狀態(tài)為Gt，該社會網(wǎng)絡的演化序列為{G1,G2,…,Gt,…,GT}。＜αi＞表示訓練集中的第i個節(jié)點對樣本。label＜αi＞表示＜αi＞的標簽信息（已連接的節(jié)點對標記為1，未連接的節(jié)點對標記為0）。{Fea1,Fea2,…,Feaj,…,FeaN}表示為樣本選取的所有結(jié)構(gòu)特征的集合，F(xiàn)eaj表示其中的第j個特征。Feaj＜αi＞t表示＜αi＞在t時刻的Feaj值。ΔFeaj＜αi＞t=Feaj＜αi＞t+1-Feaj＜αi＞t表示在相鄰時間片段中Feaj的變化情況。{ΔFeaj＜αi＞1,…,ΔFeaj＜αi＞t}表示由ΔFeaj＜αi＞x組成的長度為t的序列，其中x的取值范圍為[1,t]。為每個Feaj分別生成訓練集TrainSet(Fj,label＜αi＞)。其中，F(xiàn)j表示第i個樣本的第j個特征變化值的演變序列，即對訓練集中所有＜αi＞的訓練得到分類器ClfFeaj。ClfFeaj＜αj＞表示ClfFeaj預測＜αi＞會形成鏈接的強度。令?為權(quán)值向量，?=(w1,w2,…,wj,…,wN)，其中的wj表示為分類器ClfFeaj分配的權(quán)值。

EnDLiP的偽代碼描述如下：

3.2 補充說明

為了描述網(wǎng)絡特征的動態(tài)變化ΔFeaj＜αi＞t，除了差分（Feaj＜αi＞t+1-Feaj＜αi＞t）外，還可以使用變化率((Feaj＜αi＞t+1-Feaj＜αi＞t)/Feaj＜αi＞t)。不過此時需要處理Feaj＜αi＞t值為0的情況（見實驗部分）。下文中，代表用差分得到的序列，代表采用變化率得到的序列。

Feaj＜αi＞t的計算可不必從t=1開始。實際數(shù)據(jù)中，結(jié)構(gòu)特征值往往從中間某個時刻才發(fā)生變化。因此，取一個長度為h（數(shù)值在實驗中確定）的時間段[T-1-h,T-1]，在此區(qū)間上計算Feaj＜αi＞t的值。這在一定程度上反映了，網(wǎng)絡在某一時刻的狀態(tài)和之前h個時刻的狀態(tài)更相關(guān)。

EnDLiP中h值和動態(tài)度量的確定方法為先令h=1，分別使用差分和變化率得到兩個不同的訓練集，訓練得到分類器ClfFeaj|diff和分類器ClfFeaj|rate。根據(jù)測試集中的預測結(jié)果分別得到和，代表利用差分和變化率得到的ROC曲線下的面積，值越高，所對應的預測模型性能也就越好；隨后對h依次加1得到h′，當時，令h′代替h，并根據(jù)和的大小決定選擇差分還是變化率作為衡量h′時間段中網(wǎng)絡動態(tài)變化的方法。計算變化率時，為了防止除數(shù)為0，先為每個特征值加1再進行計算。

為每個結(jié)構(gòu)特征找到合適的h和動態(tài)度量方法后，可以得到一個分類器（本文實驗中有4個特征，共得到4個分類器）。隨后，使用最小二乘法優(yōu)化從而得到權(quán)值向量?。運用最小二乘法，可以讓期望輸出和真實輸出間的均方誤差最小，即：

要使得J(w)最小，需要滿足正交條件：

4 實驗結(jié)果與分析

4.1 數(shù)據(jù)集與特征選取

實驗使用了arXiv網(wǎng)站上三個現(xiàn)實的合著者網(wǎng)絡數(shù)據(jù)（nucl-th、hap-lat和hep-ex）。在合著者網(wǎng)絡中，每個節(jié)點代表一個作者，如果兩個作者有合作關(guān)系，則在兩個節(jié)點間會形成一條邊。nucl-th網(wǎng)絡的起止時間為1993—2010年；hep-lat網(wǎng)絡的起止時間為1993—2010年；hep-ex網(wǎng)絡的起止時間為2002—2012年。

實驗首先設定每個網(wǎng)絡的演化序列。對nucl-th網(wǎng)絡和hep-lat網(wǎng)絡，按兩年劃分時間片段，得到網(wǎng)絡演化序列{G1994,G1996,…,G2008,G2010}。對hep-ex網(wǎng)絡，按一年劃分時間片段，得到的網(wǎng)絡演化序列{G2002,G2003,…,G2011,G2012}。

本文選擇了在鏈接預測領(lǐng)域較為常用的網(wǎng)絡結(jié)構(gòu)特征：優(yōu)先連接（PA）、共同鄰居（CN）、Adamic Adar分數(shù)（AA）和Jaccard系數(shù)（JC）。計算方法如表1（其中，Γ(u)代表節(jié)點u的鄰居集合，|Γ(u)|代表u的度）。

表1 結(jié)構(gòu)特征描述

4.2 實驗設置

為了便于比較，本文按Da Silva Soares等人的方法設置訓練集和測試集。對于一個網(wǎng)絡的演化序列{G1,G2,…,Gt,…,GT}：首先，找出所有從Gt-1到Gt時新形成鏈接的節(jié)點對，記為集合A。然后，找出Gt-1中所有滿足如下條件的節(jié)點對＜u,v＞，記為集合B。要求：節(jié)點u和節(jié)點v距離為2跳，且u和v在之前的任意時刻都未形成鏈接。最后，得到集合C(C=A?B)和集合D(D=B-A)。將C作為測試集中的正例集合，從D中選取和正例數(shù)目相同的節(jié)點對作為測試集的反例集合，得到一個正、反例數(shù)目均等的測試集。選取訓練集的方法和選取測試集的方法相同，只是訓練集中的A表示從Gt-2時刻到Gt-1時刻新形成鏈接的節(jié)點對集合，而B表示是Gt-2中的距離為2跳的節(jié)點對集合。

為三個合著者網(wǎng)絡選取訓練集和測試集的樣本數(shù)目如表2。

表2 各合著者網(wǎng)絡訓練集和測試集的數(shù)目

4.3 比較方法

為了驗證EnDLiP的有效性，本文還實現(xiàn)了兩種相關(guān)的比較方法。第一種為傳統(tǒng)的靜態(tài)預測方法，另一種是Da Silva Soares等人提出的方法。在靜態(tài)預測方法中，只利用Gt-1中的信息為每一個結(jié)構(gòu)特征進行訓練并集成，其他配置與EnDLiP相同。第二個比較方法先對每一種結(jié)構(gòu)特征計算其在網(wǎng)絡演化過程中各個時刻的值，得到一個結(jié)構(gòu)特征時間序列，然后采用簡單指數(shù)平滑法（SES）和移動平均值（MA）來預測下一時刻的特征值。將所有結(jié)構(gòu)特征的預測值作為一個混合特征向量，通過學習模型（如SVM）進行訓練，得到鏈接預測結(jié)果。

4.4 實驗結(jié)果與分析

表3～表5展示了在三個網(wǎng)絡中每個結(jié)構(gòu)特征所宜采用的度量方法、最佳訓練時間段（h值），以及對應分類器的權(quán)重。圖2是在三個網(wǎng)絡中各方法的ROC曲線比較圖。其中，EnDLiP是本文提出的方法，用實線表示。其余三條虛線分別代表Da Silva Soares等人方法中預測效果最好的兩種模型（不同網(wǎng)絡中的最優(yōu)模型未必相同），以及靜態(tài)的監(jiān)督鏈接預測方法。

圖2 網(wǎng)絡中各方法的ROC曲線比較

表3 nucl-th網(wǎng)絡中各結(jié)構(gòu)特征的實驗配置

表4 hep-lat網(wǎng)絡中各結(jié)構(gòu)特征的實驗配置

表5 hep-ex網(wǎng)絡各結(jié)構(gòu)特征的實驗配置

實驗結(jié)果表明，考慮網(wǎng)絡結(jié)構(gòu)演變信息后，鏈接預測的性能確實有了很大的提高。例如，在hep-lat網(wǎng)絡中，EnDLiP的AUC值比靜態(tài)預測方法要高出8.4%，并且比Da Silva Soares等方法的最好結(jié)果還要高出13.7%。在三個網(wǎng)絡中，h的取值都較小（2～4），這說明在預測時刻，只需考察之前一小段時間內(nèi)網(wǎng)絡結(jié)構(gòu)的演變信息即可。

Da Silva Soares等的方法雖然考慮了網(wǎng)絡的動態(tài)變化，但采用的預測模型較簡單，且只對預測值進行訓練，因此預測性能跟理想情況有一定的差距。相比之下，EnDLiP并沒有引入新的預測值，而是利用了更多的網(wǎng)絡演變信息進行訓練，所以性能上能有所提高。

此外，從各分類器在集成時分配的權(quán)重也可以發(fā)現(xiàn)，雖然在每個網(wǎng)絡中的權(quán)值略有差別，但總體上，結(jié)構(gòu)特征CN和AA所占的權(quán)重要高于結(jié)構(gòu)特征PA和JC所占的權(quán)重。這說明，結(jié)構(gòu)特征CN和AA比PA和JC更適合描述網(wǎng)絡結(jié)構(gòu)的動態(tài)演變。

5 結(jié)束語

針對傳統(tǒng)靜態(tài)鏈接預測方法的局限，本文提出了一種動態(tài)的鏈接預測方法EnDLiP。該方法描述了網(wǎng)絡特征的動態(tài)變化情況，通過集成學習的方法對動態(tài)信息建模，實現(xiàn)了鏈接預測的目的。實驗表明，引入網(wǎng)絡動態(tài)變化的信息，確實提高了鏈接預測的性能。此外，對于不同的網(wǎng)絡結(jié)構(gòu)特征，其適合的動態(tài)變化度量方法（差分或變化率）與之前關(guān)聯(lián)時間片段數(shù)目（h值）均有所不同。此外，實驗也表明了不同結(jié)構(gòu)特征對網(wǎng)絡動態(tài)變化的刻畫能力也有所不同。

本文使用的集成方法還較為簡單，未來將討論其他先進集成方法的有效性。此外，也將嘗試其他刻畫網(wǎng)絡動態(tài)變化的方法，并考察其刻畫能力。

[1] Xie X，Li Y，Zhang Z.A joint link prediction method for social network[J].IFIP Advances in Information&Communication Technology，2015，503：56-64.

[2] Peng W，Baowen X U，Yurong W U.Link prediction in social networks：The state-of-the-art[J].Science China Information Sciences，2014，58（1）：1-38.

[3] Kaya B，Poyraz M.Age-series based link prediction in evolvingdiseasenetworks[J].ComputersinBiology&Medicine，2015，63（C）：1-10.

[4] 田儒雅，劉怡君，牛文元.輿論超網(wǎng)絡的領(lǐng)袖引導模型[J].中國管理科學，2014，22（10）：136-141.

[5] Bliss C A，F(xiàn)rank M R.An evolutionary algorithm approach to link prediction in dynamic social networks[J].Journal of Computational Science，2013，5（5）：750-764.

[6] 陳可佳，韓京宇，鄭正中.半監(jiān)督學習在鏈接預測問題中的應用[J].計算機工程與應用，2012，48（33）：136-141.

[7] 伍杰華.基于樹狀樸素貝葉斯模型的社會網(wǎng)絡關(guān)系預測[J].計算機應用，2013，33（11）：3134-3137.

[8] 張健沛，姜延良.一種基于節(jié)點相似性的鏈接預測算法[J].中國科技論文，2013，8（7）：659-662.

[9] 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.

[10] 張昱，張恩德，李封.基于時間信息的社會網(wǎng)絡鏈接預測研究[J].計算機與數(shù)字工程，2012，40（11）：50-51.

[11] Kumar R，Novak J，Raghavan P.Structure and evolution of blogspace[J].Communications of the ACM，2004，47（12）：35-39.

[12] Huang Z，Lin D K J.The time-series link prediction problem with applications in communication surveillance[J].Informs Journal on Computing，2009，21（2）：286-303.

[13] Tylenda T，Angelova R，Bedathur S.Towards time-aware link prediction in evolving social networks[C]//Proceedings of Workshop on Social Network Mining&Analysis Snakdd，2009：1-10.

[14] Sharan U，Neville J.Exploiting time-varying relationships in statistical relational models[C]//Webkdd and，Sna-Kdd 2007 Workshop on Web Mining and Social Network Analysis，2007：9-15.

[15] Potgieter A，April K A，Cooke R J E，et al.Temporality in link prediction：Understanding social complexity[J].Emergence Complexity&Organization，2007（11）：2007.

[16] Da Silva Soares P R，Bastos C P R.Time series based link prediction[C]//International Joint Conference on Neural Networks，2012：1-7.

AN Chen,CHEN Yang.Dynamic link prediction method based on ensemble learning.Computer Engineering and Applications,2018,54（6）：110-114.

AN Chen,CHEN Yang

College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210046,China

Link prediction is a crucial problem in social network analysis.Most of the traditional link prediction methods find the missing links or predict the future links merely based on astatic structure of a network,ignoring its dynamics.In order to utilize the dynamic information of the network better and achieve a more preferable result,in this paper,a method with consideration of the network evolution is proposed.A machine learning technique is used to model the change of the structural characteristics in networks.A classifier is trained for each structural feature and a final ensemble result is obtained by weighting all the classifiers.The experimental results in three real collaboration networks show that the proposed method outperforms the traditional static link prediction method and a related dynamic link prediction method,which demonstrates that the results of link prediction are much facilitated with the dynamic information of the network.Moreover,the experimental result also shows that different structural characteristics have different abilities to describe the network dynamics.

link prediction;machine learning;dynamic network;social network analysis;ensemble learning;supervised learning

鏈接預測是社會網(wǎng)絡分析領(lǐng)域的關(guān)鍵問題。傳統(tǒng)的鏈接預測方法大多針對社會網(wǎng)絡的靜態(tài)結(jié)構(gòu)預測隱含的鏈接或者將來可能產(chǎn)生的鏈接，而忽視了網(wǎng)絡在動態(tài)演變過程中的潛在信息。為了能更好地利用網(wǎng)絡演變的動態(tài)信息，從而取得更好的鏈接預測效果，提出了一種基于網(wǎng)絡結(jié)構(gòu)演變規(guī)律的鏈接預測方法。該方法使用機器學習技術(shù)對網(wǎng)絡結(jié)構(gòu)特征的動態(tài)變化信息進行訓練，學習每種結(jié)構(gòu)特征的變化并得到一個分類器，為每個分類器加權(quán)得到最終集成的結(jié)果。在三個現(xiàn)實的合著者網(wǎng)絡數(shù)據(jù)集上的實驗結(jié)果表明，該方法的性能要高于靜態(tài)鏈接預測方法和一個相關(guān)的動態(tài)鏈接預測方法。這說明，網(wǎng)絡結(jié)構(gòu)演變信息有助于提高鏈接預測效果。此外，實驗還表明，不同的結(jié)構(gòu)特征對網(wǎng)絡動態(tài)變化的刻畫能力也有所差別。

鏈接預測；機器學習；動態(tài)網(wǎng)絡；社會網(wǎng)絡分析；集成學習；監(jiān)督學習

2016-10-17

2016-12-04

1002-8331（2018）06-0110-05

A

TP391

10.3778/j.issn.1002-8331.1610-0187

國家自然科學基金青年基金（No.61100135，No.61302158）。

安?。?991—），男，碩士研究生，主要研究方向：機器學習、數(shù)據(jù)挖掘，E-mail：chenan0120@163.com。