第 1 章 导论

第 1 章 导论

图是计算机科学的一大主题,可用于抽象表示交通运输系统、人际交往网络和电信网络。对于训练有素的程序员而言,能够用一种形式来对不同的结构建模是强大的力量之源。

——《算法设计指南》

Steven S. Skiena,石溪大学计算机科学杰出授课教授

当今紧迫的数据挑战在于厘清关系,而不仅仅是对离散数据制表。图技术及其分析方法为用于研究、社会活动和商业解决方案的关联数据提供了强大的工具,举例如下:

  • 对金融市场、信息技术服务等多种动态环境建模;
  • 预测传染病的传播以及由此引发的服务延迟和中断;
  • 查找用于机器学习的预测性特征,以打击金融犯罪;
  • 发现针对个性化体验和推荐的模式。

随着数据之间的关联度日益增强,系统也越来越复杂,利用数据中丰富且不断演进的关系变得非常重要。

本章将介绍图分析和图算法。在介绍图算法和解释图数据库与图处理之间的区别之前,首先简要回顾图的起源。本章将探究现代数据的本质,揭示为何联系所含的信息要比用基本统计方法发现的信息复杂得多,最后还会研究一些图分析用例。

1.1 何谓图

图的历史可以追溯到 1736 年,即欧拉解决“哥尼斯堡七桥”问题的那一年。“哥尼斯堡七桥”问题是指,能否参观哥尼斯堡市里由7 座桥连接的4 个区域,而且每座桥只允许经过一次。实际上这是不可能做到的。

欧拉意识到“哥尼斯堡七桥”问题仅与连接关系本身相关,他为图论及其数学运算奠定了基础。图 1-1 描绘了欧拉的解题过程,其中有他绘制的一张草图,摘自其论文“Solutio problematis ad geometriam situs pertinentis”1

1大意是“位置几何相关问题的解决方法”。——编者注

{%}

图 1-1:图论的起源。哥尼斯堡市有两座岛,它们通过7 座桥与该市的另外两块陆地相连。难题在于如何构建一条遍历整个城市的路径,使得每座桥只经过一次

图源于数学,也是一种实用且高精度的数据建模和分析方法。构成图的对象称为节点或顶点,它们之间的关联称为关系、联系或边。本书使用节点和关系这两个术语。可以把节点看作句子中的名词,把关系看作为节点提供上下文的动词。为避免混淆,本书所指的图与图 1-2 中的方程式绘图或图表无关。

图 1-2:图是网络的一种表示方法,通常用圆表示被称为节点的实体,用线条表示关系

请看图 1-2 中的人物图,很容易就能想出几个描述该图的句子,例如人物 A 和拥有一辆车的人物 B 住在一起,人物 A 驾驶的是人物 B 的车。这种建模方法很有趣,因为易于将其与现实世界联系起来,也便于在白板上展示。这种方法有助于进行恰当的数据建模和分析。

完成图的建模才行至半途,还需要处理图,揭示其中并不显而易见的信息,而这正是图算法的用武之地。

1.2 何谓图分析和图算法

图算法属于图分析工具。图分析是使用基于图的方法来分析关联数据的过程。有多种方法可用,包括查询图数据、使用基本的统计方法、直观地研究图,或者将图整合到机器学习任务中,等等。基于图模式的查询通常用于局部数据分析,而图计算算法通常用于全局分析和迭代分析。尽管这些类型的分析方法在运用上相互交叉,但本书仍使用图算法这个术语来指代后者,它更多地用于计算分析和数据科学。

网络科学

网络科学是一个植根于图论的学术领域,主要研究有关对象关系的数学模型。网络科学家依赖图算法和数据库管理系统来研究数据的规模、关联性和复杂性。

在复杂性和网络科学方面有许多优质资源,下面列出一些供参考。

  • Albert-László Barabási 撰写的 Network Science,这是一本入门电子书。
  • Complexity Explorer 提供的在线课程。
  • 新英格兰复杂系统研究所(New England Complex Systems Institute)提供的各种资源和论文。

图算法是分析关联数据的一种有效方法,因为图的数学运算是针对关系运算设计的。图算法描述了处理图以发现其一般性质或特定量所需的步骤。基于图论的数学原理,图算法利用节点之间的关系来推断复杂系统的组织形态和动态性。网络科学家利用这些算法来发现隐藏信息,检验假设,预测行为。

从防欺诈、优化呼叫路由到预测流感传播,图算法的应用非常广泛,例如对电力系统中达到过载条件的特定节点进行评分,或者在传输系统对应的图中发现拥塞分组。

事实上,美国民航系统在 2010 年经历了两起严重的旅客滞留事件,波及多个机场,事后人们使用图分析方法研究了这两起事件。网络科学家 P. Fleurquin、J. J. Ramasco 和 V. M.Eguiluz 使用图算法证实了这两起事件的部分原因是系统级联延迟,并在纠正建议中提到了这些信息,详见论文“Systemic Delay Propagation in the US Airport Network”。

为了将航空交通网络可视化,Martin Grandjean 在其文章“Connected World: Untangling the Air Traffic Network”中创建了如图 1-3 所示的图。这张图清晰地显示了航空交通簇这样高度连接的结构。许多交通系统的连接呈集中式分布,明显含有可影响延迟的中心辐射模式(hub-and-spoke pattern)。

图 1-3:航空交通网络展示了在多个尺度上演进的中心辐射结构,这些结构有助于调节交通流量

图还有助于揭示那些非常微小的交互和动态变化如何引发全局突变。通过精确表示哪些事物在全局结构中存在交互,图将微观尺度和宏观尺度紧密地联系在一起。这些关联关系可用于预测行为和确定缺失的联系。图 1-4 是草原物种相互作用的食物网,可使用图分析评估层级组织和物种相互作用,然后预测缺失的关系,参见 A. Clauset、C. Moore 和 M. E. J.Newman 的论文“Hierarchical Structure and the Prediction of Missing Links in Networks”。

图 1-4:这张草原物种的食物网通过图将小尺度的相互作用与更大尺度的结构形态关联了起来

1.3 图处理、图数据库、图查询和图算法

图处理是指执行图工作载荷和任务的方法。大多数图查询针对图的特定部分(例如起始节点),而且要做的工作通常集中在起始节点周边的子图中。我们将这类工作称为局部图处理,而且这意味着要以声明方式查询图的结构,参见 Ian Robinson、Jim Webber 和 Emil Eifrem 在《图数据库》一书中的解释。这类局部图处理通常用于实时事务处理和基于模式的查询。

当谈到图算法时,经常要查找全局模式和结构。算法的输入通常是整张图,其输出则既可以是一张增强的图,也可以是某种总值,比如得分。我们将这样的处理归类为全局图处理,这意味着要使用计算方法(通常是迭代的)来处理图的结构。这种方法通过网络的连接关系揭示其整体性质。很多组织倾向于使用图算法来对系统建模,并且基于事物传播途径、其重要组件、群组标识和系统的整体稳健性来预测行为。

这些定义可能存在一些重叠——有时也可以通过处理算法来应答局部查询,反之亦然。但是简而言之,对整张图的操作一般通过计算方法来处理,而对子图的操作一般通过数据库来查询。

传统上,事务处理和事物分析是相互独立的,这是一种基于技术限制的非自然分离。我们认为,图分析可以驱动更智能的事务,从而为进一步分析创造了新的数据和机会。最近出现了一种趋势,那就是将这两个部分集成起来,以实现实时决策。

OLTP和OLAP

联机事务处理(online transaction processing,OLTP)通常涉及一些短期活动,比如预订机票、记入账户、预售商品等。OLTP 提供海量低延迟查询处理和高数据完整性。虽然 OLTP 的每个事务可能只涉及少量记录,但是系统要同时处理许多事务。

联机分析处理(online analytical processing,OLAP)有助于对历史数据进行更复杂的查询和分析。这些分析可能涉及多个数据源、多种格式和类型。检测趋势、执行假设场景、进行预测和发现结构模式等都是典型的 OLAP 用例。与 OLTP 相比,OLAP 系统处理的事务更少,但是处理的记录更多且运行时间更长。OLAP 系统倾向于更快地读取数据,并不希望像 OLTP 那样出现事务更新,而且通常采用面向批处理的操作。

然而近年来,OLTP 和 OLAP 之间的界限开始变得模糊。现代数据密集型应用已将实时事务操作与分析结合起来。这种处理方式上的整合是由软件领域的进步推动的,例如可伸缩性更强的事务管理和增量流处理,以及低成本、大内存硬件的支持。

将分析和事务结合起来,就可以将连续分析作为常规作业的固有组成部分。针对从 POS 机、制造系统或物联网设备收集而来的数据,当前的分析手段已经能够在处理过程中实时推荐和进行决策。这种趋势在几年前就已经出现,用于描述这种融合的术语包括事务型分析(translytics)和混合事务与分析处理(hybrid transactional and analytical processing,HTAP)。图 1-5 演示了如何使用只读副本将不同类型的处理组合到一起。

图 1-5:事务处理需要一种支持低延迟查询处理和高数据完整性的混合平台,同时需要在海量数据之上集成复杂分析

Gartner 认为:

(HTAP)可能会重新定义一些业务流程的执行方式,因为实时高级分析(例如规划、预测和假设分析)变成了处理过程的组成部分,而不再是事后执行的单独活动。这将支持新型的实时业务驱动决策过程。最终,HTAP 将成为面向智能业务操作的关键支持架构。

随着 OLTP 和 OLAP 逐渐集成,开始支持以前仅在单个“竖井”中提供的功能,不再需要为工作载荷使用不同的数据产品或系统——可以使用相同的平台以简化架构。这意味着分析查询可以利用实时数据,而且可以简化分析的迭代过程。

1.4 为何要关心图算法

图算法有助于理解关联数据。关系广泛存在于现实世界的系统中,从蛋白质的相互作用到社交网络,从通信系统到电网,从零售体验到火星任务规划。理解网络及其内部联系为洞察和创新提供了不可思议的潜力。

图算法特别适用于理解结构和揭示高度关联的数据集中的模式。没有什么比大数据更能体现关联性和交互性了。大数据汇集、混合和动态更新的信息量令人瞩目。这正是图算法的用武之地,它有助于我们理解海量数据,针对关系进行更复杂的分析,还可以为人工智能丰富上下文信息。

随着数据之间的联系越来越紧密,理解数据之间的依赖关系变得越来越重要。研究网络增长的科学家注意到,连接性会随着时间的推移而增强,但是并不均匀。择优连接理论是研究动态增长如何影响结构的一种理论。如图 1-6 所示,该理论描述了这样一种趋势:一个节点倾向于连接到已经有很多连接的节点。

图 1-6:择优连接现象:一个节点的连接关系越多,就越有可能建立新的联系。这导致了不均匀的集中度和中心

Steven Strogatz 的著作《同步:秩序如何从混沌中涌现》给出了一些示例,解释了现实系统进行自组织的不同方式。不管潜在原因如何,许多研究人员相信,网络的增长方式与其最终形态和层级是密不可分的。高密度群组和块状数据网络会不断发展,复杂性会随着数据规模的增长而增长。从互联网到图 1-7 所示的游戏社区社交网络,在当今现实世界的大多数网络中存在这种关系的聚集现象。

图 1-7:对游戏社区的分析显示,在 382 个社区中,只有 5 个社区的连接最为集中

图1-7 所示的网络分析是由Pulsar 公司的Francesco D’Orazio 提出的,旨在辅助预测视频 的病毒式传播趋势并为制定视频分发策略提供信息。Francesco D’Orazio 发现,社区分布的 集中度和内容扩散速度存在相关性。

这与平均分布模型预测的结果截然不同。在平均分布模型中,大多数节点具有相同数量的 连接。如果万维网的连接是平均分布的,那么所有网页的出入链接数量都相同。平均分布 模型认为,大多数节点是平等连接的,但是许多类型的图和许多真实网络表现出集中式分 布特征。与旅行网和社交网络的图一样,Web 也具有幂律分布特征,即少数节点高度连 接,而多数节点的连接较少。

幂律

幂律(也称标度律)描述了两个量之间的关系,其中一个量随另一个量的幂而变化,例如一个立方体的体积是其边长的 3 次幂。一个著名的例子是帕累托分布(也称二八定律),它最初用来描述 20% 的人口控制 80% 的财富。在自然界和网络中存在各种幂律。

试图使网络均匀分布的想法通常不适用于研究关系或进行预测,因为现实网络中的节点和关系分布并不均匀。如图 1-8 所示,对不均匀的数据使用平均特征会导致错误的结果。

{%}

图 1-8:在现实网络中,节点和关系的分布不均匀,在极端情况下表现出幂律分布特征。均匀分布假设大多数节点具有相同数量的关系,这样产生的是一个随机网络

由于高度连接的数据并不遵循平均分布,因此网络科学家使用图分析来搜索和解释真实数据的结构和关系分布。

在已知的自然界中,没有任何一个网络可以用随机网络模型来描述。

——Albert-László Barabási,美国东北大学复杂网络研究中心主任,著有多本网络科学相关图书

大多数用户面临的挑战是,使用传统分析工具来分析密集而不均匀的关联数据非常麻烦。在数据中可能存在某种结构,但是很难找到。采用平均方法处理混乱的数据确实很诱人,但是这种做法会隐藏模式,而且结果无法代表任何真实群组。如果将所有客户的人口统计信息都做平均化处理,并且仅基于平均化处理结果来提供客户体验,那么肯定会漏掉大多数群体:社团往往是围绕年龄、职业、婚姻状况和地址等因素形成的。

此外,通过快照无法发现动态行为,尤其是那些围绕突发性事件和爆发性事件的动态行为。如果社交群体的人际关系不断增加,就意味着有更多的交流。这会导致出现协调临界点,随后出现联盟,或者形成子群体并出现两极分化(例如选举)。预测网络随时间的演变需要更复杂的方法,但是如果了解数据中的结构和交互,就能推断行为。由于图分析注重关系研究,因此也用于预测群组的弹性。

1.5 图分析用例

在最抽象的层次上,图分析可以应用于预测动态群组的行为和规定动作。要实现这一点,就需要了解群组内部的关系和结构。图算法通过检查网络连接的整体特性来实现这一点。通过这种方法,就可以理解关联系统的拓扑结构并为其流程建模。

关于是否需要采用图分析和图算法,图 1-9 列出了 3 类常见问题。

图 1-9:图分析所回答的问题类型

下面是图分析和图算法的一些用例。你所面临的挑战与之相似吗?

  • 调查传染病或级联传输故障的传播路径。
  • 发现网络中最易受攻击或最易损坏的组件。
  • 确定在传送信息或资源时速度最快、代价最小的方式。
  • 预测数据中缺失的联系。
  • 定位复杂系统中的直接影响和间接影响。
  • 发现不可见的层级结构和依赖关系。
  • 预测群组将合并还是分裂。
  • 发现瓶颈及有权拒绝或提供更多资源的个体。
  • 基于行为发现社团以进行个性化推荐。
  • 减少欺诈和异常检测中的假正例。
  • 为机器学习提取更多预测性特征。

1.6 小结

本章介绍了当今数据是如何紧密关联在一起的,以及其意义所在。在分析群组动态性和关系方面,目前已经有了活跃的科学实践,但是相关工具在很多行业不常见。在评估先进的分析技术时,应该考虑数据的本质特性,思考是否需要了解社团属性或预测复杂行为。如果数据用于表示某个网络,就应该避免这样做,不要缩减要素以采用平均模型,而应该使用与数据和所寻求的见解相匹配的工具。

第 2 章将介绍图的概念和术语。

目录

  • 版权声明
  • O'Reilly Media, Inc.介绍
  • 前言
  • 第 1 章 导论
  • 第 2 章 图论及其概念
  • 第 3 章 图平台和图处理
  • 第 4 章 路径查找算法和图搜索算法
  • 第 5 章 中心性算法
  • 第 6 章 社团发现算法
  • 第 7 章 图算法实战
  • 第 8 章 使用图算法增强机器学习
  • 附录 额外信息及资料
  • 关于作者
  • 关于封面