图计算|江阴雨辰互联

2023年7月28日发(作者：)

图计算

1. 生活中图是如何产生的？

计算机网络，就是由许多节点(计算机或者路由器)以及节点之间的边(网线)构成的；

城市的道路系统，也是由节点(路口)和边(道路)构成的图。

微信的社交网络，也是由节点（个人，公众号）和边（关注，点赞）构成的图。

淘宝的交易网络，也是由节点（个人，商品）和边（购买，收藏）构成的图。

网页的链接网络，也是由节点（网页）和边（链接）构成的图。

图的定义：图G=(V,E)是由节点的集合V和边的集合E构成的。图在网络科学中被称为网络。

2. 图的类型

我们以身高为横坐标，以取得此身高的人数为纵坐标，可画出一条钟形分布曲线，这种曲线两边衰减地极快，特别高的人和特别矮的人都是比较少见的；这种分布可以用正态分布或泊松分布来描述它。如左上图的泊松分布，符合这种分布的网络称之为随机网络，随机网络是个理论上的网络。

实际生活中的网络是出于种种现实的目的建立的。比如微博，姚晨能成为大V，背后有一个分工严谨的团队在进行运作。对于一个现实中的网络而言，当新的节点加入的时候，总是会优先连接那些在网络中最耀眼的节点。比如新用户加入微博，总是先关注那些知名大v。网络中的节点和新节点建立连接的概率与这个节点已有的连接数正相关，网络的度分布则是幂律分布，符合这种特点的网络叫无尺度网络。又叫自然图。像Internet、电子邮件网络、电影演员合作网络、引文关系网络的节点的度都符合幂律分布，数据倾斜是很严重的现象。

3. 图计算

1) 图计算概述

图由很多个节点(vertex)构成，节点之间通过边(edge)连接，节点和边中都包含了计算状态数据。状态的更新是通过在每个节点上运行一系列的迭代计算来完成，计算结果是图中所有节点和边的最终状态的聚合。节点计算依赖与自身节点、邻居节点以及边的状态，并可以更新这些状态。

2) 分布式图计算

为了解决巨型图的存储和计算，提出了分布式图计算框架，其目的是将对于巨型图的各种操作包装为简单的接口，让分布式存储、并行计算等复杂问题对上层透明，从而使复杂网络和图算法的工程师，更加聚焦在图相关的模型设计和使用上，而不用关心底层的分布式细节。为了实现该目的，需要解决两个通用问题：图存储模式和图计算模式。

3) 图存储模式：

边分割：每个顶点都存储一次，但有的边会被打断分到两台机器上。这样做的好处是节省存储空间；坏处是对图进行基于边的计算时，对于一条两个顶点被分到不同机器上的边来说，要跨机器通信传输数据，内网通信流量大。

点分割：每条边只存储一次，都只会出现在一台机器上。邻居多的点会被复制到多台机器上，增加了存储开销，同时会引发数据同步问题。好处是可以大幅减少内网通信量。

4) 图计算模式

目前的图计算框架基本上都遵循BSP（Bulk Synchronous Parallell）计算模式。在BSP中，一次计算过程由一系列全局超步组成，每一个超步由并发计算、通信和栅栏同步三个步骤组成。同步完成，标志着这个超步的完成及下一个超步的开始。BSP模式很简洁。基于BSP模式，目前有两种比较成熟的图计算模型。

•

Pregel模型——“像顶点一样思考”（Think Like A Vertex）的图计算模式，让用户无需考虑并行分布式计算的细节，只需要实现一个顶点更新函数，让框架在遍历顶点时进行调用即可。 •

GAS模型——相比Pregel模型的消息通信范式，GraphLab的GAS模型更偏向共享内存风格。它允许用户的自定义函数访问当前顶点的整个邻域，可抽象成Gather、Apply和Scatter三个阶段，简称为GAS。

4. 图的计算

点的度数（average degree ）:对于无向网络而言，就是每个边的平均节点数，有向网络又分为出度和入度。点的度数分布和消息的传播概率P直接决定了一个消息是否可以传遍全网络，还是在传播过程中湮灭了。

平均路径(average path):对于某个点而言，计算它到网络中的所有其他点的最短路径，求和，然后除以网络中点的个数。这个值直接说明了这个点到网络中的其他节点要多少步。而对于网络的所有点的平均路径分布可以判断这个网络是均匀的（各点的平均路径大致相同），带中心区域的（有的点平均路径大，属于边缘区，反之则为中心区）。

网络半径:所有点的计算到其他点的距离，其中的最大距离就是网络半径。MAX(shortest path)对于点i的聚合系数(clustering cofficient)=点i的邻居间的边数/点i的邻居数。这个系数说明了i所在的社群是否是活跃的，有凝聚力的。这个特性在聚划算的效果预估，营销策略策划上有很大的应用前景。

最大联通分量：是一个完全子图(sub complete graph),在这个子图中，所有点都相互连接，一些在全网络中不能大范围传播的信息会在这个小集团中反复传播，沉淀下来，称为一种类似方言，行话之类的东西。可用于社区发现。

三角计数：当顶点周围与有一个其他两个顶点有连线时，这个顶点是三角形的一部分。三角形计数算法算通过各顶点的三角形数目，从而提供集群的度。可以用于社区发现，话题发现等。

最短路径：计算网络两点之间最短路径和路径上经过的节点。可用于发现两个实体之间的关系。

Pagerank：计算网络中节点入度排名。可用于社交、电商和话题推荐。

5. 图计算应用示例以wikipedia数据为例，从图中我们可以看出：拿到wikipedia文档以后，可以变成table形式的视图，然后基于table形式的视图可以分析hyperlinks，也可以分析term-doc graph，经过LDA之后进入wordtopics，至于hyperlinks，我们可以使用pagerank去分析，在下面的editor graph到community，这个过程可以称之为triangle computation，这是计算三角形的一个算法，基于此，会发现一个社区。

6. 商业应用

时趣SocialTouch是数据驱动的移动营销解决方案提供商。所涉及的客户数据源涵盖了自媒体行为，关系，内容。企业内部营销，销售，售后数据，以及其他第三方和广告投放数据。数据来源结构复杂。数据的应用类型也比较多样化，主要包括：消费者画像，交互式消费者洞察分析，潜在消费群体挖掘，个性化内容等等。

为了应对以上业务需求。SocialTouch从构建大数据架构开始，就启动研发了专利技术——CrowdGraph，专业应对消费者行为数据处理的实时图计算引擎。并成功应用于SocialTouch BI，社会化聆听，数据管理平台等产品中。下图给出了CrowdGraph的逻辑架构：淘宝：基本上，所有的关系都可以从图的角度来看待和处理，但到底一个关系的价值多大？健康与否？适合用于什么场景？很多时候是靠运营人员和产品经理凭直觉来判断和评估的。如何将各种图的指标精细化和规范化，对于产品和运营的构思进行数据上的预研指导，提供科学决策的依据，是图谱计算平台设计的初衷和出发点。基于这样的出发点，借助GraphX丰富的接口和工具包，针对淘宝内部林林总总的图业务需求，我们开发一个图谱计算平台。主要功能包括：基于度分布的中枢节点发现、基于最大联通图的社区发现、基于三角形计数的关系衡量、基于随机游走的用户属性传播和基于用户行为的商品推荐。

7. 图数据库对比 Neo4J是当下人气最高的图形数据库。从名称我们就能看出Neo4J在设计上主要考虑到Java应用程序的实际需求，但它同时也支持Python。Neo4J属于开源项目，共有GPLv3社区版、高级版、企业版三种版本；后两者都以AGPLv3商业许可为基础。更多内容请参见：/

InfiniteGraph 是一款由Objectivity公司推出的图形类数据库，该公司还推出过一款同名的对象类数据库。免费许可版本只能支持最高100万节点及边线总数。InfiniteGraph需要作为服务项目加以安装，这与以MySQL为代表的传统数据库颇为相似。InfiniteGraph借鉴了Objectivity/DB中的面向对象概念，因此其中的每一个节点及边线都算作一个对象。更多内容请参见：/

DEX一直被形容为一款具备高性能及优秀可扩展性的图形类数据库，这对于NoSQL应用程序来说无疑拥有相当强的吸引力。其个人评估版本最多可支持100万个节点。目前最新的版本是4.2，同时支持Java及.Net编程。请注意，旧的4.1版本只支持Java，且无法与新版本相兼容。更多内容请参见：/dex

InfoGrid一直标榜自己是一款“网页图形数据库”，也就是说它的某些功能主要面向网页应用程序。图五展示了InfoGrid的整体框架，而图形数据库在其中所扮演的似乎并不是主要组成部分。InfoGrid在OpenID项目中也拥有几款应用程序，该项目同样由Netmesh公司所支持。更多内容请参见：/ HyperGraphDB是一套开源数据存储机制，并依托于BerkeleyDB数据库存在。HyperGraphDB的图形模型被称为直接式超图形。从数学角度来讲，超图形允许其一条边线指向两个以上的节点。HyperGraphDB在此基础上更进一步，允许一条边线指向其它边线，如此一来HyperGraphDB在概括性方面就大大超过了其它图形类数据库。更多内容请参见：/index

微软不久之前才刚刚携Trinity首个发布版本V0.1（只允许企业内网接入）加入角逐。根据介绍，Trinity是一款基于内存的图形存储机制，且具备丰富的数据库功能，其中包括高并行性联机查询处理、ACI事务支持等等。在图形处理方面，Trinity只为用户提供了C# API。更多内容请参见：/en-us/projects/trinity/

AllegroGraph是一款老牌图形类数据库了，据称其负载“数十亿RDF（即资源描述框架）三元组仍可保持高性能”。尽管RDF三元组可以作为边线来处理，但AllegroGraph的原本设计意图是创建以RDF为中心的语义网络应用程序，并支持SPARQL、RDFS++以及Prolog等由包括Java程序在内的各类客户应用推衍得出的程序。AllegroGraph RDFStore免费版本支持最多5000万个三元组。

更多内容请参见：/agraph/allegrograph/

如何选择：

如果需要存储RDF三元组，那么AllegroGraph是首选；

处理属性图，Neo4J与DEX是当仁不让的利器；

处理超图形，HyperGraphDB堪称行家。

8. 图计算平台

Google为了应对图计算的需求，推出了新的“计算框架”——Pregel。CMU给出了一个开源的版本——GraphLab，虽然二者都是对于复杂机器学习计算的处理框架，用于迭代型（iteration）计算，但是二者的实现方法却采取了不同的路径——Pregel是基于大块的消息传递机制，GraphLab是基于内存共享机制。同样的，最近非常火的“Spark”也有支持图计算机器学习的模块——GraphX，可以实现复杂的图数据挖掘。

Giraph GraphLab GraphX 模型

开源情况

支持语言

生态系统

性能*

使用情况

BSP

开源

JAVA

Hadoop

833s

Facebook