吳祖峰，梁棋，劉嶠，秦志光

（電子科技大學 計算機科學與工程學院，四川 成都 610054）

1 引言

鏈路預測(link prediction)問題源于復雜網絡研究領域，目的是根據目標網絡的觀測數據（節(jié)點和關系）預測該網絡中節(jié)點間可能存在的關系和將會產生的關系[1]。典型的鏈路預測問題解決方案包括優(yōu)先鏈接原則和森林火災模型[2]。

鏈路預測采用的主要研究方法是依據當前網絡的拓撲結構來評估節(jié)點間關系的重要性，據此推斷節(jié)點間存在關系的可能性。鏈路預測方法可用于恢復目標網絡觀測數據中的缺失信息[3]，也可以用于研究網絡的衍變[1]。此外，由于僅依賴于網絡拓撲結構進行推斷，所以可以將其推廣到多種類型的網絡中，如社交網絡、生物領域、合作網絡等。隨著一些鏈路預測算法開始在商業(yè)領域得到應用，與之相關的研究已經成為一個熱門領域，其中，基于圖的鏈路預測算法的研究在近年來受到了廣泛重視[4]。例如，Facebook采用基于有重啟的隨機游走（RWR, random walk with restart）算法預測用戶的朋友關系，據此提高好友推薦的成功率[5]。

基于網絡拓撲圖的鏈路預測算法主要包括基于節(jié)點鄰居的相似性、基于最大似然估計[6]以及基于概率模型3種類型。代表性算法包括基于局部信息相似性的共同鄰居(common neighbor）算法、基于路徑相似性的 Katz算法和基于隨機游走相似性的RWR算法。其中，基于節(jié)點鄰居相似性的鏈路預測算法研究較早，因其性能表現相對良好，多數算法研究工作均將其作為基準參考算法[5]。另一類取得實際推廣應用的方法是基于隨機游走的鏈路預測算法。這些算法的基本思想都是對圖中節(jié)點所有可能的組合進行排序，選擇出其中最可能出現在新圖中的節(jié)點對（即圖中的邊）。

2007年，Liben-Nowell D等人在鏈路預測方面所做的開創(chuàng)性工作引起了學術界對于該問題的重視[1]。其提出的一些基本方法也成為鏈路預測研究中進行算法性能比較的Benchmark算法。其中，被廣泛引用的算法包括：共同鄰居（CN, common neighbor）法、杰卡德系數（JC, Jaccard's coefficient）法和Adamic/Adar（AA）法。所謂共同鄰居法，是指2個節(jié)點的共同鄰居節(jié)點的數目，Kossinets和Watts使用該方法分析了一個大規(guī)模的社會網絡，發(fā)現共同朋友越多的2個人越有可能在未來成為朋友[7,8]。杰卡德算法是共同鄰居法的標準化方法，表示2個節(jié)點是否含有一個共同特征[9]。Adamic/Adar法是由Adamic和Adar提出的一種方法[10]。在合作網絡中，作者w與作者u、v均有合作，如果w和u、v以外的作者沒有合作關系，那么u、v之間更有可能合作。

除上述3種Benchmark算法之外，本文還引入了近年來受到廣泛關注的基于隨機游走相似性指標的重啟的隨機游走（RWR）算法作為參照[11]。該方法可以視為 PageRank算法的擴展，二者的區(qū)別在于RWR算法假設隨機漫步者每走一步都以一定概率返回初始位置。該算法已經被應用于推薦系統(tǒng)的算法研究之中[12]。

表1給出了上述算法的名稱以及計算公式。其中，符號Γ(u)表示節(jié)點u的鄰居節(jié)點集合。

表1 預測算法名稱及公式

Polikar R 等人關于集成學習（ensemble learning）的研究表明，在對各種問題進行決策時，人們通常會在決策前尋求多種可能的選擇，通過對這些選擇進行權衡通常能夠做出最明智的決定，因此相對于單一的專家系統(tǒng)而言，多個不同性質專家系統(tǒng)的集成會產生更為有利的結果。同樣的原則適用于統(tǒng)計機器學習領域，即單一的分類器在不同問題上的泛化表現可能不同，而按照一定的原則對多種分類器進行集成則有可能實現算法性能的均衡和提升，減少因分類器選擇不當而導致的泛化性能表現過差的風險[13]。例如，由多個醫(yī)生對病人會診，不僅有助于降低誤診的風險，而且有助于得出最優(yōu)的診斷結果。Boosting方法是一類有效的集成學習方法，研究表明它能夠提高任意給定學習算法的準確度[14]。本文采用經典的 Adaboost (adaptive boosting)算法作為鏈路預測算法的集成學習器[13]。

AdaBoost是最具代表性的 Boosting算法，由Freund 和 Schapire 于 1995年提出，現有的各種Boosting算法都是在 AdaBoost算法的基礎之上發(fā)展而來的。其突出優(yōu)點是不需要任何關于弱學習器的先驗知識，樣本分布的改變取決于樣本是否被正確分類。算法的基本思路是賦予分類正確的樣本以較低的權值，同時調高分類錯誤樣本的權值，作為后續(xù)學習器的輸入，最終得到的結果是弱分類器的加權組合。AdaBoost是一種有很高精度的分類器，能夠有效避免過擬合。

近一兩年來，在基于拓撲的鏈路預測算法的研究中，在對已有算法的改進以及新算法的提出方面，仍然還沒有出現有突破性的成果，基于拓撲的鏈路預測算法的召回率依然較低。

通過本文的研究發(fā)現，現有的主流鏈路預測方法的預測結果并不完全相交，直覺上認為有可能利用算法結果的疊加提高召回率。但是，直接累加求和并不可行，因為會降低總的算法精度（如圖1所示）。據此考慮采用基于Boosting的集成學習方法對其進行改進[13]。首先將鏈路預測問題看作二分類問題，對下一時刻網絡中每一條可能存在的邊（節(jié)點對），其分類結果為2類：存在或不存在。接下來借用Boosting方法通過錯誤反饋提升弱學習算法得到強學習算法的思想，根據一定的原則選取若干鏈路預測算法作為弱分類器，基于 AdaBoost算法提出并實現了一個新的算法。在本文所使用的論文合作網絡數據集以及郵件通信數據集上的實驗結果表明，本文提出的算法對預測算法的準確度和召回率都有一定的提高。

圖1 CN和JC的預測范圍交集以及正確結果交集

2 算法設計

2.1 算法改進的依據

為了與現有工作做比較，本文選取arXiv論文合作網絡數據作為數據集，數據的選擇是參照Liben-Nowell D和Leskovec J的工作[5]選取，以便對實驗結果進行比較。數據的獲取是使用爬蟲從www.arxiv.org網站分別爬取4個領域的文章作者列表。爬取策略參見3.1節(jié)。以Hep-ph領域數據為例，如果2個作者出現在同一篇文章的作者列表中，則為這2個節(jié)點生成一條邊，代表他們有進行過合作。筆者以 1994～1996年作為預測的訓練集合，1997～1999年作為預測的測試集合。為所有度為3以上的活躍作者做預測。表2可以看到幾種常用的鏈路預測算法在數據集Hep-ph上預測新生成邊的正確結果的交集。每 2種算法之間都有交集，但并不完全重合。直覺上可以合并正確結果以擴大正確預測范圍。

表2 每2個算法預測的正確結果的交集

但是直接合并預測結果會使得預測范圍過分擴大，減少預測精度。以算法CN和JC為例。如圖1所示。左右兩側的圓形區(qū)域分別代表算法CN和算法 JC的預測結果，每個圓形區(qū)域表示的節(jié)點對的數目為1 500。區(qū)域A∪B∪C表示二者預測結果中相同的節(jié)點對，數值為692。區(qū)域A∪B∪C∪D∪E∪F∪G表示二者預測結果的并集，節(jié)點對數目為2 308。區(qū)域B∪E以及區(qū)域B∪D分別表示算法CN以及算法JC預測結果中正確的部分，節(jié)點對的數目分別為100和97。相應的區(qū)域B為二者正確預測結果的交集，節(jié)點對數目為56。

算法 CN、JC預測的準確率分別為 9.52%和9.23%。如果對 2個算法的預測結果只是做簡單的合并，即預測結果是區(qū)域A∪B∪C∪D∪E∪F∪G。正確預測值是區(qū)域E∪B∪D，節(jié)點對數目為141。準確率變?yōu)?.10%。由此可以看出，簡單的合并會使得準確率下降。

由此考慮采用Boosting的思想。采用每種算法的預測結果，根據錯誤反饋，將弱學習算法提升為強學習算法能夠有效縮小預測范圍，即縮小圖中 2個圓形區(qū)域的并集。擴大正確預測結果的并集，即圖中的黑色部分。有效地提升預測精度。

2.2 弱分類器的選擇

基于局部信息相似性的鏈路預測算法是經典算法，因其性能表現相對較好，多數算法研究工作均將其作為基準參考算法。在鏈路預測中，發(fā)現距離為2的2個節(jié)點鏈接的概率大于距離值為其他的節(jié)點對[5]，局部信息相似性的算法在鏈路預測中仍占重要地位，本文選取其中表現相對良好的CN、JC、AA作為弱分類器。而RWR作為基于隨機游走的預測算法，因其良好表現，也將之選取作為弱分類器。

Wuv表示節(jié)點間已經鏈接的邊的數目。在合作網絡中，即二者已合作文章數，圖2表示在Hep-th數據集上，作者在1994～1996三年間已合作文章數目與他們在1997～1999三年間再次合作概率的關系圖。隨著已合作文章數目的增長，兩人間再次合作的概率也越來越大。當已合作文章數大于10篇時，兩人再次合作的概率可以達到90.32%?？梢圆孪胨麄円呀浶纬梢环N長期合作的關系。已合作文章數目大于2的作者再次合作的概率均超過了50%。根據以上描述，對于已經合作過的人來說，如果他們已有合作，那么有1/2的可能他們會繼續(xù)合作下去。所以在對節(jié)點間當前已有邊的情況進行預測時，考慮將Wuv選為弱分類器。

圖2 已合作文章數目與再次合作概率關系

2.3 算法概述

算法1給出了算法的基本流程。對于一組長度為m的預測訓練集合C。Ω表示xi被分類的類型值的集合。對于xi，如果它確實出現在下一時間段的圖中，則yi=1，反之，yi=-1。接著按照式(1)為每個樣本的權重賦初始值。

算法1 ALP算法偽代碼

給定：長度為m的有著樣本標簽yi∈Ω,Ω={-1,+1}的預測訓練集合

Initialise Weights：

每個樣本最終預測結果為

對于每一種預測算法t，計算出C中每一對節(jié)點u、v的Suv，然后進行降序排列，選取前m個節(jié)點對，形成集合P，表示算法t判定這些節(jié)點對會在下一時刻的圖中存在，剩下的形成集合Q，表示算法t判定這些節(jié)點對不會在下一時刻的圖中存在。m是集合C中實際存在于下一時間段的圖中的節(jié)點對數目。將預測算法t看作一個弱分類器t，t做出的假設為ht。根據式(2)，如果xi∈P，則ht(xi)=1，反之，若xi∈Q，ht(xi)=-1。

進行T次循環(huán)，t=1,…,T：每一次循環(huán)時，首先為每個分類器計算當前的錯誤率。對于每一個樣本xi，將分類器t對其的分類與其本身所屬類型相比，如果不一致，則在此分類器的錯誤率上加上該樣本xi的權重Dt(i)。按照式(3)計算并找出錯誤率最小的分類器作為當前的分類器。但是如果εt大于1/2。就停止算法。以式(4)對εt進行歸一化處理，0＜αt＜1，αt作為當前分類器t的投票權重。更新每個樣本xi的權重，如果xi被當前分類器錯誤分類，則它的權重上升。相對來說xi如果被正確分類，那么它的權重就降低了，具體按照式(5)、式(6)升級每個樣本xi的權重。T次循環(huán)后，得到每個分類器的投票權重αt。

預測測試集合D中，使用ej表示D中的每個節(jié)點對，n為D中所有節(jié)點對的數目。對于每種預測算法t，計算出預測測試集合D中每一對節(jié)點u、v的Suv，然后進行降序排列，選取前m'個節(jié)點對，形成集合P'，剩下的形成集合Q'。m'是集合D中實際存在于下一時間的圖中的節(jié)點對數目。按照式(7)，如果ej∈P'，則ht(ej)=1，反之，若ej∈Q'，ht(ej)=-1。

由式(8)獲得每個分類器t對于樣本ej的投票總和。對于每個ej，由每個弱分類器t對其進行投票。如果分類器t判定ej在下一時刻圖中存在，則ej的權重Wej加上此分類器的投票權重αt。如果分類器t判定ej在下一時刻的圖中不存在，則為ej的權重Wej減去此分類器的投票權重αt。在所有分類器對ej投票完成之后，若ej的權重Wej為正，即預測ej會在下一時刻的圖中存在。反之，ej的權重Wej為負，則預測ej不會在下一時刻的圖中存在。

3 實驗結果與討論

3.1 數據集

給定一個圖G=＜V,E＞，對于合作網絡，合作關系不存在方向性，將它視為無向圖。對于Email-Net，即郵件網絡，視作有向圖。邊e=(u,v)∈E。設Gi代表了在時刻ti到ti'時間段內圖G的子圖。選取t0＜t0'＜t1＜t1'＜t2＜t2'這幾個時間段。將G0和G1作為分類器權重訓練的訓練集。將G1和G2作為對G1預測在G2上驗證的測試集。

本文使用的數據集包括arXiv論文合作網絡中4個領域的數據以及一組電子郵件網絡數據。其中，論文合作網絡的數據使用scrapy爬蟲爬取。具體策略如下。

首先選定爬取的文章領域以及文章發(fā)表的時間段，爬取該時間段該領域所有文章的鏈接并將其存儲在數據庫中。將所有的文章鏈接標記為未爬取。然后從數據庫中選取一定數量的未被爬取的文章鏈接，對其進行爬取。完成后將此文章鏈接標記為已爬取。重復爬取過程直到所有的文章鏈接標記為已爬取。使用Xpath對爬取下來的頁面進行解析，獲取每篇文章的題目、發(fā)表時間以及作者列表，將結果存入到數據庫中。

對于爬取下來的作者列表，以Hep-ph為例。將每個作者視為一個節(jié)點，如果2個作者出現在同一篇文章的作者列表中，則為這2個節(jié)點間生成一條無向邊。對這個領域的所有文章的作者列表處理完成后，生成一個這個領域的關系網絡。定義t0為1994年，t0'為1996年，t1為1997年，t1'為1999年，t2為2000年，t2'為2002年。所有的圖均為無向圖。其他3個領域的數據也按同樣的方法處理。

本文所使用的郵件通信數據來源于國內某高校的電子郵件服務器日志，從中截取一段時間的數據作為測試數據。該日志包含的內容較為簡單，僅有郵件收發(fā)地址和郵件發(fā)送時間，通過將用戶視為節(jié)點、通信關系視為邊，可以構造出電子郵件用戶間的郵件通信關系網絡。取3周的郵件數據，第1周數據生成圖G0，第2周的數據生成圖G1，第 3周的數據生成圖G2。所有的圖均為有向圖。

3.2 實驗設計

實驗中考慮2種預測情況。第一種預測是預測完全新生成的邊，僅對那些在當前圖中沒有形成邊的節(jié)點對進行預測。作為弱分類器的預測算法有CN、JC、AA、RWR。為了與Liben-Nowell D相關工作作比較，參照其實驗數據設定，本文僅考慮活躍節(jié)點的鏈路預測問題。定義集合A是在G0、G1中度至少為3的節(jié)點的集合，集合B是在G1、G2中度至少為3的節(jié)點的集合。預測訓練集合為C：A×A-E0。預測測試集合是D：B×B-E1。

另一種預測是將節(jié)點間在當前時刻已存在邊的情況考慮在內的預測，對該時間段的圖中節(jié)點兩兩組合所有可能形成的節(jié)點對做預測。在這種情況下，如2.2節(jié)所述，加入Wuv作為弱分類器，它表示點u、v之間在當前圖中已經存在的邊的數目。在合作網絡中，表示二者在當前時間段已經合作的文章數目。在郵件網絡中，表示二者在當前時間段已經發(fā)送的郵件數目。作為預測訓練的集合是C：A×A，作為預測測試的集合是D：B×B。數據集合如表3所示。

表3 所有的數據集

3.3 實驗結果分析

接下來，展示本文提出的算法——ALP（adaBoost link prediction）在每個數據集上的表現，以及它同其他鏈路預測算法之間的比較。

3.3.1 問題評價方法

用來衡量鏈路預測算法的精確度指標一般有準確率、召回率和AUC(ROC曲線下的面積) 3種。準確率僅考慮對排在前Mbit的邊的預測是否準確。召回率僅考慮對所有標簽為真的樣本是否被預測為真。兩者相對來說評價都比較片面。而 AUC是從整體上來衡量算法的精確度[15]。AUC值同時反映了預測的準確率以及召回率。近年來鏈路預測工作的評價方法基本采用ROC圖和AUC值。

ROC圖像是一種對于靈敏度進行描述的功能圖像。一個二分類問題的結果要么是真（P），要么是假（N）。假如輸出的預測是 P而真實的結果也是 P，那么就叫做真陽性（TP）；但是如果真實的結果是N，就叫做假陽性（FP）。相對來說，一個真陰性發(fā)生在預測結果和實際結果都是N的時候，而假陰性是當預測輸出是N而實際值是P的時候。TPR決定了一個分類器在所有陽性樣本中能正確區(qū)分陽性案例的性能，即召回率，由式(9)計算。而FPR決定了在所有陰性的樣本中有多少假陽性的判斷，由式(10)計算。將假陽性率（FPR）作為x軸，真陽性率（TPR）作為y軸，就生成ROC曲線。每一個預測結果在ROC空間上以一個點代表，一組預測結果就會生成ROC曲線。ROC圖上從左下到右上的對角線表示一個完全隨機的預測。這條線也叫無識別率線。在這條線以上的點代表了一個好的分類結果，而在這條線以下的點代表了差的分類結果。AUC是ROC曲線的面積。AUC的值越大表示一個分類器的表現越好。本文采用ROC圖和AUC值來評測算法的精確度。

3.3.2 對網絡中新出現的邊進行預測

該預測僅對那些在當前圖中沒有形成邊的節(jié)點對進行預測。觀察合作網絡的Hep-th領域內的數據表現情況。按上述所說，使用1994～1999年的數據訓練出每個分類器的投票權重。在1997～2002年的數據上，對1997～1999年的數據依據之前的投票權重作出預測，在2000～2002年的數據上對預測結果做驗證。作為弱分類器的預測算法是 CN、JC、AA、RWR。最后將本文提出算法的預測結果與這幾種算法的預測結果做比較。各個算法的表現情況如圖3所示。

圖3 Hep-th 數據集上各算法的ROC曲線(對網絡中新出現的邊進行預測)

從圖3中可以看出，在對Hep-th領域內的數據集做預測時，幾乎所有的預測算法曲線都在無識別率線之上。按上節(jié)所說，ROC曲線越靠近左上角說明該算法的結果表現越好?？梢钥闯觯琑WR算法的預測表現最差，幾乎貼近無識別率線。算法CN、JC、AA的表現較為接近，它們的ROC曲線離無識別率線均有一定的距離，相對來說預測表現比RWR算法略好。本文所用的基于 AdaBoost的鏈路預測算法ALP的ROC曲線在其他曲線的上方。且離它們都有一定的距離。由此可見，在對Hep-th領域內的數據做預測時，該算法表現優(yōu)于其他算法，提高了鏈路預測的準確率和召回率。對于只預測新生成的邊的情況，各個數據集上每個算法的表現情況如表4所示。

表4 各個算法在5個數據集上的表現(僅對新出現的邊進行預測)

從表4中可以看到，對于表中所列的5種預測算法，在實驗所用的 5個數據集上。其 AUC值均在隨機猜測值 0.5之上，即它們的預測結果都高于隨機猜測。本文用作弱分類器的4種算法的表現相差不大。但是CN以及AA方法的AUC值較 JC和 RWR算法略高。而本文提出的算法ALP在合作網絡的 Cont-Mat領域數據集上表現最好，在郵件網絡上表現較差。但是無論是在論文合作網絡還是在電子郵件網絡數據集上，它的AUC值均高于其他算法，且存在一定的差值。實驗結果表明，該算法在提高了正確預測結果的同時，并沒有擴大預測范圍，同時提高了鏈路預測算法的準確度以及召回率。說明本文對于鏈路預測算法的改進是有效的。

3.3.3 對網絡中所有可能存在的邊進行預測

該預測是將節(jié)點對在當前圖中已存在邊的情況考慮在內，對該時間段的圖中節(jié)點兩兩組合所有可能形成的節(jié)點對做預測。筆者同樣對合作網絡的Hep-th數據集進行測試。按上述所說，使用1994～1999年的數據訓練出每個分類器的投票權重。在1997～2002年的數據上，對1997～1999年的數據依據之前的投票權重作出預測，在2000～2002年的數據上對預測結果做驗證。作為弱分類器的預測算法是CN、JC、AA、RWR、Wuv。同時這幾種算法的預測結果也用來和本文提出的算法 ALP的預測結果比較。各個算法的表現情況如圖4所示。

圖4 Hep-th數據集上各算法的ROC曲線（對網絡中所有可能存在的邊進行預測）

從圖4中可以看出，在對Hep-th領域內的數據做預測時，所有的預測算法的 ROC曲線都在無識別率線之上。其中，CN的表現相對較差，它的ROC曲線與無識別率線最為貼近。依次往上是算法RWR、JC、AA、Wuv，這幾種常用的鏈路預測算法的 ROC曲線離無識別率線都有一定的距離。但是相互間的間距都不大，沒有特別明顯的表現差異。圖 4最上方的 ROC曲線是本文中提出的基于AdaBoost的鏈路預測算法ALP，它離無識別率線的距離遠遠大于其他算法，且離圖中的左上方最為接近，可以看出它的預測表現是明顯優(yōu)于其他 5種用于比較的算法。由此可見，在對Hep-th領域內的數據做預測時，該算法表現遠優(yōu)于其他算法，提高了鏈路預測的準確率和召回率。

各個鏈路預測算法在本文所用的5個數據集上的表現如表 5所示，當考慮到已有合作或是已存在通信的情況進行鏈路預測時，在各個數據集上，所有的6種算法的AUC值均大于0.5。說明文中使用的鏈路預測算法都有一定的預測效果。觀察前面 5種用作比較得預測算法，可以看出，它們之間的預測表現得差異不大，算法Wuv的表現相對來說較為良好。在各個數據集上都略高于其他算法。說明作者間已經合作過或是實體間產生過通信對于在以后的時間中繼續(xù)合作以及繼續(xù)通信的可能性有很大的影響。本文提出的算法ALP在5個數據集上的AUC值都高于其他用作比較的5種算法。在Hep-th數據集上表現最好。在數據集Astro-ph上表現相對較差。在數據集 Email-Net上的預測效果與在合作網絡上的預測效果并無太大差異。說明本文提出的算法ALP具有一定的可適用性。該算法在預測中提高了正確預測結果，并且沒有擴大預測范圍。顯著提高了鏈路預測算法的準確度以及召回率。說明本文提出的對于鏈路預測算法的改進是有效的。

表5 各個數據集上每個算法的表現（對網絡中所有可能存在的邊進行預測）

該算法的運行時間與所選取的作為弱分類器的鏈路預測算法有關。在一個處理器為2.5 GB的電腦上運行Hep-th數據的時間約為30 min。

4 結束語

本文提出了一種基于 AdaBoost的鏈路預測算法。通過在真實的論文合作網絡和電子郵件網絡數據集上的仿真實驗結果表明，本文提出的鏈路預測算法相對于現有的各種常用算法而言具有更高的靈敏度和更低的誤報率，能夠在顯著提高算法召回率的同時，保持計算結果的正確性。本文的主要貢獻是將Boosting算法思想引入到鏈路預測領域，在以后的工作中，可以選取不同的弱分類器來改進算法，也可以考慮采用其他集成學習方法和手段來設計新型鏈路預測算法。

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

[2] LESKOVEC J, BACKSTROM L, KUMAR R,et al. Microscopic evolution of social networks[A]. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Las Vegas, Nevada, USA, 2008.462-470.

[3] MYERS S A, LESKOVEC J. On the convexity of latent social network inference[J]. Threshold, 2010,9:20.

[4] SUN Y, BARBER R, GUPTA M,et al. Co-author relationship prediction in heterogeneous bibliographic networks[A]. Advances in Social Networks Analysis and Mining (ASONAM)[C]. Kaohsiung, 2011.121-128.

[5] LARS BACKSTROM J L. Supervised random walks:predicting and recommending links in social networks[A]. WSDM'11[C]. Hong Kong,China, 2011.635-644.

[6] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008,453(7191): 98-101.

[7] LV L Y. Link prediction on complex networks[J]. Journal of University of Electronic Science and Technology of China, 2010, 9: 5-39.

[8] SCHAFER J L, GRAHAM J W. Missing data: our view of the state of the art[J]. Psychol Methods, 2002, 7(2):147-177.

[9] CHOWDHURY G. Introduction to Modern Information Retrieval,Third Edition[M]. Facet Publishing, 2010.

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

[11] TONG H H, FALOUTSOS C, PAN J Y. Fast random walk with restart and its applications[A]. Proceedings of the ICDM'06[C]. Washington,DC,USA, 2006.613-622.

[12] SHANG M S, LV L, ZENG W,et al. Relevance is more significant than correlation: information filtering on sparse data[J]. Europhys Lett,2009, 88(6): 68008.

[13] POLIKAR R. Ensemble based systems in decision making[J]. IEEE Circuits and Systems Magazine, 2006, 6(3):21-45.

[14] SCHAPIRE R E. The strength of weak learnability[J]. Machine Learning, 1990,5(2):197-227.

[15] BRADLEY A P. The use of the area under the ROC curve in the evaluation of machine learning algorithms[J]. Pattern Recognition,1997, 30(7): 1145-1159.