Spark框架的Graphx算法研究

陈虹君

摘要：随着搜索引擎对网页的排名的需要，以及社交网络的兴起，海量关系所产生的大数据需要得到处理。图计算在数据关系的分析上发挥着其巨大的潜能。Spark框架是Hadoop大数据平台上整合能力强，处理速度快的内存模型框架，它的图处理Graphx也得到快速发展。该文先介绍Spark框架与Graphx的关系与发展。接着分析了Graphx中的三个典型的算法。最后总结了Graphx的场景应用。

关键词：大数据；Hadoop；Spark；图计算；Graphx；PageRank

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）01-0075-03

Research on Graphx Algorithms in Spark Framework

CHEN Hong-jun

（Chengdu College of University of Electronic Science and Technology of China， Chengdu 611731， China）

Abstract： As the search engine need of Webpage ranking， and the rise of social networking， large mass data relations need to process. Graph calculation plays its great potential in the analysis of data relationship. The Spark framework is memory model frame which is deployed on Hadoop. It has great integration ability； high processing speed.So the graph processing Graphx also obtained the fast development. In this paper， firstly introduce the relation and development of Spark framework and Graphx. Then analyze the three typical algorithms in Graphx. Finally sum up the scene using Graphx.

Key words： big data； Hadoop； Spark； graphs computing； Graphx； PageRank

图计算可以用来处理复杂的数据联系。比如：整个社交网站就像一个关系网一样，处处充满了联系。在大数据时代，网络关系日益丰富的今天，大数据的图处理正迅猛发展。而图在数据分析上的典型应用就是Facebook、twitter这样的社交网站上的对用户及话题的分析，因为用户之间可能随时都会产生新的联系，不同用户对于不同话题也有不同的倾向。

图用顶点（vertex）来表示数据对象，用边（edge）来表示数据之间的联系，而边的权值可以是价值、身份、时间等各种抽象或者逻辑上的意义。图可以转化为数学上的邻接矩阵，因此对图的各种算法应用大多都要建立在数学之上；图的应用算法需要用数学公式来分析和证明，同样一个图能否并行处理也要依赖于它相应的数据矩阵是否可以再分。

1 Spark框架与Graphx

Spark是基于内存的编程模型，它可以把中间的迭代过程不放在磁盘中，直接数据不落地在内存中执行，极大地提高了它的执行速度。Spark分为四大模块：Spark SQL-RDD（数据执行的基本单元），MLlib（机器学习）、Graphx（图计算），Spark Streaming（实时处理），整个框架形成了大数据处理各种应用场景编程的一致性。

GraphX是新的（alpha）Spark用于圖表和图形，并行计算的的API。 GraphX在一个高层次上， 延伸了Spark RDD。 通过引入Resilient Distributed Property Graph （弹性分布式属性图）： 一个有向多重图能附加每个顶点属性和边的属性。为了支持图形计算， GraphX 公开了一组基本的运算符，比如：subgraph （子图）、 joinVertices、mapReduceTriplets，以及一个最优的转变的Pregel API. 此外， GraphX 包含一个对图形算法（algorithms）和构建器 （builders） 不断增长的包集合，用以简化图形分析任务。

在 GraphX的发布之前，Spark中的图形计算使用Bagel来表达， 即对Pregel的实现。 GraphX改进了Bagel 通过更丰富的特性图形 API，使用比Pregel更精简的版本， 使系统得到优化，提升了性能并减少了内存开销。

2 Graphx算法

Graphx作为Spark的图处理框架，支持以下算法：PageRank算法、ConnectedComponents算法、TriangleCounting算法等。PageRank算法是Google专有的算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。ConnectedComponents算法，用于找出与该主题有关的用户。TriangleCounting算法，用于找出与该用户具有最稳定关系的朋友圈。

2.1 Graphx中的PageRank算法

一个页面的重要性可以由其“得票数”确定。“得票数”由所有链向它的页面的重要性来决定。到一个页面的超链接相当于对该页投一票。一个超链接指向了多个页面s个，那么它对每个页面的贡献值是1/s。一个页面的PageRank是由所有链向它的页面的重要性经过递归算法得到的。一个有较多链入的页面会有较高的得分，相反如果一个页面没有任何链入页面，那么它没有得分。数学公式[1]如（1） ：

Pi，P2，…， Pn是被研究的页面，M（Pi）是Pi链入页面的数量，L（Pj）是Pj链出页面的数量，而N是所有页面的数量。

该PageRank模型在Spark的图计算Graphx中提供了两种调用方式：

第一种：静态调用方式，如图1。在调用时提供一个参数number，用于指定迭代次数，即无论结果如何，该算法在迭代number次后停止计算，返回图结果。

第二种：动态调用方式，如图2。在调用时提供一个参数tol，用于指定前后两次迭代的结果差值应小于tol，以达到最终收敛的效果时才停止计算，返回图结果。

2.2 Graphx中的ConnectedComponents算法

在Graphx中的ConnectedComponent算法[2]是指在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量，如图3、图4。

寻找连通图在一些场景中是图计算的核心应用。比如：以关键词集合识别集群。以每个定点表示每一项（Item），以边代表它们之间的联系，或者认为他们之间具有相似性。因此。连通图就对应了不同类别的项集合。

2.3 Graphx中的TriangleCount算法

在Graphx中的的TriangleCount算法可以用于社区发现。此应用与微博上，表示你关注的人且关注你的人，大家的关注关系就会形成很多的三角形，说们与你形成三角形的人与你有稳定的关系，大家关系紧密。

3 总结

对于不同的应用场景，需要不同的数据，而对于不同的算法，同样的数据可能又有不同的数据格式。对于图技术而言，在各种工程中都可能某一部分会用到图处理，概而言之就是只要涉及到计算热度值（例如PageRank，新闻推荐，朋友圈分析）都可以使用图来处理。对于上次的PageRank的实例，需要的数据就应满足：一个网页URL及该网页链出的URL，可表示如下：

URL outURL

URL outURL

URL outURL

…… ……

对于新闻推荐，就应该需要新闻名字以及他在某段时间内被点击查看的次数；或者根据与该新闻相关新闻的热度值来推荐。对于朋友圈（好友推荐），则是一个大关系网的数据类型，这就需要知道每个人的一些特点，如兴趣爱好、地区等，同时又要包括好友关系，可以转化为图的多重边。图计算的发展随着社交网络的發展将得到飞速的发展。

参考文献：

[1] PageRank算法[EB/OL].2012.http：//blog.csdn.net/hguisu/article/details/7996185.

[2] 连通图[EB/OL].http：//www3.cs.stonybrook.edu/～algorith/files/dfs-bfs.shtml.

[3] Spark编程指南[EB/OL].2013.http：//spark.apache.org/docs/latest/programming-guide.html.

[4] 机器学习库[EB/OL].2013.http：//blog.csdn.net/johnny_lee/article/details/25656343.

[5] Graphx学习[EB/OL].2012.http：//spark.apache.org/docs/latest/graphx-programming-guide.html.

[6] 云计算的分类[EB/OL].2010.http：//tech.qq.com/a/20101103/000074.htm.

[7] 最近的spark文档[EB/OL].2014.http：//spark.apache.org/docs/latest/.