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

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

1 引言

鏈路預(yù)測(link prediction)問題源于復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域，目的是根據(jù)目標(biāo)網(wǎng)絡(luò)的觀測數(shù)據(jù)（節(jié)點和關(guān)系）預(yù)測該網(wǎng)絡(luò)中節(jié)點間可能存在的關(guān)系和將會產(chǎn)生的關(guān)系[1]。典型的鏈路預(yù)測問題解決方案包括優(yōu)先鏈接原則和森林火災(zāi)模型[2]。

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

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

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

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

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

表1 預(yù)測算法名稱及公式

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

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

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

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

圖1 CN和JC的預(yù)測范圍交集以及正確結(jié)果交集

2 算法設(shè)計

2.1 算法改進的依據(jù)

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

表2 每2個算法預(yù)測的正確結(jié)果的交集

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

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

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

2.2 弱分類器的選擇

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

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

圖2 已合作文章數(shù)目與再次合作概率關(guān)系

2.3 算法概述

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

算法1 ALP算法偽代碼

給定：長度為m的有著樣本標(biāo)簽yi∈Ω,Ω={-1,+1}的預(yù)測訓(xùn)練集合

Initialise Weights：

每個樣本最終預(yù)測結(jié)果為

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

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

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

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

3 實驗結(jié)果與討論

3.1 數(shù)據(jù)集

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

本文使用的數(shù)據(jù)集包括arXiv論文合作網(wǎng)絡(luò)中4個領(lǐng)域的數(shù)據(jù)以及一組電子郵件網(wǎng)絡(luò)數(shù)據(jù)。其中，論文合作網(wǎng)絡(luò)的數(shù)據(jù)使用scrapy爬蟲爬取。具體策略如下。

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

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

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

3.2 實驗設(shè)計

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

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

表3 所有的數(shù)據(jù)集

3.3 實驗結(jié)果分析

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

3.3.1 問題評價方法

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

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

3.3.2 對網(wǎng)絡(luò)中新出現(xiàn)的邊進行預(yù)測

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

圖3 Hep-th 數(shù)據(jù)集上各算法的ROC曲線(對網(wǎng)絡(luò)中新出現(xiàn)的邊進行預(yù)測)

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

表4 各個算法在5個數(shù)據(jù)集上的表現(xiàn)(僅對新出現(xiàn)的邊進行預(yù)測)

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

3.3.3 對網(wǎng)絡(luò)中所有可能存在的邊進行預(yù)測

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

圖4 Hep-th數(shù)據(jù)集上各算法的ROC曲線（對網(wǎng)絡(luò)中所有可能存在的邊進行預(yù)測）

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

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

表5 各個數(shù)據(jù)集上每個算法的表現(xiàn)（對網(wǎng)絡(luò)中所有可能存在的邊進行預(yù)測）

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

4 結(jié)束語

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

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