数据分析之图算法: 基于Spark和Neo4j

图论及其概念

｜

21

型进行过滤，比如观看、评分或评论。

投影出含有推断连接的单部图是图分析的重要组成部分。这些投影类型有助于揭示间接关

系及其强度。例如在图

2-11

的图

2

中，

Bev

和

Ann

只看过一部共同的电视剧，而

Bev

和

Evan

都看过的有两部。在图

3

中，我们通过共同观众的聚合视图对电视剧之间的关系进

行了加权。该指标或相似度等其他指标，可用于推断观看《太空堡垒卡拉狄加》和《萤火

虫》的活动之间存在什么内在联系。之后就可以向类似于

Evan

这样（刚刚看完《萤火虫》

最后一集）的观众发送推荐消息。

k

部图

涉及的节点类型数为

k

，例如三部图有

3

种节点。这只是对二部图和单部图的扩展，

使之用于多节点类型。现实世界中的许多图，尤其是知识图谱，其

k

值往往很大，这是因

为它们整合了许多概念和信息类型。以设计新配方为例，它是将配方集映射到配料集再映

射到化合物，然后推导出关联大众偏好的新组合。还可以通过泛化来减少节点类型的数量，

将节点的诸多形式泛化为一个节点，例如可以把“菠菜”和“油菜”视为“绿叶蔬菜”。

前面介绍了几种常用的图，下面介绍这些图可以应用的图算法类型。

2.4

　图算法的类型

下面探究在图算法中处于核心地位的

3

个分析领域。这

3

个类别分别对应第

4

章、第

5

章

和第

6

章。

2.4.1

　路径查找

路径是图分析和图算法的基础，自此开始介绍具体的算法示例。查找最短路径是使用图算

法执行的相当频繁的任务，而且它还是几种分析的先驱。最短路径是跳数最少或权重最小

的遍历路径。如果图是有向的，它就是指两个节点之间关系方向所允许的最短路径。 ...