基于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）