Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】

Stella981
• 阅读 869

一.分区策略

  Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】

  GraphX采用顶点分割的方式进行分布式图分区。GraphX不会沿着边划分图形,而是沿着顶点划分图形,这可以减少通信和存储的开销。从逻辑上讲,这对应于为机器分配边并允许顶点跨越多台机器。分配边的方法取决于分区策略PartitionStrategy并且对各种启发式方法进行了一些折中。用户可以使用Graph.partitionBy运算符重新划分图【可以使用不同分区策略】。默认的分区策略是使用图形构造中提供的边的初始分区。但是,用户可以轻松切换到GraphX中包含的2D分区或其他启发式方法。

  Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】

  一旦对边进行了划分,高效图并行计算的关键挑战就是将顶点属性和边有效结合。由于现实世界中的图通常具有比顶点更多的边,因此我们将顶点属性移到边上。由于并非所有分区都包含与所有顶点相邻的边,因此我们在内部维护一个路由表,该路由表在实现诸如triplets操作所需要的连接时,标示在哪里广播顶点aggregateMessages。

二.测试数据

  1.users.txt

    Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】

  2.followers.txt

    Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】

  3.数据可视化

    Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】

三.PageRank网页排名

  1.简介

    使用PageRank测量图中每个顶点的重要性,假设从边u到v表示的认可度x。例如,如果一个Twitter用户被许多其他用户关注,则该用户将获得很高的排名。GraphX带有PageRank的静态和动态实现,作为PageRank对象上的方法。静态PageRant运行固定的迭代次数,而动态PageRank运行直到排名收敛【变化小于指定的阈值】。GraphOps运行直接方法调用这些算法。

  2.代码实现

 1 package graphx
 2 
 3 import org.apache.log4j.{Level, Logger}
 4 import org.apache.spark.graphx.GraphLoader
 5 import org.apache.spark.sql.SparkSession
 6 
 7 /**
 8   * Created by Administrator on 2019/11/27.
 9   */
10 object PageRank {
11   Logger.getLogger("org").setLevel(Level.WARN)
12   def main(args: Array[String]) {
13     val spark = SparkSession.builder()
14         .master("local[2]")
15         .appName(s"${this.getClass.getSimpleName}")
16         .getOrCreate()
17       val sc = spark.sparkContext
18     val graph = GraphLoader.edgeListFile(sc, "D:\\software\\spark-2.4.4\\data\\graphx\\followers.txt")
19     // 调用PageRank图计算算法
20     val ranks = graph.pageRank(0.0001).vertices
21     // join
22     val users = sc.textFile("D:\\software\\spark-2.4.4\\data\\graphx\\users.txt").map(line => {
23       val fields = line.split(",")
24       (fields(0).toLong, fields(1))
25     })
26     // join
27     val ranksByUsername = users.join(ranks).map{
28       case (id, (username, rank)) => (username, rank)
29     }
30     // print
31     ranksByUsername.foreach(println)
32   }
33 }

  3.执行结果

    Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】

四.ConnectedComponents连通体算法

  1.简介

    连通体算法实现把图划分为多个子图【不进行节点切分】,清除孤岛子图【只要一个节点的子图】。其使用子图中编号最小的顶点ID标记子图。

  2.代码实现

 1 package graphx
 2 
 3 import org.apache.log4j.{Level, Logger}
 4 import org.apache.spark.graphx.GraphLoader
 5 import org.apache.spark.sql.SparkSession
 6 
 7 /**
 8   * Created by Administrator on 2019/11/27.
 9   */
10 object ConnectedComponents {
11   Logger.getLogger("org").setLevel(Level.WARN)
12   def main(args: Array[String]) {
13     val spark = SparkSession.builder()
14       .master("local[2]")
15       .appName(s"${this.getClass.getSimpleName}")
16       .getOrCreate()
17     val sc = spark.sparkContext
18     val graph = GraphLoader.edgeListFile(sc, "D:\\software\\spark-2.4.4\\data\\graphx\\followers.txt")
19     // 调用connectedComponents连通体算法
20     val cc = graph.connectedComponents().vertices
21     // join
22     val users = sc.textFile("D:\\software\\spark-2.4.4\\data\\graphx\\users.txt").map(line => {
23       val fields = line.split(",")
24       (fields(0).toLong, fields(1))
25     })
26     // join
27     val ranksByUsername = users.join(cc).map {
28       case (id, (username, rank)) => (username, rank)
29     }
30     val count = ranksByUsername.count().toInt
31     // print
32     ranksByUsername.map(_.swap).takeOrdered(count).foreach(println)
33   }
34 }

  3.执行结果

    Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】

五.TriangleCount三角计数算法

  1.简介  

    当顶点有两个相邻的顶点且它们之间存在边时,该顶点是三角形的一部分。GraphX在TriangleCount对象中实现三角计数算法,该算法通过确定经过每个顶点的三角形的数量,从而提供聚类的度量。注意,TriangleCount要求边定义必须为规范方向【srcId < dstId】,并且必须使用Graph.partitionBy对图进行分区。

  2.代码实现

 1 package graphx
 2 
 3 import org.apache.log4j.{Level, Logger}
 4 import org.apache.spark.graphx.{PartitionStrategy, GraphLoader}
 5 import org.apache.spark.sql.SparkSession
 6 
 7 /**
 8   * Created by Administrator on 2019/11/27.
 9   */
10 object TriangleCount {
11   Logger.getLogger("org").setLevel(Level.WARN)
12   def main(args: Array[String]) {
13     val spark = SparkSession.builder()
14       .master("local[2]")
15       .appName(s"${this.getClass.getSimpleName}")
16       .getOrCreate()
17     val sc = spark.sparkContext
18     val graph = GraphLoader.edgeListFile(sc, "D:\\software\\spark-2.4.4\\data\\graphx\\followers.txt", true)
19       .partitionBy(PartitionStrategy.RandomVertexCut)
20 
21     // 调用triangleCount三角计数算法
22     val triCounts = graph.triangleCount().vertices
23     // map
24     val users = sc.textFile("D:\\software\\spark-2.4.4\\data\\graphx\\users.txt").map(line => {
25       val fields = line.split(",")
26       (fields(0).toLong, fields(1))
27     })
28     // join
29     val triCountByUsername = users.join(triCounts).map { case (id, (username, tc)) =>
30       (username, tc)
31     }
32     val count = triCountByUsername.count().toInt
33     // print
34     triCountByUsername.map(_.swap).takeOrdered(count).foreach(println)
35   }
36 }

  3.执行结果

    Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】

点赞
收藏
评论区
推荐文章
Stella981 Stella981
2年前
Spark的分区机制的应用及PageRank算法的实现
佩奇排名(PageRank),又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(LarryPage)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。概念Sp
Stella981 Stella981
2年前
Linux系统安装完成后创建交换空间
有时候我们安装系统时候忘记分swap交换分区或者感觉内存够使用而没有划分SWAP分区,系统安装完成了我们改如何划分交换分区呢?本文是实践系统安装完成后创建交换区的一种方式。!(https://static.oschina.net/uploads/space/2017/1213/134422_MemC_2846946.png)一、主要步骤
Stella981 Stella981
2年前
Neo4j 第一篇:在Windows环境中安装Neo4j
<divid"cnblogs\_post\_body"class"blogpostbody"<p图形数据库(GraphDatabase)是NoSQL数据库家族中特殊的存在,用于存储丰富的关系数据,Neo4j是目前最流行的图形数据库,支持完整的事务,在属性图中,图是由顶点(Vertex),边(Edge)和属性(Property)组成的,顶点和
Stella981 Stella981
2年前
Spark学习之路 (二十八)分布式图计算系统
一、引言  在了解GraphX之前,需要先了解关于通用的分布式图计算框架的两个常见问题:图存储模式和图计算模式。二、图存储模式  巨型图的存储总体上有边分割和点分割两种存储方式。2013年,GraphLab2.0将其存储方式由边分割变为点分割,在性能上取得重大提升,目前基本上被业界广泛接受并使用。
Stella981 Stella981
2年前
Spark Graphx
Graphx   概述      SparkGraphX是一个分布式图处理框架,它是基于Spark平台提供对图计算和图挖掘简洁易用的而丰富的接口,极大的方便了对分布式图处理的需求。      众所周知·,社交网络中人与人之间有很多关系链,例如Twitter、Facebook、微博和微信等,这些都是大数据产生的地方都需要图计算,现
Stella981 Stella981
2年前
Consistent hashing一致性算法原理
最近在整理redis分布式集群,首先就整理一下分布式算法原理。常见的分区规则有哈希分区和顺序分区两种,Redis采用的是哈希分区规则。节点取余分区使用特定的数据,如Redis的键或用户ID为key,节点数量为N,则:hash(key)%N,计算出哈希值,然后决定映射到哪个节点上,如节点数为4时,哈希值的结果可能为0、1、2,3.现假
Wesley13 Wesley13
2年前
Mysql 表分区分类
针对Mysql数据库,表分区类型简析。【1】表分区类型(1)Range分区:按范围分区。按列值的范围区间进行分区存储;比如:id小于10存储在一个分区;id大于10小于20存储在另外一个分区;(2)List分区:按离散值集合分区。与range分区类似,不过它是按离散值进行分区。(3)Hash分区:按hash算法结果分区。对用户定义的表达式所返
Stella981 Stella981
2年前
Spark学习之路 (十七)Spark分区
一、分区的概念  分区是RDD内部并行计算的一个计算单元,RDD的数据集在逻辑上被划分为多个分片,每一个分片称为分区,分区的格式决定了并行计算的粒度,而每个分区的数值计算都是在一个任务中进行的,因此任务的个数,也是由RDD(准确来说是作业最后一个RDD)的分区数决定。二、为什么要进行分区  数据分区,在分布式
Stella981 Stella981
2年前
Linux系统分区方式
硬盘在使用之前,要进行分区、格式化一个硬盘可以分主分区、扩展分区、逻辑分区    主分区扩展分区<4,可以全部设置成主分区,也可以主分区扩展分区进行设置,扩展分区不能直接使用,需要在扩展分区上建立逻辑分区,逻辑分区可以有多个  主分区扩展分区编号14  逻辑分区编号只能从5开始
Wesley13 Wesley13
2年前
Unity 凹多边形三角剖分
游戏中需要实现一个小功能,显示一个玩家的能力图,这个图是一个有6个顶点任意摆放组合的多边形。而绘制多边形主要用到的知识就是Mesh构建,mesh的构建主要需要顶点列表,三角形列表,法线列表、uv列表等等等等,在这里我们只考虑顶点列表和三角形列表。那么我们需要做的就是给定一组顶点之后,如何用三角形进行划分,以便绘制。以下讨论的多边形:1.三角形顶点列表为顺