基于GraphX的社交網絡用戶推薦算法研究*

楊文杰周志剛雷歡楊慧莉

?

基于GraphX的社交網絡用戶推薦算法研究*

楊文杰1周志剛1雷歡1,2楊慧莉3

（1.廣東工業大學 2.廣東省智能制造研究所 廣東省現代控制技術重點實驗室 廣東省現代控制與光機電技術公共實驗室 3.沈陽工業大學）

針對PageRank等傳統算法在分析大規模分布式集群數據過程中存在耗時長、推薦不精準等問題，提出一種基于GraphX的社交網絡用戶推薦算法，以期提升用戶體驗。綜合搜索引擎中的相互超鏈接計算技術，采用PageRank算法和GraphX組件中的TriangleCounting算法等建立評估模型，并利用該模型用戶間的活躍度和網絡關聯度等關鍵參數來獲取用戶好友推薦表。通過Sougou數據對模型進行驗證，并與單一的PageRank算法模型進行對比分析，結果表明：算法評估模型運行速度和推薦率有顯著提升，推薦用戶好友更接近真實情況。

社交網絡；分布式集群；Spark平臺；GraphX組件；PageRank算法

0　引言

隨著人工智能、感知計算和互聯網技術的迅猛發展，互聯網云數據量亦呈指數級增長趨勢。通過互聯網大數據的融合與深度知識挖掘可為用戶實現全方位精準服務，并已廣泛應用于各行各業。Spark平臺是一個具有整合能力強、處理速度快的內存模型框架，尤其GraphX組件在基于社交網絡數據的條件下得到快速發展，其將社交網絡環境中用戶之間的關系圖挖掘出來，從而實現它的社會價值[1-2]。

基于GraphX等推薦引擎使用戶獲取更豐富、更有意義的信息[3]。目前，關于推薦算法的研究主要分為基于內容推薦[4]、基于協同過濾推薦和基于規則推薦3個方向。基于內容推薦的相關研究有：田耕提出一種關于關系和的重啟隨機游走算法[5]；侯成文提出一種組合加權的方法[6]；趙偉明采用加權余弦相似度計算用戶和視頻之間的相似度，對權重進行優化，提高了推薦效果[7]。基于協同過濾推薦的相關研究有：葛潤霞提出基于內容聚類的協同過濾推薦算法，該算法將改進的蟻群組合聚類算法和協同過濾相融合[8]；Peter等提出采用空間向量方法頻繁采樣進行推薦[9]。基于規則推薦的相關研究有：張文瑩提出基于規則的推薦方法降低計算量，在不需要用戶顯式輸入偏好的情況下進行推薦[10]。然而，這些算法針對不同的場景，存在模型建立困難、運行速度慢、用戶好友推薦不精準等問題，導致對分布式集群數據處理效率低、數據間的關聯度低、用戶體驗效果較差。

為提高大規模分布式海量數據彈性計算的執行效率和社交網絡推薦效果，本文提出一種基于GraphX的社交網絡用戶推薦算法評估模型。該模型相比傳統的PageRank算法模型運行速度快，并且其關聯度約高于PageRank算法模型3%，對微博和Facebook等網頁社交平臺用戶好友推薦更有效，更精準。

1　Spark平臺下GraphX組件的圖式計算

Spark是基于內存的編程模型，中間迭代過程不需要放在磁盤中，直接在內存中執行，大幅度減少磁盤I/O操作，極大地提高執行速度[11]。Spark充分利用內存計算，實現快速高效的分布式集群數據處理，比其他大數據計算框架運行速度快幾倍乃至幾十倍。Spark包含4大組件：Spark SQL（結構化數據）、Spark Streaming（實時計算）、MLlib（機器學習）和GraphX（圖計算）。整個框架自帶80多個算子，其中PageRank算法是Google專有的算法，用于衡量特定網頁相對于搜索引擎索引中的其他網頁而言的重要程度[12]；ConnectedComponent算法用于找出與該主題有關的用戶[13]；TriangleCounting算法用于找出與該用戶具有最穩定關系的朋友圈[14]。Spark生態框架如圖1所示。

圖1　Spark生態框架

GraphX是Spark中用于圖式并行計算的組件，其結合Pregel算法[15]進行重寫和優化。與其他分布式圖式計算框架相比，GraphX依靠Spark平臺，具備Spark的特性，可高效地完成圖計算的流水作業。GraphX流水作業流程圖如圖2所示。

圖2　GraphX流水作業流程圖

2　基于GraphX的社交網絡用戶推薦算法

2.1　算法評估模型

本文基于Spark平臺的GraphX組件，利用PageRank算法，同時融合TriangleCounting等算法，形成基于GraphX圖式計算的社交網絡新型用戶好友推薦算法，算法描述如下：

1）以被推薦的用戶為源點，利用Triangle Counting等算法對整個社交關系網中復雜的用戶關系進行清洗；

2）以被推薦的用戶為源點，采用PageRank算法計算該源點的有向圖邊以及各個屬性值，從而得到與之被推薦用戶的關系度degrees；

3）綜合考慮各用戶間的關系，并在1）、2）步為前提的條件下，選取Max degree用戶，推薦給用戶；

4） PageRank算法的表達為

其中，1,2,...,p是被研究的頁面；(p)是鏈入p頁面的集合；(p)是p鏈出頁面的數量；是所有頁面的數量；為阻尼因子，通常約為0.85；PageRank值是一個特殊矩陣中的特征向量，如式(1)所示，其中是等式的答案；

5）算法評估模型表達式

將網頁使用的推薦算法PageRank運用到社交網絡用戶推薦評估體系中，如果一個用戶被多個不知情的其他用戶或通過潛在的朋友圈所瀏覽，用戶與用戶之間的“票數”會升高，說明兩者相關性很大。通俗來講，就是評價用戶和用戶之間的關系程度，從而評估是否應該推薦該用戶。

2.2　核心算法

算法評估模型以Spark集群為平臺，采用Scala語言進行編寫。數據源采用Sougou實驗室的開放數據[16]，實現對用戶的推薦。其核心算法如下：

1）采用IntelliJ IDEA開發工具搭建開發環境，其中Hadoop使用2.7.3版本，Scala使用2.9.1版本，Spark使用2.0.2版本；

2）將數據導入HDFS文件系統中，同時導入相關的Spark jar包，以供代碼調用；

3）核心代碼如下：

① val conf = new SparkConf().setAppName ("SimpleGraphX").setMaster("local")//設置運行環境

② val sc = new SparkContext(conf)//初始配置

③ val vertexArray = Array(...)//數據載入

④ val edgeArray = Array(...)

⑤ val sourceId: VertexId = 5L //圖關系頂點

⑥ val initialGraph = graph.mapVertices((id, _) => if (id == sourceId) 0.0 else Double.PositiveInfinity)

⑦ val sssp = initialGraph.pregel(...)//評估模型初始化，通過參數調用不同底層算法

⑧ def max(a: (VertexId, Int), b: (VertexId, Int)):(VertexId, Int) = {if (a._2 > b._2) a else b}

⑨ println("max of outDegrees:" + graph. outDegrees.reduce(max) + " max of inDegrees:" + graph.inDegrees.reduce(max) + " max of Degrees:" + graph.degrees.reduce(max))//輸出用戶關聯度排序

其中，代碼①~②表示設置運行環境和應用進程的名稱；③~⑦為數據的描述和用戶關系度的發現，其中pregel函數（根據給定參數不同調用底層不同算法）由PageRank和TriangleCounting等算法實現，通過該函數模型可以計算各個源點的屬性以及邊的權重；⑧~⑨找出關系圖中權重最大值，即被推薦的用戶。運行數據處理過程中DAG（有向圖）如圖3所示。

圖3　數據處理過程DAG圖

3　實驗與分析

3.1　實驗平臺

實驗硬件以一臺I5 16 GB內存筆記本為基礎，以Vware Workstation為虛擬軟件，開啟5臺Centos Linux操作系統的虛擬機，每臺虛擬機都安裝有Spark和Hadoop集群，其中一主四從架構圖如圖4所示。

圖4　一主四從集群架構圖

3.2　實驗數據

本實驗采用Sougou實驗室數據。該數據均為文本格式，儲存于HDFS數據庫中，存在多余信息，需要對其進行ETL和格式轉換，以得到實驗所需格式的數據，即表示用戶好友關系的數據，其中包括1468974條用戶好友關系數據、45336條鏈接關系數據和63549條用戶信息數據。

3.3　結果與分析

表1　GraphX組件中的算法排名數據

表2　PageRank算法排名數據

對比表1和表2的實驗數據可得：利用2種模型進行用戶好友推薦的結果不同；采用基于GraphX組件的算法評估模型，用戶關聯度最高達到了80.5%，最低為67.8%，用戶關聯度排名前5的平均值約74.5%，并且和真實的用戶好友關聯排名相比一致；而采用傳統的PageRank算法模型，用戶關聯度最高只有77.4%，最低為60.1%，用戶關聯度排名前5的平均值約69.8%，但對于排名第五的推薦好友用戶和真實用戶關系排名出現不同。由此可知，對比這2種算法模型，基于GraphX組件的算法評估模型實驗值和真實值一致，且用戶關聯度排名約高于PageRank算法模型結果3%，使得用戶好友推薦更加精準，因此其相比傳統的PageRank算法更優越。

4　結論

為提高社交網絡數據的運行速度和用戶好友推薦的精準率，提出基于GraphX的社交網絡用戶推薦算法。實驗表明：該算法相比于傳統的PageRank算法，其推薦效果最高提高了7.8%，最低提高了3.1%，能夠更好展現出用戶體驗度。

[1] Holden Karau, Andy Konwinski. Learning Spark: Lightning- fast Data Analysisi[M]. O’Reilly Media, Inc. 2016.

[2] Andersen J S, Zukunft O. Evaluating the Scaling of Graph- Algorithms for Big Data Using GraphX[C]// International Conference on Open and Big Data. IEEE, 2016:1-8.

[3] 推薦算法[EB/OL].(2016-04-28)[2018-01-03].http://blog.csdn. net/u014605728/article/details/51274814.

[4] 周濤.基于用戶情境的協同推薦算法研究與應用[D].重慶:重慶大學,2010.

[5] 田耕.基于關系和內容的推薦算法研究[D].北京:北京交通大學,2015.

[6] 侯成文.基于內容的郵箱廣告推薦系統[D].北京:北京郵電大學,2015.

[7] 趙偉明.基于用戶行為分析和混合推薦策略的個性化推薦方法研究[D].北京:北京工業大學,2014.

[8] 葛潤霞.基于內容聚類的協同過濾推薦系統研究[D].濟南:山東師范大學,2008.

[9] Turney, Peter D, Pantel, et al. From frequency to meaning: vector space models of semantics[J]. Journal of Artificial Intelligence Research, 2010, 37(1):141-188.

[10] 張文瑩.移動應用中基于規則的LBS推薦系統研究[D].哈爾濱:哈爾濱工業大學,2013.

[11] 陳虹君.Spark框架的Graphx算法研究[J].電腦知識與技術,2015,11(1):75-77.

[12] PageRank[EB/OL].(2016-04-15)[2018-01-03].https://en.wiki-pedia.org/wiki/PageRank.

[13]Connected_component[EB/OL]. (2017-11-14)[2018-01-03]. https://en.wikipedia.org/wiki/Connectes_component_(graph_theory).

[14] Pagh R. Colorful triangle counting and a MapReduce imple- menttation[J]. Information Processing Letters, 2012, 112(7): 277-281.

[15] 孫海.Spark的圖計算框架:GraphX[J].現代計算機,2017(9): 120-122,127.

[16] 數據[EB/OL].(2012-08-07)[2018-01-03]. http://www.sogou.com/labs/resource/list_yuliao.php.

Research on Recommendation Algorithm for Social Network Users Based on GraphX

Yang Wenjie1Zhou Zhigang1Lei Huan1,2Yang Huili3

(1.Guangdong University of Technology 2.Guangdong Institute of Intelligent Manufacturing Guangdong Key Laboratory of Modern Control Technology Guangdong Open Laboratory of Modern Control & Optical, Mechanical and Electronic Technology 3. Shenyang University of Technology)

For PageRank on the analysis of the traditional methods, such as large-scale distributed cluster data in the process of some problems such as time-consuming, recommend not accurate, put forward a kind of social network users recommendation algorithm based on GraphX, in order to improve the user experience. Comprehensive calculation of mutual hyperlinks of search engine technology, using PageRank algorithm and GraphX components Triangle Counting algorithm of the evaluation model is set up, etc, the user's friend recommendation form is obtained by using the active degree of the model and the network relational degree. The model is validated through the Sougou data, and a single model of PageRank algorithm is compared and analyzed, the experimental results show that the speed and recommendation rate of the model are improved significantly, and the recommendation of users is closer to the real situation.

Social Network; Distributed Cluster; Spark Platform; GraphX Components; PageRank Algorithm

楊文杰，男，1991年生，碩士，主要研究方向：大數據、機器學習、圖像處理。E-mail:812406210@qq.com

周志剛，男，1993年生，碩士，主要研究方向：機器學習、圖像處理。

雷歡，男，1987年生，碩士，主要研究方向：機器視覺、深度學習。

楊慧莉，女，1993年生，碩士，主要研究方向：大數據、機器學習。

廣東省科技計劃項目（2017B090901041）