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

劉 英, 郭景濤

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

?

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

劉 英1，2*, 郭景濤3

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

算法：RankLearn輸入：R={r1，r2，…，rα}，排序列表集合；E，社會網(wǎng)絡(luò)中的已知邊；T，最終列表的長度；g，滑動窗口大??；輸出：結(jié)果列表L；初始化階段：?i，w[i]←ri中的前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個鏈接中找出一個預(yù)測最準(zhǔn)確的排序結(jié)果.為了實現(xiàn)上述思想，用wi作為排序器ri中包含前g個結(jié)果的滑動窗口，用x[i]作為wi中正確預(yù)測的鏈接個數(shù).在選取了最佳的鏈接后，將其加入到結(jié)果列表L中，并更新滑動窗口的索引值.對于最優(yōu)排序結(jié)果的計算，暴力搜索方法需要對所有的鏈接組合進行搜索，所需的時間復(fù)雜度為O(αN).本文通過局部搜索的方法尋找最優(yōu)的結(jié)果列表，每個排序器列表訪問一次，因此算法所需的時間復(fù)雜度僅為O(αN).

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

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

Tab.1 Instance of sort learning algorithm

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

2.1 數(shù)據(jù)集與評價指標(biāo)

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

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

2.2 對比算法

為了評價RankLearn算法的性能，實驗將RankLearn與一些經(jīng)典的鏈接預(yù)測算法進行了對比.

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

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

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

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

2.3 實驗結(jié)果

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

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

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

3 結(jié)束語

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

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

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

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

[4] 武南南. 時變網(wǎng)絡(luò)的鏈接預(yù)測研究[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]. 計算機學(xué)報, 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é)報,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