• 1. 图计算天云大数据
  • 2. 图计算介绍 图计算用于挖掘人、物和实体之间的潜在不易观察的行为和联系,而这些联系很难用传统数据库示。
  • 3. 以运营商CDR通话为例传统数据库图数据库主叫id被叫id通话时长姓名性别年龄18600000000186000000013张三男2818600000001186000000002李四女2618600000000张三男2818600000001李四女2632 传统数据结构是由表结构组成,图数据结构是由顶点、边组成。顶点包含顶点属性,边包含权重和方向。 以CDR为例,顶点属性包括手机号、姓名、性别和年龄,边的方向代表主叫被叫,边的权重代表通话时长。
  • 4. 图结构算法 —— 最短路径在指定关系网络上输入两个节点A和B,查询A和B的最短路径。 最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括: 确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。适合使用Dijkstra算法。 确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。 全局最短路径问题 - 求图中所有的最短路径。适合使用Floyd-Warshall算法。 Dijkstra算法
  • 5. 图结构算法 —— 最小连通图 在指定关系网络上输入单个节点A,查询与A相关联的“最小圈”(最小连通图) 强连通图 - 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。 最小强连通图 - 把连通图的所有结点用最少的边将其连接起来的子图。强连通图
  • 6. 图结构算法 —— key person输入单个节点,查询与该节点周边的key person。 节点度(node degree)- 所有与该节点有关的链接数量。 亲近中心性 – 每个节点的影响力由它和网络其余节点之间距离决定。 居间中心性 – 一个节点如果把持传播通道的话,它可能获得更大权重。
  • 7. 图结构算法 —— 传播影响力可以计算每个节点的传播影响力(pagerank)。 Pagerank:一个节点的“得票数”由所有链向它的节点的重要性来决定,到一个节点的边相当于对该节点投一票。一个节点的PageRank是由所有链向它的节点的重要性经过递归算法得到的。一个有较多链入的节点会有较高的等级,相反如果一个节点没有任何链入边,那么它没有等级。 节点越大代表该节点在网络中pagerank等级越高
  • 8. 图计算算法应用最短路径 - 好友推荐,转账检测,计算关系紧密程度 最小连通图 – 洗钱、虚假交易识别 Key person – 寻找意见领袖,防止客户流失的群体效应 Pagerank – 传播影响力分析
  • 9. 实时图计算分析应用手机/社交游戏新用户注册快速更新朋友圈推荐用户和游戏电子商务/零售用户浏览记录快速更新兴趣和商品图商品实时推荐银行/金融新交易记录快速更新金融关系圈欺诈检测 风险排名
  • 10. 运营商精准推荐 数据准备:用户ID,用户标签; 以用户为顶点,相同tag为边,形成兴趣图结构; 利用2步3步邻居为用户实时精准推荐。用户ID及标签兴趣图结构
  • 11. 潜在用户挖掘u1-u6是现存用户,n1-n3 是潜在用户。 可以通过2步或3步邻居分析找到一个潜在的新用户。“你的朋友已使用我们的服务,你要吗?”
  • 12. 欺诈检测 转账记录组成图结构; 实时检测资金转账异常行为。Fraud
  • 13. 图计算与BSP框架图计算的灵活性需求 在海量图计算中经常面临迭代计算,在每一次迭代中,每一个顶点都能接收来自上一次迭代的信息,并将这些信息传送给下一个顶点,并在此过程中修改其自身的状态信息,或改变整个图的拓扑结构。这就要求图计算框架足够的灵活。 BSP计算框架 整体同步并行计算模型(Bulk Synchronous Parallel Computing Model,简称BSP模型)是一个计算框架,按照这个框架编写的BSP程序会在集群的各个节点上做本地的I/O和计算,这一点和MapReduce相似,但不同的是BSP框架中,各个节点之间可以进行比较有效的通信。BSP是一个适合海量图计算的计算框架
  • 14. BSP框架一个BSP程序由一系列串行的超步(superstep)组成 在一个超步中, 所有的进程并行执行局部计算。一个超步可分为三个阶段: 1 )本地计算阶段, 每个处理器只对存储本地内存中的数据进行本地计算。 2 )全局通信阶段, 对任何非本地数据进行操作。 3 )栅栏同步阶段, 等待所有通信行为的结束。
  • 15. BSP框架本地计算全局通讯栅栏同步
  • 16. BSP VS MapReduceVSKmeans相比于MapReduce快500到1000倍 PageRank比MapReduce快10到20倍MapReduceBSPYARNHDFS
  • 17. (本页无文本内容)