结构:使用图对真实场景进行建模
图 (或 络 )是一种数据结构。 它由顶点(点)和边缘(线)组成。 许多现实世界的场景可以建模为图形。 这不一定是现实的某些客观性质所固有的,而是主要基于这样一个事实,即人类根据客体(顶点)及其彼此之间的相互关系(边缘)来主观地解释世界(一种反对这一观点的论点 )。 图计算中常用的数据模型是属性图 。 以下示例说明了通过三种不同方案进行的图形建模。
软件图
Stephen是名为TinkerPop的面向图形的工程小组的成员 。 斯蒂芬为Rexster做出了贡献。 Rexster通过软件依赖关系与其他项目相关。 当用户在Rexster中发现错误时,他们会发出票证 。 可以通过图形方便地捕获对协作编码环境的描述。 顶点(或事物)是人员,组织,项目和票证。 边(或关系)例如是成员资格,依赖关系和问题。 可以使用点和线将图形可视化,下面描述了上述情况。
讨论图
Matthias对图感兴趣。 他是Aurelius的CTO和图形数据库Titan的项目负责人。 Aurelius有一个邮件列表 。 在此邮件列表上,人们讨论了图论和技术。 Matthias参与了讨论。 他的贡献越来越多。 邮件列表以递归方式显示为一棵树 。 此外,消息的非结构化文本引用了共享概念。
概念图
图可以用来表示任意概念之间的关系,甚至是与图有关的概念。 例如,请注意后面的句子中的概念(斜体)如何关联。 图可以表示为邻接表 。 处理图的一般方法是通过图遍历 。 图形遍历有两种常规类型: 深度优先和宽度优先 。 图形可以保存在称为图形数据库的软件系统中。 图形数据库以不同于常见软件知识的关系数据库的方式组织信息。 在下图中,与图有关的概念相互链接,表明概念关系形成了图。
多域图
前面的三个场景(软件,讨论和概念)是真实系统(例如GitHub , Google Groups和Wikipedia )的表示。 这些看似完全不同的模型可以通过共享顶点无缝集成到单个原子图结构中。 例如,在关联的图中, Gremlin是Titan的依赖项,Titan由Matthias开发,Matthias在Aurelius的邮件列表上写消息(软件与讨论合并)。 接下来, 蓝图是Titan的依赖项,Titan是带标签的图 (软件与概念合并)。 虚线表示其他此类跨域链接,这些链接演示了如何在跨域共享顶点时如何创建通用模型。 集成的通用模型可以经受比任何单个模型单独提供的服务更丰富(也许更智能)的服务。
流程:通过遍历解决实际问题
确定循环依赖
随着开源软件的增长以及将模块轻松集成到项目中的便利, 循环依赖项比比皆是,并可能导致软件工程中的问题。 当项目A依赖项目B,并且通过某种依赖路径,项目B依赖项目A时,就会发生循环依赖。 当以图形方式表示依存关系时,遍历可以轻松识别出这种圆形度(例如,在下图中, A-> B-> D-> G-> A是一个循环 )。
排名讨论贡献者
寻找相关概念
多域遍历
先前讨论的不同图形模型(即软件,讨论和概念)通过共享顶点被集成到单个世界模型中。 类似地,可以构成上述图遍历以产生对跨域问题的解决方案。 例如:
“向我推荐参与的项目,这些项目应保持适当的依赖关系结构,并请有贡献的参与者来促进空间发展,并且在概念上与我以前研究过的技术有关。”
当异构的物联 链接在一起并在其中有效移动时,这种类型的问题解决才有可能。 链接和移动的方法分别是图形和遍历。 总结本节,提供了其他有用的遍历示例。
“基于项目的数量和其依赖项的数量,以递归方式计算项目的’稳定性等级’,以此类推。”
“根据项目之间的共享(或类似)概念进行集群项目。”
“建议一个开发人员团队开发一个即将使用X依赖项并且与Y概念相关的项目。”
“按每期提交者所贡献的项目数量来排名。”
图计算技术
计算的实践是在两个纠缠的量(空间和时间)之间划上一条细线。 在图计算领域,存在相同的权衡。 本节将讨论各种图形技术,以识别每种选择所获得和牺牲的内容。 此外,提出了一些示例技术。 注意,存在更多的技术,并且所提到的示例绝不是穷举性的。
内存中图形工具包
示例 : JUNG , NetworkX , iGraph ,Fulgora(即将推出)
- [+]丰富的图算法库
- [+]丰富的图形可视化库
- [+]不同空间/时间折衷的不同内存表示形式
- [-]限于可以容纳到主内存中的图形
- [-]交互通常非常繁琐
实时图形数据库
图形数据库也许是图形计算技术最流行的化身。 它们提供事务语义,例如ACID(本地数据库的典型值)和最终的一致性(分布式数据库的典型值)。 与内存中图形工具包不同,图形数据库利用磁盘来保留图形。 在合理的机器上,本地图数据库可以支持数十亿条边,而分布式系统则可以处理数千亿条边。 在如此规模的情况下,在多用户并发的情况下(随机访问磁盘和内存正在发挥作用),全局图算法是不可行的。 可行的是局部图算法/遍历。 而不是遍历整个图形,而是将某些顶点集用作遍历的源(或根)。
示例 : Neo4j , OrientDB , InfiniteGraph , DEX , Titan
- [+]针对本地邻域分析(“以自我为中心”的遍历)进行了优化
- [+]经过优化,可处理大量并发用户
- [+]交互是通过面向图的查询/遍历语言进行的
- [-]由于随机磁盘交互,全局图分析效率低下
- [-]由于数据库功能(例如事务语义)而导致的大量计算开销
批处理图框架
批处理图框架利用计算集群。 该领域中大多数流行的框架都将Hadoop用于存储(HDFS)和处理(MapReduce)。 这些系统面向全球分析。 也就是说,涉及整个图数据集的计算,在许多情况下,涉及遍及整个图多次的计算(迭代算法)。 此类分析不能实时运行。 但是,由于它们执行数据的全局扫描,因此可以利用从磁盘的顺序读取(请参阅《大数据病理学》 )。 最终,像内存系统一样,它们面向数据科学家,或者在生产环境中用于将结果反馈到实时图形数据库中。
示例 : Hama , Giraph , GraphLab , Faunus
- [+]针对全局图分析进行了优化
- [+]跨机器集群表示的流程图
- [+]利用对磁盘的顺序访问来缩短读取时间
- [-]不支持多个并发用户
- [-]不是实时图形计算系统
本节介绍了不同的图形计算解决方案。 重要的是要注意,还存在诸如Convey的MX系列和Cray的YARC图形引擎之类的硬件解决方案。 讨论的每种技术都有一个重要的主题-它们专注于处理图形数据。 每个类别的权衡取决于现代硬件/软件以及理论计算机科学提出的限制。
结论
对于熟练的人来说,图计算不仅是一套技术,而且是一种根据图来思考世界以及根据遍历来思考世界的方法。 随着数据变得越来越可访问,建立更丰富的环境模型变得更加容易。 越来越困难的是以一种可以被不同的计算系统方便而有效地处理的形式存储数据。 在许多情况下,图是建模的自然基础。 当模型是图形时,可以将多种图形计算技术应用于该模型。
致谢
翻译自: https://www.javacodegeeks.com/2014/06/on-graph-computing.html
文章知识点与官方知识档案匹配,可进一步学习相关知识算法技能树首页概览33834 人正在系统学习中 相关资源:【内存遍历工具】Cheat.Engine.V5.4.简体中文版-专业指导文档类…
声明:本站部分文章及图片源自用户投稿,如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢!