图是计算机科学的统一主题下的分支之一，这是一种抽象的表示形式，它描述了运输系统、人机交互和电信网络的组织。这么多不同的结构可以用单一的形式来建模，这给图程序员赋予了强大力量。 —The Algorithm Design Manual, by Steven S. Skiena (Springer), Distinguished Teaching Professor of Computer Science Stony Brook University

当今最紧迫的数据挑战，都集中在关系上，而不仅仅是把离散的数据进行表格化（tabulating discrete data）。图技术和分析为用于研究、社交行动和业务解决方案提供了强大的工具，比如:

• 用于从金融市场到IT服务的各类动态环境的建模
• 预测流行病的蔓延以及服务延误和中断
• 找到机器学习的预测性特征，以打击金融犯罪
• 发现个性化体验和推荐模式 随着数据日益互联，系统日益复杂，能否利用数据中丰富且不断发展的关系至关重要。本章介绍图分析和图算法。首先，我们将简要复习图的起源,然后引入图算法并解释图数据库和图处理之间的区别。我们将探讨现代数据本身的本质，也就是：数据网络的分析结果能够比基本统计方法的结果要精巧得多。本章最后将介绍可以使用图算法的一些用例。

什么是图？

图的历史可以追溯到1736年，当时Leonhard Euler（ 著名数学家欧拉）解决了"哥尼斯堡七桥问题”。这个问题是这样的，一个城市的所有四个区域由七座桥梁连接，问是否有路径能够访问整个城市，但只跨越每座桥梁一次。答案是没有这样的路径。随着思考的深入，欧拉发现只有连接本身是相关的，他因此建立了图理论及其数学的基础。图1-1描绘了Euler的进展与他的原始草图之一,这些图来源于论文“Solutio problematis ad geometriam situs pertinentis”。 图 1-1。图理论的起源。哥尼斯堡市包括两个大岛，通过七座桥梁连接彼此，并和城市的两个大陆部分相连接。题目是创造一次连续步行穿过城市,跨越每座桥一次,而且只有跨越一次。

虽然图起源于数学,但它们也是一种实用性和高保真度（high fidelity）的建模和分析方法。组成图的对象称为节点(node)或顶点(vertice)，它们之间的链接称为关系(relationship)、链接(link)或边(edge)。我们使用本书中的术语节点(node)和关系(relationship)：你可以想到节点作为句子中的名词,将关系作为动词,为节点提供上下文。为了避免任何混淆,我们在这本书中谈论的图与方程绘图(graphing equation)或表格图表(chart)没有任何的关系,如图 1-2 所示。 图 1-2。图是网络的表示形式,通常用圆圈表示我们调用节点的实体,以及表示关系的线路。左侧是Graph（图），右侧不是Graph，它们是方程绘图(graphing equation)或者是图表(chart)。

查看图 1-2 中的人员关系图,我们可以轻松地构造几个句子描述它。例如，A与拥有汽车的人B住在一起,A驾驶B拥有的汽车。这种建模方法极具吸引力，因为它很容易映射到现实世界,并且非常"白板友好”（意思是，能够很轻松地在白板上画出数据的模型）。这非常有助于数据建模和分析。

但建模一个图只是开始，我们可能还希望将它们处理到形成洞察力的水平。那就到了图算法的领域。

什么是图分析和算法？

图算法是图分析工具的子集。（图分析是一个比图算法更宽的概念，它包含图算法。）

图分析指的是，使用任何基于图的方法来分析数据网络。我们可以使用各种方法:可以查询图数据,使用基本统计,直观地探索图,或将图纳入我们的机器学习任务。基于图的模式查询通常用于本地数据分析,而图计算算法通常引用更全局和迭代分析。尽管在如何使用这些类型的分析方面存在重叠,但我们使用术语**图算法（graph algorithm）**来表示后者,它用于更密集的计算分析和数据科学用途。

图算法提供了分析数据网络的最有效方法之一,因为它们的数学基础是专门为处理关系而构建的。它们描述了处理图发现一般或特定品质的步骤。基于图理论的数学（图论，graph theory）,图算法用节点之间的关系推断出复杂系统的组织和动力学特性。网络科学家使用这些算法来发现隐藏的信息、测试假设，并预测行为。

网络科学 网络科学是一个学术领域,它深深植根于图论,它涉及到对象之间关系的数学模型。因为他们的数据量大小、连接性和复杂性的不同，网络科学家需要依赖于图算法和数据库管理系统。 关于复杂性和网络科学，有许多奇妙的资源。下面是一些可供您探索的参考。 • Network Science,由Albert-László Barabási著,是一个入门级的电子书 • Complexity Explorer提供在线课程 • New England Complex Systems Institute提供各种资源和论文

图算法具有广泛的潜力,比如从防止欺诈和优化呼叫路由到预测流感的传播。例如,我们希望对电力系统中的可能过载的特定节点进行评分。或者,我们希望在一个运输系统中发现阻塞的区域。

事实上,在 2010 年,美国航空旅行系统经历了两起严重的事件,涉及多个拥堵的机场。后来，网络科学家P.Fleurquin、J.J.Ramasco和V. M. Eguíluz使用图算法来确认这两个事件作为系统级联延迟（多级延迟，cascading delay）的一部分,并利用这些信息进行改进性建议。这些成果发表在"Systemic Delay Propagation in the US Airport Network”这个论文中。

为了可视化支撑航空运输的网络，图1-3是Martin Grandjean为他的文章"Connected World: Untangling the Air Traffic Network”创作的配图。该图清楚地显示了航空运输集群的高度连接结构。许多运输系统都表现出了集中的分布,有明确的枢纽和辐条模式,容易会产生延误。 图 1-3。航空运输网络展示了在多个尺度上演变的枢纽和辐条结构。这些结构解释了乘客流动的模式。

图还有助于揭示导致全球突变中非常小的相互作用和动力学。比如通过精确地表示全球结构内交互的事物，将微观和宏观尺度结合在一起。这些关联用于预测行为并确定缺失的连接。图1-4是草原物种的食物链网络，该图被用来评估分层组织和物种的相互作用，然后预测缺失的关系。该成果由A. Clauset, C. Moore,和M. E. J. Newman在论文“Hierarchical Structure and the Prediction of Missing Links in Network”中发表。 图1-4.这个草原物种的食物链网络，使用图将小规模的相互作用与大的结构形成联系起来。

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

图处理（graph processing）包含了那些承载了图相关工作负载和任务的方法。大多数图查询都考察图的特定部分（例如，起始节点），工作通常集中在周围的子图形中。我们将这种类型的工作称为图局部(graph local)，图局部意味着声明式地（用一种声明式的语言）查询一个图的结构，正如Ian Robinson, Jim Webber, 和Emil Eifrem在《Graph Databases》（O’Reilly）这本书中所解释的那样。这种图局部处理通常用于实时事务和基于模式的查询。

在谈到图算法时，我们通常会寻找全局模式和结构。算法的输入通常是整个图，输出可以是一个图中被增加的属性，或一些聚合值，如分数。我们将这种处理归类为图全局（graph global），它意味着使用计算算法（通常是迭代的）处理图形的结构。这种方法通过连接来揭示了网络的整体性质。组织倾向于使用图算法来建模系统，并根据事物的传播方式、重要组件、组标识和系统的整体鲁棒性来预测行为。

在图局部和图全局的定义中，可能有些重叠，有时我们可以使用算法的处理来回答本地查询，反之亦然。但通常意义上，可以简单的认为，全图的操作是由计算算法处理的，子图的操作是在数据库中查询的。

传统上，事务处理和分析都是孤立的。这种人为的隔阂是因为技术的限制造成的。我们的观点是，图分析推动更智能的交易，为进一步分析创造新的数据和机会。最近出现了一种将事务处理和分析集成在一起的趋势，以便实现更实时的决策。

OLTP和OLAP

在线交易处理（OLTP，Online transaction processing）通常是短时间内的行为和操作，如预订机票、贷记账户、预订销售等。OLTP的主要任务是实现大量的低延迟查询处理和高数据完整性。OLTP的每个事务可能只涉及少量记录，为了应对业务，OLTP会并行处理许多事务。

在线分析处理（OLAP，Online analytical processing）有助于对历史数据进行更复杂的查询和分析。这些分析可能包括多个数据源、格式和类型。检测趋势、执行假设中的场景、进行预测和发现结构模式是典型的OLAP的用例。与OLTP相比，OLAP系统在大规模记录上运行长时间的分析任务，但和不一定都是事务。

OLAP系统倾向于快速读取，而尽量减少在OLTP中经常出现的事务（如更新）。在OLAP中，面向批处理的操作是常见的。

然而，最近，OLTP和OLAP之间的界限开始变得模糊。现代数据密集型应用程序现在将实时事务操作与分析相结合。这种处理的集成，是由软件方面的一些进步，如更可扩展的事务管理和增量流处理，以及成本更低的大内存硬件所推动的。将分析和事务结合在一起，可以使连续分析成为常规操作的自然组成部分。随着数据从销售点（POS）机器、制造系统或物联网（IOT）设备中不断收集，现代的数据分析支持在处理过程中进行实时推荐和决策的能力。这一趋势是在几年前观察到的，转义（translytics）和混合事务和分析处理（HTAP，hybrid transactional and analytical processing）这些术语就是用来描述这些进步的。图1-5说明了只读副本是如何被用于这些不同类型的处理的（指的是OLTP和OLAP）。 图1-5.混合平台，支持了事务处理所需的低延迟查询处理和高数据完整性，又同时集成对大量数据的复杂分析。

Gartner： 因为实时高级分析（例如：计划、预测和假设分析）成为流程本身的一个组成部分，而不是事后执行的单独活动，HTAP会重新定义一些业务流程的执行方式。这种改进将使实时业务驱动决策过程成为可能，最终，HTAP将成为智能业务运营的关键支持架构。

随着OLTP和OLAP变得更加集成，并开始支持以前仅在单独的服务中提供的功能，这使得我们不再需要使用单独的OLAP和OLTP产品。我们可以通过使用相同的平台来简化架构，这意味着我们的分析查询可以利用实时数据，这可以简化分析的迭代过程。

为什么我们要关心图算法？

图算法被用于帮助理解数据网络。我们可以看到现实系统中的关系，比如从蛋白质之间交互到社交网络，从通信系统到电网，从零售体验到火星任务规划。了解网络及其内部连接为洞察和创新提供了难以置信的潜力。

图算法特别适合在高度连接的数据中发现出集中结构和展现出模式。没有什么地方比大数据有更显著的连通性和交互性了。在大数据中，有大量的汇集、混合和动态更新的信息量。大数据中，图算法可以帮助理解我们的数据总体，我们也可以通过更复杂的分析，用关系来为人工智能提供上下文信息和特征。

随着我们的数据变得越来越紧密，了解它的关系和相互依赖性变得越来越重要。研究网络增长的科学家们注意到，连接性随着时间的推移而增加，但并不一致。择优附着（preferential attachment）是研究生长动力学对结构影响的理论之一。如图1-6所示，这个想法描述了一个节点链接到已经有很多连接的其他节点的趋势。 图1-6.择优附着指的是一个节点连接越多，接收新链接的可能性就越大的现象。这会导致不均匀的浓度和中心化。

在Steven Strogatz的书《Sync: How Order Emerges from Chaos in the Universe, Nature, and Daily Life》（Hachette）中，他用例子解释了现实生活系统进行自我组织的不同方式。不管潜在的原因是什么，许多研究人员认为，网络的发展与其产生的形状和层次结构密不可分。高度密集的群体和块状数据网络往往会被发展起来，随着数据规模的增加，复杂性也在增加。我们今天看到了大多数现实世界网络中的这种关系集群，从互联网到社交网络，如图1-7所示的游戏社区。 图1-7.这个游戏社区分析显示，382个社区中只有5个社区的有密集的连接。

图1-7所示的网络分析是由Pulsar的Francesco D’Orazio创建的，用于帮助预测内容的重要性和分发信息的策略。D’Orazio发现了一个社区的分布集中度和一段内容的传播速度之间的相关性。

以上这些（择优附着、中心化、不均匀）与平均分布模型（average distribution model）有很大的不同。在平均分布模型中，大多数节点的连接数都相同。例如，如果万维网拥有平均分布的连接，那么所有页面进出的链接数将大致相同，因为平均分布模型的假设就是：大多数节点是相等连接的，但许多类型的图和许多实际网络表现出集中特性。网络、旅游和社交网络等图形一样，具有幂次法则分布，其中一些节点高度连接，大多数节点适度连接。

幂次法则（power law） 幂次法则（也称为比例规律）描述了两个量之间的关系，其中一个量随另一个量的幂而变化。例如，一个立方体的面积与其边长的幂为3有关。一个著名的例子是帕累托分布或“80/20规则”，最初用来描述20%的人口控制了80%的财富。我们在自然世界和网络中也能看到各种幂次法则。 试图“平均”一个网络通常不会很好地用于调查关系或预测，因为现实世界中的网络具有不均匀的节点分布和关系。我们可以很容易地在图1-8中看到，对不均匀的数据使用平均特征将导致不正确的结果。 图1-8.现实世界中的网络节点和关系分布不均匀，其极端表现为幂次法则分布。平均分布假定大多数节点具有相同数量的关系，并在随机网络中生成结果。

由于高度连接的数据不遵循平均分布，网络科学家使用图分析来搜索和解释现实世界中结构和关系分布。

**我们所知道的自然界中没有一个网络可以用随机网络模型来描述。**
Albert-László Barabási, Director, Center for Complex Network Research,
Northeastern University，众多网络科学图书的作者

大多数用户面临的挑战是，用传统的分析工具分析数据时，连接紧密且不均匀是很麻烦的。那里可能有一个结构，但很难找到。对杂乱的数据采用平均方法是很有诱惑力的，但这样做会隐藏很多模式，而且我们的结果不代表任何真实的群体。例如，如果你对所有客户的人口统计信息进行平均，并且仅仅根据平均值提供一种体验服务，那么你肯定会错过大多数社区：社区倾向于围绕年龄、职业或婚姻状况和位置等相关因素聚集。

此外，动态行为，特别是在突发事件和突发事件周围，是不能用平均化的快照看到的。举例来说，你想象一个社会团体的人际关系不断增加，你也会期待更多的交流。这可能导致协作的拐点，随后的联盟或小团体的形成或极化。所以，需要复杂的方法来预测一个网络随着时间的发展，如果我们了解数据中的结构和交互，我们可以推断出行为。由于各种关注关系的存在，图分析被用于预测群体的弹性。

图分析用例

在最抽象的层次上，图分析应用于动态群体的行为预测和行动规划，这需要对团队的关系和结构进行了解。图算法通过检查网络的连接来实现这一点。通过这种方法，你也可以了解相互连接的系统群的拓扑结构，并对其流程建模。

有三大类问题，表明图分析和算法是否有必要，如图1-9所示。 图1-9.图分析能够回答的问题类型

这些都是图算法能够解决的问题。你的挑战相似吗？

• 调查疾病或级联传输失败的路径。
• 发现网络攻击中最易受攻击或损坏的组件。
• 找出最便宜或最快的信息或资源路由方法。
• 预测数据中丢失的链接。
• 定位复杂系统中的直接和间接影响。
• 发现看不见的层次结构和依赖关系。
• 预测团队是合并还是分离。
• 找出瓶颈或谁有能力拒绝/提供更多资源。
• 展示基于行为的社区，提供个性化建议。
• 减少欺诈和异常检测中的误报。
• 提取更多机器学习的预测特征。

结论

在本章中，我们研究了今天的大数据是如何紧密相连的，以及这一点给我们的启示。在分析群体动态和关系方面存在着强大的科学实践，但这些工具在企业中并不总是常见的。在高层级的分析中，我们应该考虑数据的品质，了解社区的属性，预测复杂行为。如果我们的数据是一个网络，我们应该抵制用平均值考虑问题的诱惑。相反，我们应该使用与我们的数据和我们正在寻求的见解相匹配的工具。在下一章中，我们将介绍图概念和术语。

《图算法》的连载。分享给对图计算感兴趣的朋友们。 公众号：《 Medical与AI的故事》 原文链接：https://mp.weixin.qq.com/s/gy1TdM4vmZqvFalZrTxrlQ