基于GraphX的社交網(wǎng)絡(luò)用戶推薦算法研究*

楊文杰周志剛雷歡楊慧莉

?

基于GraphX的社交網(wǎng)絡(luò)用戶推薦算法研究*

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

（1.廣東工業(yè)大學(xué) 2.廣東省智能制造研究所 廣東省現(xiàn)代控制技術(shù)重點(diǎn)實(shí)驗(yàn)室 廣東省現(xiàn)代控制與光機(jī)電技術(shù)公共實(shí)驗(yàn)室 3.沈陽工業(yè)大學(xué)）

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

社交網(wǎng)絡(luò)；分布式集群；Spark平臺；GraphX組件；PageRank算法

0　引言

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

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

為提高大規(guī)模分布式海量數(shù)據(jù)彈性計算的執(zhí)行效率和社交網(wǎng)絡(luò)推薦效果，本文提出一種基于GraphX的社交網(wǎng)絡(luò)用戶推薦算法評估模型。該模型相比傳統(tǒng)的PageRank算法模型運(yùn)行速度快，并且其關(guān)聯(lián)度約高于PageRank算法模型3%，對微博和Facebook等網(wǎng)頁社交平臺用戶好友推薦更有效，更精準(zhǔn)。

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

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

圖1　Spark生態(tài)框架

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

圖2　GraphX流水作業(yè)流程圖

2　基于GraphX的社交網(wǎng)絡(luò)用戶推薦算法

2.1　算法評估模型

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

1）以被推薦的用戶為源點(diǎn)，利用Triangle Counting等算法對整個社交關(guān)系網(wǎng)中復(fù)雜的用戶關(guān)系進(jìn)行清洗；

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

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

4） PageRank算法的表達(dá)為

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

5）算法評估模型表達(dá)式

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

2.2　核心算法

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

1）采用IntelliJ IDEA開發(fā)工具搭建開發(fā)環(huán)境，其中Hadoop使用2.7.3版本，Scala使用2.9.1版本，Spark使用2.0.2版本；

2）將數(shù)據(jù)導(dǎo)入HDFS文件系統(tǒng)中，同時導(dǎo)入相關(guān)的Spark jar包，以供代碼調(diào)用；

3）核心代碼如下：

① val conf = new SparkConf().setAppName ("SimpleGraphX").setMaster("local")//設(shè)置運(yùn)行環(huán)境

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

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

④ val edgeArray = Array(...)

⑤ val sourceId: VertexId = 5L //圖關(guān)系頂點(diǎn)

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

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

⑧ 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))//輸出用戶關(guān)聯(lián)度排序

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

圖3　數(shù)據(jù)處理過程DAG圖

3　實(shí)驗(yàn)與分析

3.1　實(shí)驗(yàn)平臺

實(shí)驗(yàn)硬件以一臺I5 16 GB內(nèi)存筆記本為基礎(chǔ)，以Vware Workstation為虛擬軟件，開啟5臺Centos Linux操作系統(tǒng)的虛擬機(jī)，每臺虛擬機(jī)都安裝有Spark和Hadoop集群，其中一主四從架構(gòu)圖如圖4所示。

圖4　一主四從集群架構(gòu)圖

3.2　實(shí)驗(yàn)數(shù)據(jù)

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

3.3　結(jié)果與分析

表1　GraphX組件中的算法排名數(shù)據(jù)

表2　PageRank算法排名數(shù)據(jù)

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

4　結(jié)論

為提高社交網(wǎng)絡(luò)數(shù)據(jù)的運(yùn)行速度和用戶好友推薦的精準(zhǔn)率，提出基于GraphX的社交網(wǎng)絡(luò)用戶推薦算法。實(shí)驗(yàn)表明：該算法相比于傳統(tǒng)的PageRank算法，其推薦效果最高提高了7.8%，最低提高了3.1%，能夠更好展現(xiàn)出用戶體驗(yàn)度。

[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] 周濤.基于用戶情境的協(xié)同推薦算法研究與應(yīng)用[D].重慶:重慶大學(xué),2010.

[5] 田耕.基于關(guān)系和內(nèi)容的推薦算法研究[D].北京:北京交通大學(xué),2015.

[6] 侯成文.基于內(nèi)容的郵箱廣告推薦系統(tǒng)[D].北京:北京郵電大學(xué),2015.

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

[8] 葛潤霞.基于內(nèi)容聚類的協(xié)同過濾推薦系統(tǒng)研究[D].濟(jì)南:山東師范大學(xué),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] 張文瑩.移動應(yīng)用中基于規(guī)則的LBS推薦系統(tǒng)研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2013.

[11] 陳虹君.Spark框架的Graphx算法研究[J].電腦知識與技術(shù),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].現(xiàn)代計算機(jī),2017(9): 120-122,127.

[16] 數(shù)據(jù)[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年生，碩士，主要研究方向：大數(shù)據(jù)、機(jī)器學(xué)習(xí)、圖像處理。E-mail:812406210@qq.com

周志剛，男，1993年生，碩士，主要研究方向：機(jī)器學(xué)習(xí)、圖像處理。

雷歡，男，1987年生，碩士，主要研究方向：機(jī)器視覺、深度學(xué)習(xí)。

楊慧莉，女，1993年生，碩士，主要研究方向：大數(shù)據(jù)、機(jī)器學(xué)習(xí)。

廣東省科技計劃項(xiàng)目（2017B090901041）