来源：数据科学一线DSFrontier
本篇博文的主要内容来源于 O’Reilly 系列的《GraphAlgorithms》，对图算法进行了综述介绍，作者为 Amy E. Hodler & Mark Needham。
网址：https://learning.oreilly.com/library/view/graph-algorithms-/9781492060116/
你肯定没有读过这本书，因为这本书的发布日期是2019年5月。本文会覆盖该书的大部分内容，读完这篇，你能够了解图算法的基本概念。关于此书，作为市面上为数不多的面向数据科学应用的图算法书籍，写的比较全面系统和易懂。当然，书在细节上的提高空间还有很多。今天内容很多，坐稳~
目录
图算法 & 图分析
图基础知识
连通图与非连通图
未加权图与加权图
有向图与无向图
非循环图和循环图
图算法
路径搜索算法
DFS & BFS
最短路径
最小生成树
随机游走
中心性算法
DegreeCentrality
ClosenessCentrality
BetweennessCentrality
PageRank
社群发现算法
MeasuringAlgorithm
ComponentsAlgorithm
LabelPropagation Algorithm
LouvainModularity Algorithm
结论
图分析使用基于图的方法来分析连接的数据。我们可以：查询图数据，使用基本统计信息，可视化地探索图、展示图，或者将图信息预处理后合并到机器学习任务中。图的查询通常用于局部数据分析，而图计算通常涉及整张图和迭代分析。
图算法是图分析的工具之一。图算法提供了一种最有效的分析连接数据的方法，它们描述了如何处理图以发现一些定性或者定量的结论。图算法基于图论，利用节点之间的关系来推断复杂系统的结构和变化。我们可以使用这些算法来发现隐藏的信息，验证业务假设，并对行为进行预测。
图分析和图算法具有广泛的应用潜力：从防止欺诈，优化呼叫路由，到预测流感的传播。下图是 Martin Grandjean 创建的航线网络图，这幅图清楚地展示了航空运输集群高度连接的结构，帮助我们了解航空运力如何流动。航线网络采用典型的辐射式结构（hub-and-spoke structure），这样的结构在有限运力的前提下，增大了航线的网络的始发-到达对（OD Pair），然而却也带来了系统级联延迟的可能。
我们已经在前一篇博文中介绍了属性图的概念。我们已经知道了节点、关系、属性（Property）、标签等概念。
子图（Subgraph）是一张图的一部分。当我们需要对图中的特定节点，特定关系，或者特定标签或者属性进行特定分析时，子图就会很有用。
路径（Path）是一组节点及他们的关系的集合。以上图为例，“Dan” 开过型号为 “Volvo V70” 的车，这辆车是属于 “Ann” 的。那么节点 “Dan” “Ann” “Car”和关系 “Drives” “Owns” 组成了一个简单的路径。
我们在介绍图算法前，先梳理一下图的不同属性（Attribute）。
连通图与非连通图
连通图（Connected Graphs）指图内任意两个节点间，总能找到一条路径连接它们，否则，为非连通图（Disconnected Graphs）。也就是说，如果图中包含岛（Island）,则是非连通图。如果岛内的节点都是连通的，这些岛就被成为一个部件（Component，有时也叫 Cluster）。
有些图算法在非连通图上可能产生无法预见的错误。如果我们发现了未预见的结果，可以首先检查图的结构是否连通。
未加权图与加权图
未加权图（Unweighted Graphs）的节点和边上均没有权重。对于加权图（Weighted Graphs），所加权重可以代表：成本、时间、距离、容量、甚至是指定域的优先级。下图给出了示意图。
基本的图算法可以通过处理权重来代表关系的强度。许多算法通过计算指标，用作后续算法的权重。也有些算法通过更新权重值，来查找累计总数、最小值或最优化结果。
关于加权图的一个典型用途是路径寻找算法。这些算法支持我们手机上的地图应用程序，并计算位置之间最短/最便宜/最快的运输路线。例如，下图使用了两种不同的方法来计算最短路线。
如果没有权重，计算最短路径时，实则在计算关系（Relation，也称 Hop）的数量。那么在上图左边，我们找到 A 和 E 之间的最短距离为 2，经过 D 点。如果像上图右边所示，边被赋予了权重，用以代表节点之间的物理距离（单位：KM）。那么我们可以找到 A 和 E 之间的最短距离是 50 KM，需要经过 C 和 D 两个点。而此时，在未加权图中计算的最短路径 A-D-E 距离为 70 KM，比我们找到的路径 A-C-D-E 距离远。
有向图与无向图
在无向图（Undirected Graphs）中，节点的关系被认为是双向的（bi-directional），例如朋友关系。而在有向图（Directed Graphs）中，节点的关系可以指定方向。边如果指向了一个节点，我们称为 in-link，边如果从一个节点出发，我们称为 out-link。
边的方向加入了更多维度的信息，同样关系的边，却包含不同的方向，则代表了不同的语义信息。如下图所示，有向图绘制了一个简单的同学网络，边的方向代表着 “喜欢”。那么从图中，我们可以知道，同学中 “最受欢迎的” 的人是 “A” 和 “C”。
我们还可以用道路网络帮我们理解为什么需要有向图和无向图。例如，高速公路一般都是双向的，我们使用无向图即可。但是，在城市内部，经常会有单向车道，我们必须使用有向图。
非循环图和循环图
图论中，循环指一些特殊的路径，它们的起点和终点是同一个节点。在非循环图（Acyclic Graph）中，不存在循环路径，相反则为循环图（Cyclic Graphs）。如下图所示，有向图和无向图都可能包含循环，所不同的是，有向图的路径必须遵循边的方向。图中的 Graph 1 是一个典型的 DAG（Directed Acyclic Graph，有向无循环图），并且 DAG 通常有叶子节点（leaf node，也称 dead node）。
Graph 1 和 Graph 2 是无循环的，因为我们在不重复任何一条边的情况下，无法从任何一个点出发，再回到它。Graph 3 中有一个简单的循环 A-D-C-A。而 Graph 4 中，我们可以发现多个循环：B-F-C-D-A-C-B，C-B-F-C 等等。
循环在图中非常常见。有时，我们为了提高处理效率，会将循环图转化为非循环图（通过剪除一些关系）。DAG 在调度、版本控制等问题中十分常见。实际上，我们在数学或者计算机科学中经常遇见的树（Tree）就是一个典型的 DAG，只是对于树来说，只能拥有一个 Parent，而 DAG 没有这个限制。
我们关注三类核心的图算法：路径搜索（Pathfinding and Search）、中心性计算（Centrality Computation）和社群发现（Community Detection）。
路径搜索算法
图搜索算法（Pathfinding and Search Algorithms）探索一个图，用于一般发现或显式搜索。这些算法通过从图中找到很多路径，但并不期望这些路径是计算最优的（例如最短的，或者拥有最小的权重和）。图搜索算法包括广度优先搜索和深度优先搜索，它们是遍历图的基础，并且通常是许多其他类型分析的第一步。
路径搜索（Pathfinding）算法建立在图搜索算法的基础上，并探索节点之间的路径。这些路径从一个节点开始，遍历关系，直到到达目的地。路径搜索算法识别最优路径，用于物流规划，最低成本呼叫或者叫IP路由问题，以及游戏模拟等。
下图是路径搜索类算法的分类：
DFS & BFS
图算法中最基础的两个遍历算法：广度优先搜索（Breadth First Search，简称 BFS）和深度优先搜索（Depth First Search，简称 DFS）。BFS 从选定的节点出发，优先访问所有一度关系的节点之后再继续访问二度关系节点，以此类推。DFS 从选定的节点出发，选择任一邻居之后，尽可能的沿着边遍历下去，知道不能前进之后再回溯。
下面是两张同样的图，分别采用 BFS 和 DFS 进行图的遍历，图上节点的数字标识这遍历顺序。
BFS
DFS
对于我们数据科学的角色来说，我们很少真正需要使用 BFS 和 DFS。这两个图搜索算法更多地作为底层算法支持其他图算法。例如，最短路径问题和 Closeness Centrality （在后文会有介绍）都使用了 BFS 算法；而 DFS 可以用于模拟场景中的可能路径，因为按照 DFS 访问节点的顺序，我们总能在两个节点之间找到相应的路径。感兴趣的话，可以猜一猜，后文介绍的算法是否使用了图搜索算法，并且分别使用了 DFS 还是 BFS。
最短路径
最短路径（Shortest Paths）算法计算给定的两个节点之间最短（最小权重和）的路径。算法能够实时地交互和给出结果，可以给出关系传播的度数（degree），可以快速给出两点之间的最短距离，可以计算两点之间成本最低的路线等等。例如：
最常见的最短路径算法来自于 1956 年的 Edsger Dijkstra。Dijkstra 的算法首先选择与起点相连的最小权重的节点，也就是 “最临近的” 节点，然后比较 起点到第二临近的节点的权重 与 最临近节点的下一个最临近节点的累计权重和 从而决定下一步该如何行走。可以想象，算法记录的累计权重和 如同地理的 “等高线” 一样，在图上以 “波” 的形式传播，直到到达目的地节点。
最短路径算法有两个常用的变种：A （可以念作 A Star）algorithm和 Yen’s K-Shortest Paths。A algorithm 通过提供的额外信息，优化算法下一步探索的方向。Yen’s K-Shortest Paths 不但给出最短路径结果，同时给出了最好的 K 条路径。
所有节点对最短路径（All Pairs Shortest Path）也是一个常用的最短路径算法，计算所有节点对的最短路径。相比较一个一个调用单个的最短路径算法，All Pairs Shortest Path 算法会更快。算法并行计算多个节点的信息，并且这些信息在计算中可以被重用。
本文不打算再深入了，下图是从A节点开始的计算过程，看懂这张图，你就明白了。
All Pairs Shortest Path 算法通常用于，当最短路径受限或者变成了非最优时，如何寻找替代线路。其实算法非常常用：
最小生成树
最小生成树（Minimum Spanning Tree）算法从一个给定的节点开始，查找其所有可到达的节点，以及将节点与最小可能权重连接在一起，行成的一组关系。它以最小的权重从访问过的节点遍历到下一个未访问的节点，避免了循环。
最常用的最小生成树算法来自于 1957 年的 Prim 算法。Prim 算法与Dijkstra 的最短路径类似，所不同的是， Prim 算法每次寻找最小权重访问到下一个节点，而不是累计权重和。并且，Prim 算法允许边的权重为负。
上图是最小生成树算法的步骤分解，算法最终用最小的权重将图进行了遍历，并且在遍历的过程中，不产生环。
算法可以用于优化连接系统（如水管和电路设计）的路径。它还用于近似一些计算时间未知的问题，如旅行商问题。虽然该算法不一定总能找到绝对最优解，但它使得复杂度极高和计算密集度极大的分析变得更加可能。例如：
随机游走
随机游走（Random Walk）算法从图上获得一条随机的路径。随机游走算法从一个节点开始，随机沿着一条边正向或者反向寻找到它的邻居，以此类推，直到达到设置的路径长度。这个过程有点像是一个醉汉在城市闲逛，他可能知道自己大致要去哪儿，但是路径可能极其“迂回”，毕竟，他也无法控制自己~
随机游走算法一般用于随机生成一组相关的节点数据，作为后续数据处理或者其他算法使用。例如：
中心性算法
中心性算法（Centrality Algorithms）用于识别图中特定节点的角色及其对网络的影响。中心性算法能够帮助我们识别最重要的节点，帮助我们了解组动态，例如可信度、可访问性、事物传播的速度以及组与组之间的连接。尽管这些算法中有许多是为社会网络分析而发明的，但它们已经在许多行业和领域中得到了应用。
下图罗列了我们所有需要了解的中心性算法指标。
Degree Centrality
Degree Centrality （度中心性，以度作为标准的中心性指标）可能是整篇博文最简单的 “算法” 了。Degree 统计了一个节点直接相连的边的数量，包括出度和入度。Degree 可以简单理解为一个节点的访问机会的大小。例如，在一个社交网络中，一个拥有更多 degree 的人（节点）更容易与人发生直接接触，也更容易获得流感。
一个网络的平均度（average degree），是边的数量除以节点的数量。当然，平均度很容易被一些具有极大度的节点 “带跑偏” （skewed）。所以，度的分布（degree distribution）可能是表征网络特征的更好指标。
如果你希望通过出度入度来评价节点的中心性，就可以使用 degree centrality。度中心性在关注直接连通时具有很好的效果。应用场景例如，区分在线拍卖的合法用户和欺诈者，欺诈者由于尝尝人为太高拍卖价格，拥有更高的加权中心性（weighted centrality）。
Closeness Centrality
Closeness Centrality（紧密性中心性）是一种检测能够通过子图有效传播信息的节点的方法。紧密性中心性计量一个节点到所有其他节点的紧密性（距离的倒数），一个拥有高紧密性中心性的节点拥有着到所有其他节点的距离最小值。
对于一个节点来说，紧密性中心性是节点到所有其他节点的最小距离和的倒数：
其中 u 是我们要计算紧密性中心性的节点，n 是网络中总的节点数，d(u,v) 代表节点 u 与节点 v 的最短路径距离。更常用的公式是归一化之后的中心性，即计算节点到其他节点的平均距离的倒数，你知道如何修改上面的公式吗？对了，将分子的 1 变成 n-1 即可。
理解公式我们就会发现，如果图是一个非连通图，那么我们将无法计算紧密性中心性。那么针对非连通图，调和中心性（Harmonic Centrality）被提了出来（当然它也有归一化的版本，你猜这次n-1应该加在哪里？）：
Wasserman and Faust 提出过另一种计算紧密性中心性的公式，专门用于包含多个子图并且子图间不相连接的非连通图：
其中，N 是图中总的节点数量，n 是一个部件（component）中的节点数量。
当我们希望关注网络中传播信息最快的节点，我们就可以使用紧密性中心性。
Betweenness Centrality
中介中心性（Betweenness Centrality）是一种检测节点对图中信息或资源流的影响程度的方法。它通常用于寻找连接图的两个部分的桥梁节点。因为很多时候，一个系统最重要的 “齿轮” 不是那些状态最好的，而是一些看似不起眼的 “媒介”，它们掌握着资源或者信息的流动性。
中间中心性算法首先计算连接图中每对节点之间的最短（最小权重和）路径。每个节点都会根据这些通过节点的最短路径的数量得到一个分数。节点所在的路径越短，其得分越高。计算公式：
其中，p 是节点 s 与 t 之间最短路径的数量，p(u) 是其中经过节点 u 的数量。下图给出了对于节点 D 的计算过程：
联系客服
