基于集成學習的動態鏈接預測方法

安琛，陳陽

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

基于集成學習的動態鏈接預測方法

安琛，陳陽

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

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

1 引言

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

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

2 動態網絡中的鏈接預測問題

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

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

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

3 本文提出的方法

3.1 方法描述

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

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

圖1 EnDlip算法流程圖

為了完整描述EnDLiP，需要引入下列符號。令一個社會網絡G在時刻t的狀態為Gt，該社會網絡的演化序列為{G1,G2,…,Gt,…,GT}。＜αi＞表示訓練集中的第i個節點對樣本。label＜αi＞表示＜αi＞的標簽信息（已連接的節點對標記為1，未連接的節點對標記為0）。{Fea1,Fea2,…,Feaj,…,FeaN}表示為樣本選取的所有結構特征的集合，Feaj表示其中的第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＞)。其中，Fj表示第i個樣本的第j個特征變化值的演變序列，即對訓練集中所有＜αi＞的訓練得到分類器ClfFeaj。ClfFeaj＜αj＞表示ClfFeaj預測＜αi＞會形成鏈接的強度。令?為權值向量，?=(w1,w2,…,wj,…,wN)，其中的wj表示為分類器ClfFeaj分配的權值。

EnDLiP的偽代碼描述如下：

3.2 補充說明

為了描述網絡特征的動態變化Δ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開始。實際數據中，結構特征值往往從中間某個時刻才發生變化。因此，取一個長度為h（數值在實驗中確定）的時間段[T-1-h,T-1]，在此區間上計算Feaj＜αi＞t的值。這在一定程度上反映了，網絡在某一時刻的狀態和之前h個時刻的狀態更相關。

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

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

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

4 實驗結果與分析

4.1 數據集與特征選取

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

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

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

表1 結構特征描述

4.2 實驗設置

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

為三個合著者網絡選取訓練集和測試集的樣本數目如表2。

表2 各合著者網絡訓練集和測試集的數目

4.3 比較方法

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

4.4 實驗結果與分析

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

圖2 網絡中各方法的ROC曲線比較

表3 nucl-th網絡中各結構特征的實驗配置

表4 hep-lat網絡中各結構特征的實驗配置

表5 hep-ex網絡各結構特征的實驗配置

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

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

此外，從各分類器在集成時分配的權重也可以發現，雖然在每個網絡中的權值略有差別，但總體上，結構特征CN和AA所占的權重要高于結構特征PA和JC所占的權重。這說明，結構特征CN和AA比PA和JC更適合描述網絡結構的動態演變。

5 結束語

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

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

[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] 田儒雅，劉怡君，牛文元.輿論超網絡的領袖引導模型[J].中國管理科學，2014，22（10）：136-141.

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

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

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

[8] 張健沛，姜延良.一種基于節點相似性的鏈接預測算法[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] 張昱，張恩德，李封.基于時間信息的社會網絡鏈接預測研究[J].計算機與數字工程，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

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

鏈接預測；機器學習；動態網絡；社會網絡分析；集成學習；監督學習

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）。

安琛（1991—），男，碩士研究生，主要研究方向：機器學習、數據挖掘，E-mail：chenan0120@163.com。