劉 英, 郭景濤

(1.內(nèi)蒙古大學(xué) 公共管理學(xué)院，內(nèi)蒙古 呼和浩特 010010;2.內(nèi)蒙古機(jī)電職業(yè)技術(shù)學(xué)院 信息與管理工程系，內(nèi)蒙古 呼和浩特 010070;3.內(nèi)蒙古大學(xué) 公共管理學(xué)院,內(nèi)蒙古 呼和浩特 010010)

?

基于排序?qū)W習(xí)的社會(huì)網(wǎng)絡(luò)鏈接預(yù)測(cè)算法研究

劉 英1，2*, 郭景濤3

(1.內(nèi)蒙古大學(xué) 公共管理學(xué)院，內(nèi)蒙古 呼和浩特 010010;2.內(nèi)蒙古機(jī)電職業(yè)技術(shù)學(xué)院 信息與管理工程系，內(nèi)蒙古 呼和浩特 010070;3.內(nèi)蒙古大學(xué) 公共管理學(xué)院,內(nèi)蒙古 呼和浩特 010010)

鏈接預(yù)測(cè)是大規(guī)模社會(huì)網(wǎng)絡(luò)分析挖掘的重要研究內(nèi)容之一，具有非常重要的應(yīng)用前景.社會(huì)網(wǎng)絡(luò)種類繁多，不同的網(wǎng)絡(luò)鏈接類型往往需要不同的鏈接預(yù)測(cè)方法.為了滿足用戶的個(gè)性化需求并提高鏈接預(yù)測(cè)的性能，該文提出了一種基于排序?qū)W習(xí)的社會(huì)網(wǎng)絡(luò)鏈接預(yù)測(cè)算法.該算法以傳統(tǒng)的鏈接預(yù)測(cè)方法為基礎(chǔ)，通過排序?qū)W習(xí)方法對(duì)不同的排序結(jié)果進(jìn)行學(xué)習(xí)，從而得到具有最大準(zhǔn)確性的綜合排序列表.在綜合排序列表的構(gòu)建中，在每個(gè)排序列表中設(shè)置一個(gè)滑動(dòng)窗口，通過對(duì)滑動(dòng)窗口的維護(hù)每次迭代選出一個(gè)全局最優(yōu)值，從而使得最終的排序列表是最優(yōu)的.實(shí)驗(yàn)表明，該文提出的算法與相關(guān)的鏈接預(yù)測(cè)算法相比較具有更高的預(yù)測(cè)性能,能找出一個(gè)預(yù)測(cè)最準(zhǔn)確的排序結(jié)果.

鏈接預(yù)測(cè)；排序?qū)W習(xí)；社會(huì)網(wǎng)絡(luò)；監(jiān)督學(xué)習(xí)

鏈接預(yù)測(cè)是大規(guī)模社會(huì)網(wǎng)絡(luò)分析挖掘的重要研究內(nèi)容之一，具有非常重要的應(yīng)用前景[1].在電子商務(wù)網(wǎng)站中，通過對(duì)用戶-商品二部圖中潛在的鏈接進(jìn)行預(yù)測(cè)，可以為用戶推薦商品，在提高商品銷售量的同時(shí)也提高了用戶對(duì)網(wǎng)站的粘性[2].在社會(huì)網(wǎng)絡(luò)服務(wù)中，通過用戶間的鏈接進(jìn)行預(yù)測(cè)可以進(jìn)行相似用戶的查詢以及好友的推薦，而用戶查詢和好友推薦是社會(huì)網(wǎng)絡(luò)服務(wù)最基本的服務(wù)內(nèi)容[3].在隨著時(shí)間演化的復(fù)雜網(wǎng)絡(luò)中，通過分析網(wǎng)絡(luò)中節(jié)點(diǎn)間的相似性，可以預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)變化，從而為復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)的研究提供基礎(chǔ)[4].此外，在信息不完全的網(wǎng)絡(luò)中，如移動(dòng)通信網(wǎng)絡(luò)，運(yùn)營商只有用戶間的通過記錄網(wǎng)絡(luò)，而沒有用戶的電話薄列表(即好友關(guān)系)，通過鏈接預(yù)測(cè)方法可以識(shí)別用戶的好友,從而為服務(wù)的推廣提供依據(jù)[5].

然而，上述鏈接預(yù)測(cè)方法往往適用于特定的社會(huì)網(wǎng)絡(luò).在不同的社會(huì)網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的鏈接表示不同的含義，如電子商務(wù)推薦中的鏈接表示用戶對(duì)商品的評(píng)價(jià)，社會(huì)網(wǎng)絡(luò)服務(wù)中的鏈接表示用戶間的好友關(guān)系，移動(dòng)通信網(wǎng)絡(luò)中的鏈接表示通話記錄等.在具體的社會(huì)網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的鏈接受網(wǎng)絡(luò)環(huán)境的影響，具有不同的角色，因而需要不同的鏈接預(yù)測(cè)方法.基于上述原因，研究人員在鏈接預(yù)測(cè)時(shí)同時(shí)考慮多種指標(biāo)(每種指標(biāo)對(duì)應(yīng)著相應(yīng)的計(jì)算方法)，并采用非監(jiān)督學(xué)習(xí)的方法對(duì)不同指標(biāo)下的結(jié)果進(jìn)行融合，如Borda方法[12]和馬爾科夫序列[13]等.

本文在對(duì)社會(huì)網(wǎng)絡(luò)中的鏈接進(jìn)行預(yù)測(cè)時(shí)同時(shí)考慮多種指標(biāo)，并采用有監(jiān)督的機(jī)器學(xué)習(xí)方法對(duì)不同指標(biāo)下的結(jié)果進(jìn)行融合.為了滿足用戶的個(gè)性化需求并提高鏈接預(yù)測(cè)的性能，本文提出了一種基于排序?qū)W習(xí)的社會(huì)網(wǎng)絡(luò)鏈接預(yù)測(cè)算法.該算法以傳統(tǒng)的鏈接預(yù)測(cè)方法為基礎(chǔ)，通過排序?qū)W習(xí)方法對(duì)不同的排序結(jié)果進(jìn)行學(xué)習(xí)，從而得到具有最大準(zhǔn)確性的綜合排序列表.在綜合排序列表的構(gòu)建中，在每個(gè)排序列表中設(shè)置一個(gè)滑動(dòng)窗口，通過對(duì)滑動(dòng)窗口的維護(hù),每次迭代選出一個(gè)全局最優(yōu)值，從而使得最終的排序列表是最優(yōu)的.

1 相基于排序?qū)W習(xí)的鏈接預(yù)測(cè)

在社會(huì)網(wǎng)絡(luò)中，用戶之間的鏈接有著不同的角色，如家庭成員、好友及同事等.通過對(duì)不同預(yù)測(cè)結(jié)果進(jìn)行相關(guān)性分析可以得出如下結(jié)論：通過某種方法預(yù)測(cè)到的鏈接在另外一種算法中可能不會(huì)出現(xiàn).本節(jié)采用有監(jiān)督的排序?qū)W習(xí)方法對(duì)不同預(yù)測(cè)結(jié)果進(jìn)行融合，在綜合多種指標(biāo)的優(yōu)勢(shì)下進(jìn)行鏈接的預(yù)測(cè).

在排序?qū)W習(xí)中，我們對(duì)α個(gè)排序器的結(jié)果列表集合R={r1,r2,…,rα}進(jìn)行學(xué)習(xí)，從而得到最優(yōu)的排序結(jié)果.算法的基本思想為：

(1) 對(duì)于每個(gè)排序器的結(jié)果列表ri，維持一個(gè)固定長度的滑動(dòng)窗口，令滑動(dòng)窗口的起點(diǎn)的索引為0，終點(diǎn)的索引為ρi，令f(ri)為ri中滑動(dòng)窗口ρi內(nèi)的正確預(yù)測(cè)的邊的個(gè)數(shù)，即

(1)

(3) 對(duì)于R中除ri以外的所有列表rj，如果rj的滑動(dòng)窗口ρj中含有rmax，那么移除rmax并相應(yīng)的更新ρj的起點(diǎn)和終點(diǎn)索引值.

(4) 更新R中所有列表的f(ri)值.

(5) 重復(fù)第2至4步，直到最終的結(jié)果列表包含所需的結(jié)果個(gè)數(shù)T.

如果在進(jìn)行排序?qū)W習(xí)前共包含α個(gè)排序器，最終得到的包含T個(gè)結(jié)果的列表為L，那么上述方法的目標(biāo)是最大化結(jié)果列表中的正確預(yù)測(cè)個(gè)數(shù)，即

其中l(wèi)i∈{0,1}為L中第i個(gè)結(jié)果對(duì)應(yīng)的預(yù)測(cè)結(jié)果.在上述方法中，每個(gè)結(jié)果只能預(yù)測(cè)一次，當(dāng)某個(gè)預(yù)測(cè)結(jié)果第一次出現(xiàn)時(shí)，刪除其在其他結(jié)果列表中的出現(xiàn).該思想的依據(jù)是：最終的預(yù)測(cè)結(jié)果中的每一項(xiàng)都來自于其對(duì)應(yīng)的最優(yōu)排序器，這樣使得最終的結(jié)果列表也是最優(yōu)的.該算法的細(xì)節(jié)如下：

算法：RankLearn輸入：R={r1，r2，…，rα}，排序列表集合；E，社會(huì)網(wǎng)絡(luò)中的已知邊；T，最終列表的長度；g，滑動(dòng)窗口大?。惠敵觯航Y(jié)果列表L；初始化階段：?i，w[i]←ri中的前g個(gè)鏈接；?i，x[i]=w[i]∩E，ρ[i]=0，σ[i]=g；n=0；循環(huán)階段：Whilen≤Tdoimax←x[i]的最大索引；L[n]=R[imax][ρ[imax]]；n=n+1；ρ[imax]=ρ[imax]+1；For?ido Ifl[n]∈w[i]，thenw[i]=w[i]l[n]； Whilew[i]≤gdo l=R[i][σ[i]]； σ[i]=σ[i]+1； Ifl?Lthenw[i]=w[i]+1； Endwhilex[i]=w[i]∩E；Endwhile

RankLearn算法的思想是，在每一次迭代中，在α個(gè)排序器的前g個(gè)鏈接中找出一個(gè)預(yù)測(cè)最準(zhǔn)確的排序結(jié)果.為了實(shí)現(xiàn)上述思想，用wi作為排序器ri中包含前g個(gè)結(jié)果的滑動(dòng)窗口，用x[i]作為wi中正確預(yù)測(cè)的鏈接個(gè)數(shù).在選取了最佳的鏈接后，將其加入到結(jié)果列表L中，并更新滑動(dòng)窗口的索引值.對(duì)于最優(yōu)排序結(jié)果的計(jì)算，暴力搜索方法需要對(duì)所有的鏈接組合進(jìn)行搜索，所需的時(shí)間復(fù)雜度為O(αN).本文通過局部搜索的方法尋找最優(yōu)的結(jié)果列表，每個(gè)排序器列表訪問一次，因此算法所需的時(shí)間復(fù)雜度僅為O(αN).

下面通過一個(gè)具體的實(shí)例對(duì)算法的執(zhí)行過程進(jìn)行闡述.給定rA和rB兩個(gè)排序列表，令g=5，表1通過3個(gè)子表描述了算法的兩次迭代過程.其中rA和rB兩個(gè)列表中上部分邊的出現(xiàn)概率大于下面的邊，例如p(1,2)≥p(1,4)；當(dāng)rA=(1,2)時(shí)，tp=0，這表明雖然邊(1,2)出現(xiàn)的概率最大，但是在未來仍沒有出現(xiàn).初始時(shí)，在rA和rB中分別取長度為5的滑動(dòng)窗口(見表1(a)中的灰度部分)，計(jì)算可得f(rA)=4和f(rB)=3，并選取(1,2)作為最終列表中的第一項(xiàng).在第一次迭代過程中，刪除rB中的(1,2)項(xiàng)(用下劃線表示)并更新滑動(dòng)窗口，此時(shí)有f(rA)=4和f(rB)=4.在第二次迭代過程中，刪除rA中的(5,18)項(xiàng)，更新滑動(dòng)窗口，并將(5,18)加入到最終的排序列表中.經(jīng)過兩次迭代后，排序列表L={(1,2),(5,18)}.

表1 排序?qū)W習(xí)算法的實(shí)例

Tab.1 Instance of sort learning algorithm

2 實(shí)驗(yàn)結(jié)果與分析

2.1 數(shù)據(jù)集與評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)采用公開的DBLP[14]社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集.DBLP數(shù)據(jù)集是學(xué)者學(xué)術(shù)合作數(shù)據(jù)集，包含1990年至2004年間關(guān)于計(jì)算機(jī)領(lǐng)域的學(xué)術(shù)文章發(fā)表情況.該數(shù)據(jù)集包含540 459篇發(fā)表的文章以及1 564 617個(gè)作者.在實(shí)驗(yàn)過程中，應(yīng)用1990年至2000年共11年的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，并用余下4年的數(shù)據(jù)作為測(cè)試算法性能的數(shù)據(jù).

在評(píng)價(jià)算法的性能時(shí)，采用了信息檢索領(lǐng)域常用的評(píng)價(jià)指標(biāo)，包含查準(zhǔn)率、召回率和F值，關(guān)于這些指標(biāo)的詳細(xì)定義可參見文獻(xiàn)[15].

2.2 對(duì)比算法

為了評(píng)價(jià)RankLearn算法的性能，實(shí)驗(yàn)將RankLearn與一些經(jīng)典的鏈接預(yù)測(cè)算法進(jìn)行了對(duì)比.

Borda算法[12]：該算法將不同排序方法得到的結(jié)果進(jìn)行融合，采用投票的方法以便在結(jié)果中達(dá)成共識(shí)，是一種非監(jiān)督的學(xué)習(xí)方法.

最近鄰算法(Nearest Neighbors，NN)：NN算法是一種簡單的基于局部鏈接結(jié)構(gòu)的方法，該算法通過節(jié)點(diǎn)的最近鄰來計(jì)算節(jié)點(diǎn)間的相似性.

AdaBoost(AB)算法[7]：AB算法是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的弱分類器，然后把這些弱分類器集合起來，構(gòu)成一個(gè)更強(qiáng)的最終分類器.

分類樹算法(Classification Trees，CT)[9]：CT算法通過決策樹思想構(gòu)建一個(gè)分類器，并應(yīng)用得到的分類器對(duì)鏈接進(jìn)行預(yù)測(cè).

2.3 實(shí)驗(yàn)結(jié)果

首先，通過實(shí)驗(yàn)分析了上述5種算法在鏈接預(yù)測(cè)時(shí)的整體性能.在實(shí)驗(yàn)中，令RankLearn算法的g=300，關(guān)于g的取值的分析見下文.在實(shí)驗(yàn)結(jié)果的展示中，預(yù)測(cè)結(jié)果的查詢率-召回率分布如圖1所示.從圖中可以看出，當(dāng)要求預(yù)測(cè)結(jié)果的召回率很小時(shí)，AB算法具有最高的查準(zhǔn)率，然而由于召回率低導(dǎo)致大部分正確結(jié)果沒有被返回.當(dāng)召回率逐漸提高時(shí)，RankLearn和Borda算法的曲線始終處于右上方，這表明這兩種算法具有更好的檢索性能.此外，在RankLearn和Borda的對(duì)比中，RankLearn算法的檢索性能要優(yōu)于Borda算法.

接下來，通過改變算法返回的預(yù)測(cè)結(jié)果個(gè)數(shù)來觀察不同算法的F值變化，實(shí)驗(yàn)結(jié)果如圖2所示.由于F值綜合考慮了檢索結(jié)果的查準(zhǔn)率和召回率，因而能代表檢索結(jié)果的性能.同樣令RankLearn算法的g=300，從該圖中可以看出，RankLearn和Borda算法的曲線始終處于其他三種算法的上方，并且RankLearn算法處于Borda算法的上方，因而可以認(rèn)為RankLearn算法的檢索性能是最好的，Borda算法次之.

最后，通過實(shí)驗(yàn)分析了RankLearn算法的滑動(dòng)窗口大小g對(duì)算法性能的影響.在圖3和圖4中，橫軸為滑動(dòng)窗口的大小g，縱軸為RankLearn算法的F值相對(duì)于Borda算法的F值的提高百分比，負(fù)值表示RankLearn算法的F值 低于Borda算法的F值.圖3和圖4分別為RankLearn算法在訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集中相對(duì)于Borda算法的性能提高程度.從這兩幅圖中可以看出，無論在訓(xùn)練數(shù)據(jù)集還是測(cè)試數(shù)據(jù)集上，RankLearn算法的F值相對(duì)于Borda算法都有所提高，并且在200至400處取到最大值.

3 結(jié)束語

鏈接預(yù)測(cè)是大規(guī)模社會(huì)網(wǎng)絡(luò)分析挖掘的重要研究內(nèi)容之一，然而社會(huì)網(wǎng)絡(luò)種類繁多，不同的網(wǎng)絡(luò)鏈接類型往往需要不同的鏈接預(yù)測(cè)方法.本文在對(duì)社會(huì)網(wǎng)絡(luò)中的鏈接進(jìn)行預(yù)測(cè)時(shí)同時(shí)考慮多種指標(biāo)，采用有監(jiān)督的機(jī)器學(xué)習(xí)方法對(duì)不同指標(biāo)下的結(jié)果進(jìn)行融合，提出了一種基于排序?qū)W習(xí)的社會(huì)網(wǎng)絡(luò)鏈接預(yù)測(cè)算法.該算法以傳統(tǒng)的鏈接預(yù)測(cè)方法為基礎(chǔ)，通過排序?qū)W習(xí)方法對(duì)不同的排序結(jié)果進(jìn)行學(xué)習(xí)，從而得到具有最大準(zhǔn)確性的綜合排序列表.在綜合排序列表的構(gòu)建中，在每個(gè)排序列表中設(shè)置一個(gè)滑動(dòng)窗口，通過對(duì)滑動(dòng)窗口的維護(hù)每次迭代選出一個(gè)全局最優(yōu)值，從而使得最終的排序列表是最優(yōu)的.實(shí)驗(yàn)表明，本文提出的算法與相關(guān)的鏈接預(yù)測(cè)算法相比較具有更高的預(yù)測(cè)性能.

[1] 胡海波, 王科, 徐玲, 等. 基于復(fù)雜網(wǎng)絡(luò)理論的在線社會(huì)網(wǎng)絡(luò)分析[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2008, 5(2): 1-14.

[2] 朱巖, 林澤楠. 電子商務(wù)中的個(gè)性化推薦方法評(píng)述[J]. 中國軟科學(xué), 2009 (2): 183-192.

[3] 張中峰, 李秋丹. 社交網(wǎng)站中潛在好友推薦模型研究[J]. 情報(bào)學(xué)報(bào), 2012, 30(12): 1 319-1 325.

[4] 武南南. 時(shí)變網(wǎng)絡(luò)的鏈接預(yù)測(cè)研究[D].重慶： 重慶大學(xué), 2012.

[5] JANICIK G A, LARRICK R P. Social network schemas and the learning of incomplete networks[J]. Journal of Personality and Social Psychology, 2005, 88(2): 348.

[6] LIBEN-NOWELL D, KLEINBERG J. The link-prediction problem for social networks[J]. JASIST, 2007, 58(7):1 019-1 031.

[7] Al HASAN M, CHAOJI V, SALEM S, et al. Link prediction using supervised learning[C]. SDM’06: Workshop on Link Analysis, Counter-terrorism and Security, 2006.

[8] BROUARD C, SZAFRANSKI M. Semi-supervised penalized output kernel regression for link prediction[C]. Proceedings of the 28th International Conference on Machine Learning (ICML-11), 2011: 593-600.

[9] FENG X, ZHAO J C, XU K. Link prediction in complex networks: a clustering perspective[J]. The European Physical Journal B,2012, 3(85):1-9.

[10] MENON A K, ELKAN C. Machine learning and knowledge discovery in databases[M]. Springer Berlin Heidelberg, 2011:437-452.

[11] LIU W, Lü L. Link prediction based on local random walk[J]. EPL (Europhysics Letters), 2010, 89(5): 58 007.

[12] DWORK C,KUMAR R,NADR M, et al. Rank aggregation methods for the web[C].In WWW’01, ACM, 2001：613-622.

[13] 陳彥萍, 李增智, 唐亞哲, 等. 一種滿足馬爾可夫性質(zhì)的不完全信息下的 Web 服務(wù)組合方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2006, 29(7): 1 076-1 083.

[14] Al HASAN M, CHAOJI V, SALEM S, et al. Link prediction using supervised learning[C]. SDM’06: Workshop on Link Analysis, Counter-terrorism and Security,2006.

[15] MANNING C D, RAGHAVAN P, SCHüTZE H. Introduction to information retrieval[M]. Cambridge: Cambridge University Press, 2008.

[16] 曹建芳,陳俊杰,楊燦.面向自然語言理解的圖像情感語義檢索[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào),2014,29(2):81-85.

責(zé)任編輯：龍順潮

Learning to Rank Based Link Prediction Algorithm in Social Networks

LIUYing1，2*，GUOJing-tao3

(1.Public Management College,Inner Mongolia University, Hohhot 010010;2.Information Technology and Management Engineering Department,Inner Mongolia Technical College of Mechanics and Electrics，Hohhot 010010;3.Public Management College,Inner Mongolia University,Hohhot 010010 China)

Link prediction is one of the most important research issues for mining and analyzing large-scale social networks, and is ubiquitous in many applications. There are kinds of social networks, and different types of link need different methods for link prediction. In order to satisfy personalized user requests and improve the performance of link prediction, this paper proposed a learning to rank based link prediction algorithm in social networks. Based on traditional link prediction methods, the proposed algorithm tried to learn a final list with maximized accuracy from existing ranking list. On the constructing of the final list, we set and maintained a slide window for each ranking list, and at each iteration, chose a global optimum from all slide windows, which made sure that the final list was optimum. The experiments show that, the proposed algorithm has better performance in link prediction than related works.

link prediction; learning to rank; social networks; supervised learning

2015-02-08

內(nèi)蒙古自治區(qū)教育廳課題(NJ274)

劉英(1981— ),女，內(nèi)蒙古 烏蘭察布人，講師.E-mail:478345761@qq.com

TP319

A

1000-5900(2015)03-0120-07