文档章节

SparkInAction 图计算 用户关系染色分析

clebeg
 clebeg
发布于 2015/11/05 19:10
字数 610
阅读 253
收藏 4

SparkInAction 图计算 用户关系染色分析

前言

需求:如果一个用户使用了某个手机,这个手机上登录过其他的用户,那么这些用户是有关系的,同样用户关联到的用户又可以通过手机关联到其他用户 这样就构成了一个强大的关系网。现在给出用户与手机登录关系表,请找出所有的用户是有关系的。

问题分析

整个用户手机关系网拓扑图如下图所示:
用户手机关系拓扑图
从图中可以发现,找到有关系的关联的用户,就是要找出上面无向图的所有联通分支。比如上图有两个联通分支。

测试数据集

对应上图,测试数据集合如下:

#user_id,phone_id
001,01
002,01
003,01
004,01
005,01
004,02
006,02
007,02
008,02
009,03
010,03
011,03

希望的输出结果为所有关联的用户对应同一个ID。

测试代码

  val rootDir = "datas"
  def main(args: Array[String]) {
    val conf = new SparkConf().setAppName("SparkInAction").setMaster("local")
    val sc = new SparkContext(conf)
    val userPhoneRS = sc.textFile(rootDir + "/user_phone.relationship")
    # 生成用户对应的点
    val users: RDD[(VertexId, (String))] =
     userPhoneRS.map(_.split(",")(0)).distinct()
     .map(userId => (userId.toLong, ("TEST_USER")))
    # 生成手机对应的点,为了防止手机ID和用户ID重复,使用了一个小技巧,就是手机ID = 最大的用户ID + 手机ID
    val maxUserId = users.max()._1
    val phones: RDD[(VertexId, (String))] =
     userPhoneRS.map(_.split(",")(1)).distinct()
     .map(phoneId => (phoneId.toLong + maxUserId, ("TEST_PHONE")))
    # 生成所有的点
    val vertices = users.union(phones)

    # 生成所有的边
    val edges: RDD[Edge[String]]= userPhoneRS.map {
      line =>
        val up = line.split(",")
        Edge(up(0).toLong, up(1).toLong + maxUserId, "TEST_EDGE")
    }

    # 生成图
    val default = ("Missing")
    val graph = Graph(vertices, edges, default)
    graph.vertices.collect().foreach(println)
    graph.edges.collect().foreach(println)

    # 找到所有的联通分支
    val graph2 = graph.connectedComponents()

    # 结果展示
    graph2.vertices.filter(_._1 <= maxUserId).collect().foreach(println)
  }

运行结果:

(4,1)
(6,1)
(8,1)
(10,9)
(2,1)
(11,9)
(1,1)
(3,1)
(7,1)
(9,9)
(5,1)

可以发现,结果正如我们所料。

总结

基于 Spark GraphX 可以做很多图计算方面的事情,而且是分布式,速度比单机处理快,值得好好研究。 下面推荐一下好的资料:

个人微信公众号

欢迎关注本人微信公众号,会定时发送关于大数据、机器学习、Java、Linux 等技术的学习文章,而且是一个系列一个系列的发布,无任何广告,纯属个人兴趣。
Clebeg能量集结号

© 著作权归作者所有

clebeg
粉丝 45
博文 40
码字总数 40057
作品 0
广州
程序员
私信 提问
腾讯开源微服务架构 Tars,高性能 RPC 开发框架

腾讯微服务架构 Tars 于今日正式开源。 Tars 取名于电影“星际穿越”中的机器人,是支持多语言的高性能 RPC 开发框架和配套一体化的服务治理平台,可以帮助企业或者用户以微服务的方式快速构...

王练
2017/04/10
14.7K
13
【复习图论】如何找出一个强连通图的奇环

如何找出一个强连通图的奇环 这个问题来自于《算法概论》的课后习题,我想了2天,最后想出一个可行的办法。 首先,对于环的问题,有两个常规的手段,一个是点染色,还有一个是利用边的分类。...

m2012
2012/10/29
1K
0
探索零知识证明系列1 - 初识「零知识」与「证明」

引言: 我认为区块链很难称为一个“技术”。它更像是一个领域,包罗万象。或者形而上地说,区块链更像一个有机体,融合了各种不同的理论技术。 零知识证明是构建信任的重要技术,也是区块链这...

深入浅出区块链
08/01
0
0
红黑树——以无厚入有间(插入)

首先说一下,关于红黑树有一篇很棒的论文《A dichromatic framework for balanced trees》,作者之一的Robert Sedgewick,想必大家不会陌生。如果有兴趣可以仔细研读一下,里面讲了更多细节的...

仪式黑刃
2018/09/02
0
0
洛谷 P2921 在农场万圣节Trick or Treat on the Farm题解

题意翻译 题目描述 每年,在威斯康星州,奶牛们都会穿上衣服,收集农夫约翰在N(1<=N<=100,000)个牛棚隔间中留下的糖果,以此来庆祝美国秋天的万圣节。 由于牛棚不太大,FJ通过指定奶牛必须遵...

zealsoft
08/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

前端技术之:Prisma Demo服务部署过程记录

安装前提条件: 1、已经安装了docker运行环境 2、以下命令执行记录发生在MackBook环境 3、已经安装了PostgreSQL(我使用的是11版本) 4、Node开发运行环境可以正常工作 首先需要通过Node包管...

popgis
今天
5
0
数组和链表

数组 链表 技巧一:掌握链表,想轻松写出正确的链表代码,需要理解指针获引用的含义: 对指针的理解,记住下面的这句话就可以了: 将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指...

code-ortaerc
今天
4
0
栈-链式(c/c++实现)

上次说“栈是在线性表演变而来的,线性表很自由,想往哪里插数据就往哪里插数据,想删哪数据就删哪数据...。但给线性表一些限制呢,就没那么自由了,把线性表的三边封起来就变成了栈,栈只能...

白客C
今天
41
0
Mybatis Plus service

/** * @author beth * @data 2019-10-20 23:34 */@RunWith(SpringRunner.class)@SpringBootTestpublic class ServiceTest { @Autowired private IUserInfoService iUserInfoS......

一个yuanbeth
今天
5
0
php7-internal 7 zval的操作

## 7.7 zval的操作 扩展中经常会用到各种类型的zval,PHP提供了很多宏用于不同类型zval的操作,尽管我们也可以自己操作zval,但这并不是一个好习惯,因为zval有很多其它用途的标识,如果自己...

冻结not
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部