Spark学习之路 (二十七)图简介

时间:2022-12-13 20:15:47

一、图

1.1 基本概念

图是由顶点集合(vertex)及顶点间的关系集合(边edge)组成的一种数据结构。

这里的图并非指代数中的图。图可以对事物以及事物之间的关系建模,图可以用来表示自然发生的连接数据,如:社交网络、互联网web页面

常用的应用有:在地图应用中找到最短路径、基于与他人的相似度图,推荐产品、服务、人际关系或媒体

二、术语

2.1 顶点和边

一般关系图中,事物为顶点,关系为边

Spark学习之路 (二十七)图简介

2.2 有向图和无向图

在有向图中,一条边的两个顶点一般扮演者不同的角色,比如父子关系、页面A连接向页面B;

在一个无向图中,边没有方向,即关系都是对等的,比如qq中的好友。

GraphX中有一个重要概念,所有的边都有一个方向,那么图就是有向图,如果忽略边的方向,就是无向图。

2.3 有环图和无环图

有环图是包含循环的,一系列顶点连接成一个环。无环图没有环。在有环图中,如果不关心终止条件,算法可能永远在环上执行,无法退出。

Spark学习之路 (二十七)图简介 Spark学习之路 (二十七)图简介

2.4 度、出边、入边、出度、入度

度表示一个顶点的所有边的数量

出边是指从当前顶点指向其他顶点的边

入边表示其他顶点指向当前顶点的边

出度是一个顶点出边的数量

入度是一个顶点入边的数量

2.5 超步

图进行迭代计算时,每一轮的迭代叫做一个超步

三、图处理技术

图处理技术包括图数据库、图数据查询、图数据分析和图数据可视化。

3.1 图数据库

Neo4j、Titan、OrientDB、DEX和InfiniteGraph等基于遍历算法的、实时的图数据库;

3.2 图数据查询

对图数据库中的内容进行查询

3.3 图数据分析

Google Pregel、Spark GraphX、GraphLab等图计算软件。传统的数据分析方法侧重于事物本身,即实体,例如银行交易、资产注册等等。而图数据不仅关注事物,还关注事物之间的联系。例如,如果在通话记录中发现张三曾打电话给李四,就可以将张三和李四关联起来,这种关联关系提供了与两者相关的有价值的信息,这样的信息是不可能仅从两者单纯的个体数据中获取的。

3.4 图数据可视化

OLTP风格的图数据库或者OLAP风格的图数据分析系统(或称为图计算软件),都可以应用图数据库可视化技术。需要注意的是,图可视化与关系数据可视化之间有很大的差异,关系数据可视化的目标是对数据取得直观的了解,而图数据可视化的目标在于对数据或算法进行调试。