2.1 图算法的分类

所有的图算法在本质上都是对更为基础的图上的计算、分析与查询操作的高度概括与集成。那么，什么是基础的图上的计算、分析与查询操作呢？可以简单概括为以下两类操作。

❑ 面向元数据的低维、离散的操作。典型的例如面向顶点或边的聚合、排序等操作。

❑ 面向高维数据的操作。典型的例如路径、子图、网络查询以及图算法等操作。

从图计算的视角，面向元数据的操作与之前所有SQL或NoSQL数据库没有本质区别，因此并不是本书的重点。面向高维数据的操作，指的是从关联数据的角度，查询数据之间的关联关系、关联路径和影响力范围，例如我们常说的根因分析（Root-cause Analysis）、贡献度分析（Contribution Analysis）、归因分析（Attribution Analysis）、影响力分析（Impact Analysis）、溯源分析（Backtracing）等。通过构建图数据模型，然后进行图上的查询与分析，通常会获得更高效、更灵活、更白盒化且更具可解释性的效果。

高维数据的查询有3个子类。

❑ 邻居查询：如最典型的k邻查询。

❑ 路径查询：如最短路径、环路、权重路径等。

❑ 展开、组网等其他较复杂查询：如从某顶点展开、多顶点组网等。

当然，所有的高维查询都可以通过拆解或分而治之的方式降维为低维查询，因为它们都是从某个或某类元数据（如顶点、边或其属性字段）开始操作的，而这些高维查询再进行组合、聚合、变形，就形成了我们所谓的图算法。例如度算法中的全图入度查询，本质上就是计算所有顶点的入度。显然，在一张大图上，这个看似简单的算法的计算复杂度可能会非常高，如何进行加速就变成了重要的议题，我们会在第3章中进行详细分析。再比如全图k邻查询（k-Hop Neighbors，k跳邻居），在连通度较高的图中，即便是查询1个顶点的3跳、5跳邻居都可能会非常耗时（假如1个顶点的1跳邻居有20个，2跳邻居有400个，3跳邻居有8000个，而5跳邻居已经在3200000个的量级），如果有10000000个顶点，那么运行完这个算法的耗时和复杂度将是天文量级的。不经优化的图算法很多都是不具备实用性的，而优化可以获得指数级的性能提升与耗时降低—可能原来需要运行1个月的算法，如果在不增加硬件投入的前提下能提速1000倍，降低至0.7h（约40min）内完成，其意义是不言而喻的！这也是为什么图算法的性能优化如此重要。

在剖析图算法的具体分类之前，我们先了解一个设计良好的图算法应该具备的特征。通过梳理过去一个半世纪以来多位数学家和计算机学家对于算法特征的共性探讨，我们总结了如下5点：

1）无歧义，即确定的操作逻辑。

2）清晰、明确的操作步骤。

3）具备良好的可行性（如时间、空间、复杂度与效率）。

4）定义了明确的输入、输出规则，以及可验证正确性。

5）在有限步骤内可以完成。

第一点关注算法中的每一步操作都应该是可以明确定义与执行的，即便是某种随机化的操作。例如在后面的章节中介绍的随机游走算法：从任意一个顶点出发，选中顶点的任意一个邻居顶点作为访问的下一个顶点。算法的每一步操作都需要明确无歧义。

第二点关注算法的执行步骤（多步）应该有明确、清晰的定义。这可以看作对第一点中每个步骤的一种融会贯通。

第三点关注算法的可计算性、可行性，包括但不限于对系统资源的消耗，特别是算法的复杂度（如时间复杂度、空间复杂度等）。我们在第3章中会进行详细剖析。

第四点中讨论的要点可分为两个维度，一是对于输入、输出数据的定义与预期，二是数据的正确性验证。显然，错误的输入数据与错误的输出结果只会带来GIGO（Garbage-In and Garbage-Out，表示进去和出来的都是垃圾）。

最后一点与第三点略有重叠，但是它着重突出的是算法可以在有限步骤内得以终结。在这个前提下，我们需要关注算法占用的计算与存储资源以及执行时间与效率等。如果一个算法永远不会终结，那么它对于实际场景应用而言会是灾难，意味着系统资源会被耗尽，出现灾难性的后果。显然，我们需要尽可能避免这种情况的发生。

关于图算法的分类，业界并没有严格意义上的共识。有的侧重于学术研究的图计算框架，甚至会把广度优先搜索（BFS）或深度优先搜索（DFS）作为算法单列，尽管它们更适合作为一种图遍历模式存在。还有的如最短路径算法，在20世纪计算机发展的前30年间（20世纪40年代至70年代），最短路径算法不断推陈出新，对于计算机体系架构的发展有相当大的推动作用。图2-2示意了一种典型的在图上寻路所对应的算法分类情况。

如图2-2所示，DFS算法实现的是一种随机游走式的寻路，且不关心路径是否最短。BFS算法实现的是无权重最短寻路，而Dijkstra算法则实现的是有权重最短寻路。

我们在研究图算法的分类时，一般都把图算法归类为组合数学算法的一部分，因为组合数学涉及的领域相当广泛，而图论是其中相当重要且有代表性的一部分。在组合数学中，几乎所有的著名问题，如旅行商问题、地图着色、任务分配、线性规划（过河问题）等，都与图论或离散数学相关。按照在组合数学中的图论类算法，可以简单地把算法作如下分类。

❑ 图路由类算法：最小生成树类算法、最短路径问题、最长路径问题、旅行商问题等。

❑ 网络分析与网络流算法：链接分析、网页排序算法、网络最大流问题等。

❑ 图搜索类算法：A*、B*、暴力搜索、回溯问题、双向搜索算法等。

❑ 子图类算法：强链接子图、团（Clique）、同态子图等。

❑ 图可视化类算法：力导向图、频谱布局、分层渲染、弧式图等。

❑ 其他图算法：染色类算法、拓扑排序算法、图匹配算法、最大势问题等。

我们还可以按照如下五大维度分别对图算法进行分类，每个分类下又有一些典型子类算法。

1）按设计模式分类，可分为以下6类：

❑ 遍历式（列举式）。在图算法以及图查询模式中，遍历式是最为常见的。像广度优先算法与深度优先算法是最常用的图遍历模式，很多现实世界的问题就是通过这些遍历模式解决的，如象棋、围棋对弈问题。下面的回溯式算法也可以看作遍历式的一种特例。

❑ 穷举式（暴力计算）。在海量数据集上，穷举式计算并不一定是可行的，但很多情况下带有过滤（图上剪枝）规则的穷举式计算又是必要的。例如在工商数据集中，搜索一个自然人与一个发行人（上市公司）之间的全部最短关联路径是完全可行的，即便两者之间存在成千上万条路径。

❑ 分而治之。分而治之是算法设计中最经典的思路，把大的问题缩小，把大的数据集缩小，通过递归、并发、分布式等方法来分块处理，最后再汇总来解决全量的问题。二进制搜索、全图k邻算法等都是典型的采用分而治之的模式来解决问题的算法。

❑ 回溯式、回溯式算法通常用于解决约束满足问题，如各种迷宫或字谜类的益智游戏（如经典的国际象棋八皇后问题、数独问题、背包问题等）、地图着色问题、最大割问题等。因为有约束条件限定，算法在进行某种随机遍历的过程中可能会通过回退（即回溯或剪枝）来优化遍历以找到正确的结果。

❑ 随机化。通过随机操作的方式来求解的算法在学术界与工业界都很常见，例如蒙特卡罗类算法在连通图中计算最小割问题的Karger算法，就是通过随机删除图中的边并合并删前相连顶点的方式来实现以多项式时间复杂度（参见下文中的按复杂度分类）求解问题。

❑ 归约式。归约式算法通过把一个问题转换（如映射）成另一个问题，进而寻求一种更简约的解决问题的方式。例如广度优先搜索求某个（群）顶点的k跳邻居中年龄最大者（或最小，或任意可度量维度或属性）的过程中，需要对结果集进行排序（转换），然后选取最大结果值返回，这就是一种典型的先转换再求解的归约式算法。

2）按优化问题模式分类，可分为以下3类：

❑ 线性规划（LP）。在最优化问题求解的过程中，经常会遇到线性规划问题，如商业管理中的降本增效问题、交通能源与通信领域的最大网络流问题等。

❑ 动态规划（DP）。在经济学与航空工程学领域经常会遇到动态规划问题。简而言之，动态规划问题一般通过把复杂的问题以递归的方式分解为更小的问题并找到最优解来说明该问题具备最优子结构（Optimal Substructure）。例如，只要能证明贪心算法中的每一步都是最优的，就可以用它来解决具有最优子结构的问题。贪心算法通常可以被看作动态规划类算法的一个特例，最小生成树（MST）类算法就是典型的通过分解子结构来实现的贪心算法。

❑ 启发式算法。启发式算法是在常规方式无法找到最优解的情况下（太慢或效果太差），通过在精度、准确性、完整性、最优性等维度之间进行协调取舍，进而实现一种近似最优解的算法方案。

3）按复杂度分类。可分为以下5类：

❑ 恒定时间。复杂度O（1）就是典型的恒定时间。比如，无论数据集大小，通过数组或向量数据结构访问任一顶点所需的时间恒定为O（1）。

❑ 线性时间。访问时间与输入数据集大小成正比，例如遍历全部顶点所需时间与数据集大小呈线性。

❑ 对数时间。典型的是二叉树（或多叉树）搜索类算法，比如在常见的数据库索引数据结构中，定位任一叶子节点所需的时间与数据集大小呈对数关系。显然，在数据集相同的情况下，对数时间要比线性时间更短。

❑ 多项式时间。从时间复杂度上比较，指数时间要比多项式时间更长。两者量化的区别用一个具体的例子来说明，如果数据量为N，多项式时间可能是aN3+bN2+1，而指数时间是N100，后者比前者复杂度更高。

❑ 指数时间。通常我们认为，在大数据集上，如果一个算法是指数时间复杂度，则不具备真正意义上的可实施性。因为计算复杂度可以理解为无穷大，问题无法在有限时间内得到解决。例如穷举式暴力搜索算法，其算法复杂度与输入数据集大小呈指数关系，穷举全部可能的结果并不现实，这时通常会采用近似算法把时间复杂度至少降低到多项式时间。

4）按实现方法分类，可分为以下5类：

❑ 递归与非递归。每一个算法都可以以递归或非递归的方式实现，区别在于实现算法的逻辑步骤以及具体使用的数据结构，进而导致具体的算法实现方式的效率有所不同。

❑ 串行与并行。几乎所有的图算法初始都是以串行的思路设计的，但是很多都可以通过并行（并发）来得到性能的大幅提升。

❑ 集中式与分布式。同上，分布式要求对算法的数据结构及系统架构进行大幅改造，有的算法进行简单改造就可以获得很好的分布式条件下的效率提升，但有些算法采用分布式可能会出现指数级的性能下降。因此，改造与否、如何改造是研究算法与系统架构设计的专业人士需要格外注意的地方。

❑ 确定性与非确定性。所谓启发式算法指的就是后者。

❑ 精确式与近似式。有一部分图算法可以采用近似求解的方式来使之前极高的算法复杂度得到指数级降低，从而达到资源消耗可控的目的。

5）按研究领域分类。领域划分通常没有明确的边界，且多个领域之间会有大量的重叠，因此这种划分方式并不固定。

❑ 搜索。搜索又可以细分为路径搜索、元数据搜索、子图（网络）搜索等。

❑ 排序。排序又可细分为元数据排序、路径长短排序、图规模排序等。

❑ 合并。在图查询与算法的计算过程中，合并是个极为常见的操作，具体的逻辑类似于合并排序（Merge Sort）算法，特别是在多线程并发情况下的算法实现。

❑ 数值分析。数值分析在本质上是一种数值化近似方式的算法，通过量化的方式来加速求解，比如，保险行业精算师的主要工作就是进行数值分析，以及金融业中的存贷款定价、风险量化分析等操作，都可以通过数值分析类算法来实现。而通过巧妙设计的图算法，可以让这些数值分析的准确度、效率与可解释性都远超之前基于机器学习、深度学习的方法。

工业界的图数据库厂商可能还会有不同的分类方法，图2-3所示也是一种算法分类（5类）。

本书在后面的章节中综合了学术界和工业界图计算领域目前最新的发展情况，把图算法划分为了以下六大类，并分别对应第4～9章的内容：

❑ 中心性（Centrality）算法：如节点出入度、全图出入度、接近中心性、中介中心性、图中心性、调和中心性等。

❑ 相似度（Similarity）算法：如杰卡德（Jaccard）相似度、余弦相似度、欧几里得距离等。

❑ 连通性和紧密度（Connectivity）算法：如强弱连通分量、三角形计算、二分图、MST、全图k邻等。

❑ 拓扑链接预测（Topology&Connectivity）算法：共同邻居、AA指标、优先连接等。

❑ 传播与分类（Propagation & Categorization）算法：如LPA、HANP算法、k均值、鲁汶识别等。

❑ 图嵌入（Graph Embedding）算法：如随机游走、FastRP、Node2Vec、Struc2Vec、GraphSAGE等。

需要指出的是，分类有助于我们梳理知识，但也并非一成不变。有一些算法可能会横跨在多个分类中，例如MST既属于连通性和紧密度算法又属于拓扑链接预测算法。算法本身也会不断演进，推陈出新。有一些算法在发明之时做了一些假设，但是随着时代的变化，那些假设已不再适合了。仍以MST算法为例，它的最初目标是从一个顶点出发，使用权重最小的边连通与之关联的所有节点，该算法假设全图是连通的（即只有一个连通分量）。而很多真实的场景中存在大量的孤点以及多个连通分量，此时算法就需要去适配这些情况，在算法调用接口及参数上就需要支持多顶点ID、允许指定权重对应的属性字段，以及支持限定返回结果集数量等。

最后，我们用一张脑图来总结图算法的分类，如图2-4所示。