基于分布式圖計算框架的好友推薦算法研究

趙馬沙　周　薇　張　豪　韓冀中

1(中國科學院信息工程研究所信息智能處理技術研究室　北京 100093)2(中國科學院大學　北京 100049)3(重慶郵電大學通信與信息工程學院　重慶 400065)

?

基于分布式圖計算框架的好友推薦算法研究

趙馬沙1,2周薇1,2張豪3韓冀中1

1(中國科學院信息工程研究所信息智能處理技術研究室北京 100093)2(中國科學院大學北京 100049)3(重慶郵電大學通信與信息工程學院重慶 400065)

摘要隨著社交網絡的興起與發展，用戶數目規模呈現出指數級增長的趨勢。這些大規模數據里蘊含著許多有價值的信息，挖掘其中有用的信息已經成為學者研究的重點，好友推薦就是數據挖掘里的一個重要應用。為了獲得更優的性能、更高的可擴展性，采用分布式平臺解決大規模好友推薦成為學術界和工業界的一個發展趨勢。目前使用得較廣泛的為基于MapReduce框架的好友推薦算法，該方法有較高的可擴展性，但是受限于MapReduce低效的中間數據傳輸，存在性能缺陷。針對上述問題，提出一種基于分布式圖計算框架的好友推薦算法。最后，在多個真實的社交網絡數據集上評測了該方法。實驗結果表明，該方法要優于業界先進的好友推薦算法，在準確率相當的情況下，性能大約為其他算法的7倍。

關鍵詞好友推薦分布式圖計算框架隨機游走

0引言

隨著Web2.0的出現及興起，社交網絡得到了蓬勃發展，用戶數越來越多。2014年一月份的調查表明[1]，Twitter[2]每月的平均活躍用戶人數高達2.41億。2014年5月，QQ空間官方聲稱其每月的平均活躍用戶高1.2億。這些大規模數據里蘊藏著許多潛在的有價值信息，而挖掘其中的有用信息已經成為業界學者的一個研究重點。其中好友推薦[3]就是數據挖掘[4]的一個非常重要的應用，目前已經被廣泛地應用在各類社交網站上。

目前的好友推薦算法主要分為兩種[5]，一種是基于局部信息的，比如已經被廣泛應用于社交網絡的二度人脈(好友的好友)好友推薦。這種基于局部信息的算法計算復雜度低，運行消耗的時間少，但因其利用的信息量少，所以準確率不高。第二種是基于全局信息的好友推薦算法，算法通常會偵測整個社會圖的所有路徑結構，由于其利用了更多的信息，所以推薦結果更加準確。但是對于大規模的在線社交網絡來說，這類方法的計算成本相當高，不適用實時推薦。

針對以上缺陷，有學者提出了基于局部隨機游走的好友推薦算法[6]。它根據“小世界”理論[7]，隨機游走有限范圍內的所有路徑，為用戶提供了既快速又準確的朋友推薦。

為了應對日益增長的社交網絡數據，分布式好友推薦算法也得到了研究學者的青睞。目前使用得較為廣泛的是基于MapReduce的大規模好友推薦算法[8]。該算法擁有較高的可擴展性，能應對日益增長的社交網絡數據。但由于MapReduce框架中間數據的持久化機制，在其上實現的好友推薦算法性能較低。

針對以上問題，本文提出一種基于分布式圖計算框架的好友推薦方法。該方法結合了局部隨機游走和分布式圖計算框架，實現了好友推薦迭代計算，中間數據采用消息傳遞的模式，減少了數據持久化的代價。最后，在分布式集群下評測了本文提出的方法，使用多個真實的大規模社交網絡公開數據集。實驗結果表明，該方法在性能上比單機的好友推薦算法提高了4倍，比基于MapReduce框架的算法提升了7倍，并且該算法具有較高的可擴展性，隨著集群規模的增長成正比增長。

1相關工作

好友推薦算法有很多，社會學中的同質性理論認為，擁有相同愛好的人更可能成為朋友，所以很多社交平臺通過用戶屬性的相似度來推薦好友[9,10]。比如百度利用用戶的愛好等屬性推薦朋友。

還有一種方法就是利用好友關系的網絡拓撲圖[11]，主要有兩類：一類是基于社會網絡結構的局部特性，比如二度人脈FOAF(FriendofaFriend)的方法[12]。它基于這樣的現象：如果兩個人有很多共同的朋友，那么他們在將來就很有可能成為朋友。由于FOAF的簡單高效，所以Facebook、騰訊QQ等均采用它為用戶推薦潛在好友。但是，這種基于網絡局部特性的方法由于利用的信息不充分，得到的結果往往不是很準確。另一類方法是基于社會網絡的全局特性，探索社會網絡圖中的所有路徑結構，比如經典的Google網頁排序算法PageRank[13]，利用了整個圖結構的信息。雖然這種算法提高了結果的準確性，但是在現實的社交網絡中，用戶數目通常是上百萬、千萬甚至是億，運行這種算法成本太大，消耗的時間太多，也不適合應用在實時推薦上。

為了解決上述問題，有學者提出了一個基于局部隨機游走的好友推薦算法。這個方法考慮了更多的鄰居信息，具有更高的準確性；同時比起基于全局的方法，由于無需遍歷整個社會圖，因此其具有更低的時間復雜度。

上述所有的方法都是為單機而設計的，當社交網絡用戶數增多，面對復雜的大規模好友推薦時，就會出現計算效率的問題，而且不具有很好的可擴展能力。于是一些學者開始研究可擴展的分布式好友推薦算法，通過集群的計算能力來應對大規模數據帶來的挑戰。文獻[14]提出了基于MapReduce框架的分布式好友推薦方法，該方法采用MapReduce的Key-Value結構實現了二度人脈等好友推薦算法[15]。盡管MapReduce具有較高的可擴展性，但是其低效的中間數據共享方式導致了該方法的性能不高。

2相關背景

2.1BSP模型

大同步并行BSP(BulkSynchronizationParallel)模型是由哈佛大學Valiant和牛津大學BillMcColl提出的并行計算模型。BSP模型是一種包含一個主節點和多個從節點的分布式的模型。每個從節點負責處理圖中的一個子圖，作業的處理是由迭代的過程組成，每次迭代稱為一個超步。超步是在數據處理中的最小計算單位，主要包括三個階段：并行計算、通信和柵欄同步，如圖1所示。

圖1　BSP超步的三個階段

1) 本地計算階段，每個節點只處理本節點維護的數據。

2) 全局通信階段，每個節點將本地計算的結果發送給鄰居節點。

3) 柵欄同步階段，等待所有通信行為結束。

在一個確定的超步中，一個從節點只有在上一個超步中接收到所有來自相鄰頂點的消息才可以處理這一個頂點。此外，該系統只有所有圖頂點都處理完畢之后才進行下一個超步。

目前，很多公司已經開發了許多基于BSP模型的圖數據處理系統，最著名的就是Google發明的Pregel[16]。Pregel是一種面向圖算法的分布式編程框架，采用迭代的計算模型。在每一輪，每個頂點處理上一輪收到的消息，并給相鄰頂點發消息，更新自身狀態和拓撲結構(出、入邊)等。類似的還有Apache的Hama[17]，它是Hadoop[18]生態系統中的一個子項目，兼容很多Hadoop的分布式存儲系統，如HDFS、HBase等。

由于Pregel并非開源，我們基于Pregel的思想實現了BSP圖計算框架[19]，本文的實驗也是運行在該框架上。與Pregel類似，BSP圖計算框架首先將圖分割為頂點不相交的子圖并將各個子圖分配到計算節點上，BSP圖計算框架的計算過程基于BSP模型實現。計算被分為多個超步，每一超步中各個計算節點依次調用各個頂點的更新函數。在頂點更新函數中，每個頂點可以根據所收到的上一輪的消息更新該頂點的狀態并產生本輪發送給其他頂點的消息。待所有圖頂點均更新完畢且所有消息均已到達目標節點，各計算節點進行柵欄同步并同時進入下一超步。這一過程循環往復直至所運行的算法達到收斂條件。因此，基于BSP框架實現圖算法時，主要工作是通過編寫頂點狀態更新函數來完成的。

2.2基于局部隨機游走的好友推薦算法

基于局部隨機游走的頂點間相似性是一個在社會圖的基礎上定義的相似性指標。

首先給出社會圖的定義，社會圖是一個由頂點集合和邊集合構成的社會網絡，頂點代表用戶，邊代表用戶之間的關系，兩者之間構成一個圖。

正式地，根據圖理論定義社會圖G=(V，E)，其中V表示頂點集合，也就是用戶集合，E表示無向邊集合，也就是用戶之間的關系。僅當兩個頂點vi、vj間的無向邊(vi，vj)∈E時，vj(vi)被稱為vi(vj)的鄰接。這樣社會圖能夠表示為鄰接矩陣A=(aij)∈E，如果vi和vj為朋友，則aij=1，否則為0。

(1)

20世紀60年代，美國著名社會心理學家Milgram提出了“小世界”理論。理論指出：你和任何一個陌生人之間所間隔的人不會超過五個，也就是說，最多通過五個中間人你就能夠認識任何一個陌生人。這個理論已經被應用到了很多的領域，局部隨機游走算法的思想就是根據“小世界”假說，在社會圖上進行有限長度的隨機游走，而不是針對整個社會圖進行全局地遍歷[20]。

(2)

其中L代表圖頂點vi、vj之間隨機游走的路徑長度，根據“小世界”理論，可取2到6之間的整數，E為社會圖中邊的總數目，Γ(j)是頂點vj的度，代表頂點的流行度，流行度指數β是一個可變參數，調節頂點vj的流行度對相似度的影響，實驗證明β取0.5時得出的結果最理想。

學者還通過大量的實驗證明，在準確性上，基于局部隨機游走的好友推薦算法高于基于二度好友的方法，甚至高于基于全局的推薦算法。基于全局的推薦算法雖然對社會網絡進行全局遍歷，但其沒有充分地捕獲圖中頂點(用戶)的局部信息[21]。而基于局部隨機游走的好友推薦算法根據“小世界”假設，更加注重頂點(用戶)附近鄰居的作用，充分利用了用戶局部信息，所以它的準確性能夠高于基于全局的好友推薦方法。在性能上，基于局部隨機游走的好友推薦算法遠高于基于全局的推薦算法。

3基于圖計算框架的好友推薦算法

本節描述了本文提出的一種基于分布式圖計算框架的好友推薦方法。首先介紹該方法并行化的原理，然后以算法的形式詳細介紹了圖計算迭代完成好友推薦的3個階段：初始化階段、迭代階段以及結束階段。

3.1原理

首先分析式(1)，轉移概率矩陣Q就是圖中頂點之間互相轉移的概率。如圖2所示，aij代表頂點i到頂點j的轉移概率，也就是下一步從頂點i到頂點j的概率。矩陣中每一行代表某一個頂點到其他頂點的轉移概率，根據矩陣元素的計算公式，可以得到結論。如果頂點i和頂點j無邊，轉移概率則為0，如果有邊，轉移概率就是頂點i包含的邊的倒數。

圖2概率轉移矩陣Q

式(1)中出現了Q的轉置，轉置矩陣如圖3所示。

圖3概率轉移矩陣Q的轉置

從圖3可以看出，轉置后的矩陣中，每一行代表其他頂點到該頂點的轉移概率。

[pi0pi1pi2…pin]

圖5是一個列向量，每一個元素是由n個加數相加得到。對每個加數ajk×pij，分析其意義，pij為頂點i經過t-1步到達頂點j的概率，ajk為頂點j到達頂點k的概率，兩者相乘即為頂點i經過t步到達頂點k的一部分概率，而所有的加數相加就代表頂點i經過t步到達頂點k的概率。通過這種形式化的分析，我們就可以理解式(1)了。

3.2算法

在BSP上實現分布式的局部隨機游走算法分為3個階段，分別為初始化階段、迭代階段和結束階段：

1) 初始化階段：根據輸入的圖數據文件，遍歷文件中的每一行，在BSP中生成頂點對象，然后記錄每個頂點的邊。

算法1初始化圖數據

輸入：圖數據文件file

1：foreachlineinfiledo

2：vertex←createVertex(line)

//line是文件file的每一行數據，vertex是BSP框架中的頂點對象

3：edges←getEdges(vertex)

//edges是存儲頂點所有的邊

4：endforeach

5:return

2) 迭代階段：BSP框架控制每個頂點運行該階段，首先頂點會接受每一條邊發過來的消息，得到其中的值。然后計算p值，如果迭代次數沒有達到指定次數，則繼續發消息，再次迭代，如果達到指定次數，則停止。

算法2迭代階段

輸入：頂點vertex，頂點的邊edges，迭代的次數turn

1：foreachedgeinedgesdo

2：dstVertex←getDstVertex(edge)

//dstVertex是目標頂點

3：value←getMessage(dstVertex)

//value是邊的權值

4：values.add(value)

5：endforeach

6：p←calculate(vertex,value)

7：ps.add(p)

8：ifturn<=STEPthen

//如果迭代次數小于STEP，繼續發消息

9：foreachedgeinedgesdo

10：dstVertex←getDstVertex(edge)

11：sendMessage(dstVertex,p)

//把p值發給每條邊

12：values.add(value)

13：endforeach

14：elsehalt()

3) 結束階段：每個頂點計算得到p值后，BSP框架計算出每個頂點和目標頂點的相似度sin，然后把所有的sin存儲sins集合中，最后集合匯總對所有的sin進行排序，最后按照相似度從大到小輸出。

算法3結束階段

輸入：各頂點的ps

輸出：各頂點的相似度，從大到小輸出

1：foreachvertexdo

2：sin←getSin(ps)

//sin就是相似度的值

3：sins.add(sin)

//sins存儲所有頂點的相似度

4：endforeach

5：printsort(sins)

//輸出排序的結果

6：return

4實驗結果

4.1測試數據集和實驗環境

為了評測本文方法的有效性，本文選取兩個好友推薦對比系：單機的局部隨機游走算法和基于MapReduce的二度人脈好友推薦算法。并在多個真實公開的數據集上做了評測實驗，和單機的局部隨機游走算法比較。一方面證明本文提出的分布式算法是正確的，另一方面說明分布式的算法能帶來很大的性能提升，從而可以應付日益增長的大數據集帶來的挑戰。和如今被很多公司廣泛用到的二度人脈算法比較，說明本文提出的算法比現在流行的算法擁有更高的性能，可以在實際中應用。實驗環境是由4臺主機組成的集群，具體硬件配置參數如表1所示。

表1　實驗環境

在數據集的選取上，本著真實公開和全面的原則，選擇了5個不同大小的數據，如表2所示。所有的數據來源各社交網站里，從law.di.unimi.it/datasets.php下載，由WebGraph和LLPprojects提供。這5個數據集的規模是從小到大增長的，很好地說明了本文提出的方法擁有很好的擴展性。其次從數據集中頂點的平均邊數也可以看出每個圖的稀疏程度不同，說明本文提出的方法適用面廣泛。

表2　實驗數據集

4.2和單機的局部隨機游走算法比較

首先我們對分布式算法和單機算法的結果進行了比較，實驗表明兩種算法中相同頂點的相似度都是一樣的，所以局部隨機游走算法的分布式版本是正確的。

接下來，我們測試了單機算法和分布式算法運行的時間，數據如表3所示。

表3　分布式和單機時間對比

由表3得出的時間對比圖如圖6所示，橫坐標是測試數據集中頂點的個數(大致)，萬為單位，縱坐標是算法運行的時間，秒為單位。

圖6　單機和并行算法時間對比圖

由圖或者表中的數據可以看出，數據量小的時候，分布式算法時間要消耗得更多一些，這是因為并行框架本身要消耗資源和時間，并行帶來的性能還沒有彌補框架損失的性能。但隨著數據集的增大，很明顯，分布式的時間比單機版本消耗的時間要少，性能大約提升了四倍，而且性能的提升程度和集群的大小是成正比的。

4.3和MapReduce的二度人脈算法比較

在分布式好友推薦算法中，基于MapReduce的二度人脈好友推薦算法使用得較廣泛，Facebook和Hi5等OSNs就使用了該方法進行好友推薦，來自于Facebook的數據科學家LarsBackstrom在eswc2011的報告[22]中介紹了他們是如何利用二度人脈的算法來為用戶推薦朋友。下面就BSP上的局部隨機游走算法和MapReduce上的二度人脈算法進行比較。首先看兩個算法的推薦效果。采用MeanReciprocalRank(MRR)值作為測試指標，在原來的數據圖中刪除某頂點的10個好友，然后分別用這兩個算法試圖把刪去的10個好友推薦回來，比較這十個好友的MRR值，結果如表4所示。

表4　MRR值對比

由于數據量很大，一個頂點的邊有很多，所以得到的MRR值非常小。由表4可以看出，BSP的MRR值比MapReduce的MRR值要大，可以得出結論，BSP上的局部隨機游走算法的推薦是更準確的。

接下來，比較兩者的計算時間，數據如表5所示。

表5　兩個并行算法時間對比

圖7是表5中數據的折線圖顯示，橫坐標是測試數據集頂點的個數，單位為萬，縱坐標是算法運行的時間，單位為秒。

圖7　單機和并行算法時間對比圖

由圖7可以看出MapReduce上的二度人脈的性能遠遠不如BSP上的局部隨機游走算法的性能，主要原因是并行框架的差異，BSP適合迭代圖數據計算，中間消息采用消息傳遞，而不是通過文件系統存儲中間結果。而MapReduce框架的啟動代價比較大，并且中間的結果是存儲在本地磁盤中，從而每次計算會產生大量的IO操作，所以抑制了性能。

5結語

本文首先提出了一種基于分布式圖計算框架的好友推薦方法，然后通過大量的實驗證明了該方法的高效性和可擴展性。實驗中，首先和單機的局部隨機游走算法進行了比較，證明了分布式的算法能夠帶來很大的性能提升，從而可以通過增加普通集群的方式來應付大數據帶來的挑戰。接著又和現在流行的二度人脈算法進行了比較，證明了本文提出的算法具有很高的應用價值。為了進一步提高本文方法的適用面，未來我們的工作主要集中在優化好友推薦算法上。

參考文獻

[1]SocialNetworkService[EB/OL].http://newsroom.fb.com/Key-Facts.

[2]HaewoonKwak,ChanghyunLee,HosungPark,etal.WhatisTwitter,asocialnetworkornewsmedia?[C]//Proceedingsofthe19thInternationalConferenceonWorldWideWeb,2010:591-600.

[3]IdoGuy,InbalRonen,EricWilcox.Doyouknow?:recommendingpeopletoinviteintoyoursocialnetwork[C]//Proceedingsofthe14thinternationalconferenceonIntelligentuserinterfaces,February08-11,2009:77-86.

[4]MarkHall,EibeFrank,GeoffreyHolmes,etal.Thewekadataminingsoftware:anupdate[J].ACMSIGKDDexplorationsnewsletter,2009,11(1):10-18.

[5] 王兵輝.社交網絡中潛在好友推薦算法研究[D].云南大學,2013.

[6] 俞琰,邱廣華.基于局部隨機游走的在線社交網絡朋友推薦算法[J].系統工程,2013,31(2):47-54.

[7] 佟婷婷,宋藝.小世界理論及其在Internet中的應用[J].企業技術開發,2010,29(1):26-27.

[8] 楊婷.基于MapReduce的好友推薦系統的研究與實現[D].北京郵電大學,2013.

[9] 楊長春,楊晶,丁虹.一種新的新浪微博好友推薦算法[J].計算機應用與軟件,2014,31(7):255-258,274.

[10] 于海群,劉萬軍,邱云飛.基于用戶偏好的社會網絡二級人脈推薦研究[J].計算機應用與軟件,2012,29(4):39-43.

[11]SilvaNB,TsangIR,CavalcantiGDC,etal.Agraph-basedfriendrecommendationsystemusinggeneticalgorithm[C]//Proceedingsof6thIEEEWorldCongressonComputationalIntelligence.Piscataway:IEEEPress,2010:233-239.

[12] 張龍昌,劉志晗,王攀,等.基于FOAF的分布式移動SNS應用[J].電信科學,2010,26(5):88-92.

[13] 平衛芳.Web數據挖掘中PageRank算法的研究與改進[D].華東理工大學,2014.

[14] 賀超波,湯庸,陳國華,等.面向大規模社交網絡的潛在好友推薦方法[J].合肥工業大學學報:自然科學版,2013,36(4):420-424.

[15]MapReduce上實現二度人脈好友推薦算法[EB/OL].http://www.datalab.sinaapp.com/?=192.

[16] 張杰.PyGel:基于DPark的分布式圖計算引擎的研究與實現[D].華南理工大學,2013.

[17] 蔡大威.基于Hadoop和Hama平臺的并行算法研究[D].浙江大學,2013.

[18] 朱珠.基于Hadoop的海量數據處理模型研究和應用[D].北京郵電大學,2008.

[19]WeiZhou,BoLi,ZhangZhang,etal.Arbor:EfficientLarge-ScaleGraphDataComputingModel[C]//Proceedingsofthe15thIEEEInternationalConferenceonHighPerformanceComputingandCommunications,2013:300-307.

[20] 李金枝.基于RWR的圖像分割算法研究[D].重慶大學,2010.

[21]PapadimitriouA,SyseonidisP,ManolopoulosY.Fastandaccuratelinkpredictioninsocialnetworkingsystems[J].JournalofSystemandSoftware,2012,85(9):2119-2132.

[22]DealingwithstructuredandunstructureddataatFacebook[EB/OL].http://videolectures.net/eswc2011_backstrom_facebook/.

STUDY ON A FRIEND RECOMMENDATION ALGORITHM BASED ON DISTRIBUTEDGRAPHCOMPUTINGFRAMEWORK

Zhao Masha1,2Zhou Wei1,2Zhang Hao3Han Jizhong1

1(Institute of Information Engineering,Chinese Academy of Science,Beijing 100093,China)2(University of Chinese Academy of Science,Beijing 100049,China)3(School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

AbstractWith the rise and development of social networking sites, the user number show a growth trend in exponential level, in these massive data there contains a lot of valuable information, and to mine the useful information has become the focus of the scholars in their studies. The friend recommendation algorithm is one of the most important applications in data mining. To acquire better performance and higher scalability, it becomes a developing trend in both the academia and the industry to use a distributed platform in solving the large-scale friend recommendation. Currently, the friend recommendation algorithm based on MapReduce framework has been widely used because of its high scalability. However, the inefficient transmission of the intermediate data of MapReduce results in the performance deficiencies. To solve these problems, the paper proposes a distributed graph computing framework-based friend recommendation algorithm. In end of the paper, we give the evaluation of the proposed algorithm on a couple of real social network datasets, and the experimental results show that it is superior to the advanced friend recommendation algorithms of the industry, and its performance is about seven times than that of other algorithms under the circumstance of similar accuracy.

KeywordsFriend recommendationDistributed graph computing frameworkRandom walk

收稿日期：2014-10-09。國家自然科學基金項目(60903047)；國家高技術研究發展計劃項目(2012AA01A401，2013AA013204)；中國科學院先導專項(XDA06030200)。趙馬沙，碩士生，主研領域：大規模數據處理。周薇，博士生。張豪，碩士生。韓冀中，教授級高工。

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.008