九、使用图的美国国内航班数据分析

“在获得数据之前先进行理论分析是一个重大错误。”

– 福尔摩斯

在本章中，我们重点介绍一种称为图的基本计算机科学数据模型，以及在它们上常用的不同类型的算法。作为数据科学家或开发人员，熟悉图并迅速识别它们何时提供解决特定数据问题的正确解决方案非常重要。例如，图非常适合基于 GPS 的应用（例如 Google Maps），并考虑到各种参数（包括用户是开车，步行还是乘坐公共交通工具）找到从 A 点到 B 点的最佳路线，或者用户想要的是最短的路线，还是无论公路总距离如何都可以最大限度地利用高速公路的路线。这些参数中的一些也可以是实时参数，例如交通状况和天气。使用图的另一类重要应用是社交网络，例如 Facebook 或 Twitter，其中顶点表示个人，边表示关系，例如好友，关注。

我们将从对图和相关图算法的高级介绍开始本章。然后，我们将介绍networkx，这是一个 Python 库，可轻松加载，操纵和可视化图数据结构，并提供丰富的图算法集。我们将通过建立样本分析来继续讨论，该样本分析使用各种图算法分析美国的航班数据，其中机场用作顶点，航班用作边线。与往常一样，我们还将通过构建一个简单的仪表板 PixieApp 来对这些分析进行操作。我们将通过使用在第 8 章，“金融时间序列分析和预测”中学习到的时间序列技术构建历史模型来建立预测模型。

图简介

图的引入和相关的图论在 1736 年被列昂哈德·欧拉（Leonhard Euler）研究柯尼斯堡（Königsberg）七桥。

这座城市被普雷格尔河分开，普雷格尔河在某些时候形成了两个岛屿，并根据下图所示的布局建造了七座桥梁。问题是找到一种方法让人们一次又一次地跨过每座桥，然后回到起点。欧拉证明了这个问题没有解决方案，并且在此过程中诞生了图论。基本思想是将城市图转换为一个图，其中每个土绘图都是一个顶点，每个桥都是连接两个顶点（即土绘图）的边。然后将问题简化为找到一条路径，该路径是边缘和顶点的连续序列，仅包含每个桥一次。

下图显示了欧拉如何将柯尼斯堡七桥问题简化为图问题：

将柯尼斯堡七桥问题简化为图问题

使用更正式的定义，图是表示对象（称为顶点或节点）之间对象之间的成对关系（称为边缘）的数据结构。）。通常使用以下表示法表示图：G = (V, E)其中V是顶点集，而E是顶点集的边缘。

图主要有两大类：

有向图（称为有向图）：成对关系的顺序很重要，即，从顶点A到顶点B的边（AB）不同于从顶点B到顶点A的边缘（BA）。
无向图：成对关系的顺序无关紧要，即边（A-B）与边（B-A）相同。

下图显示了示例图的表示形式，即无向（边缘没有箭头）和有向（边缘有箭头）：

图的表示

主要有两种表示图的方式：

邻接矩阵：使用n维矩阵表示图（我们称其为A），其中n是图中的顶点数。使用 1 到n个整数对顶点进行索引。我们用A[i, j] = 1来表示顶点i和顶点j之间存在边，而A[i, j] = 0来表示顶点i和顶点j之间不存在边缘。在无向图的情况下，因为顺序无关紧要，所以我们总是有A[i, j] = A [j, i]。然而，在有序关系重要的有向图的情况下，A[i, j]可能与A[j, i]不同。以下示例显示了如何在有向和无向的邻接矩阵中表示样本图：

图的邻接矩阵表示（有向和无向）

重要的是要注意，邻接矩阵表示具有恒定的空间复杂度，即O(n²)，其中n是顶点数，但是的时间复杂度为O(1)，这是恒定时间，用于计算两个顶点之间是否存在边连接。当图密集（边缘很多）时，高空间复杂度可能还可以，但在图稀疏时可能会浪费空间，在这种情况下，我们可能更喜欢以下邻接表表示形式。

注意

注意：大 O 表示法通常用于代码分析，以通过随着输入大小的增加评估其行为来表示算法的性能。它用于评估运行时间（运行算法所需的指令数量）和空间需求（随着时间的推移需要多少存储空间）。
邻接表：对于每个顶点，我们维护一个边连接的所有顶点的列表。在无向图的情况下，每个边都被表示两次，每个端点代表一个边，对于顺序重要的有向图则不是这种情况。

下图显示了有向图和无向图的图的邻接表表示形式：

图的邻接表表示（有向和无向）

与邻接矩阵表示法相反，邻接列表表示法具有较小的空间复杂度，即O(m + n)，其中m是边的个数，n是顶点数。但是，与邻接矩阵的O(1)相比，时间复杂度增加到O(m)。由于这些原因，当图稀疏连接时（即没有很多边），最好使用邻接表表示。

正如前面的讨论所暗示的那样，要使用哪种图表示形式在很大程度上取决于图密度，还取决于我们计划使用的算法类型。在下一节中，我们将讨论最常用的图算法。

图算法

以下是最常用的图算法的列表：

搜索：在图的上下文中，搜索意味着找到两个顶点之间的路径。路径定义为边和顶点的连续序列。在图中搜索路径的动机可能是多种多样的。可能是您有兴趣根据一些预定义的距离标准（例如，边的最小数量（例如 GPS 路线图））找到最短路径，或者只是想知道两个顶点之间存在一条路径（对于例如，请确保网络中的每台计算机均可从其他任何计算机访问）。一种搜索路径的通用算法是从给定的顶点开始，发现与之相连的所有顶点，将发现的顶点标记为已探索（因此我们不会两次找到它们），并继续进行相同的探索每个发现的顶点，直到找到目标顶点，或者用尽顶点为止。该搜索算法有两种常用的风格：广度优先搜索和深度优先搜索，每种都有各自的用例，它们更适合于这些用例。这两种算法的区别在于我们找到未探索顶点的方式：
- 广度优先搜索（BFS）：首先探索与相邻的未探索节点。探索完相邻邻域后，开始探索层中每个节点的邻域，直到到达图的末尾。由于我们正在探索首先直接连接的所有顶点，因此该算法保证找到与找到的邻域数量相对应的最短路径。 BFS 的扩展是著名的 Dijkstra 最短路径算法，其中每个边都与非负权重相关联。在这种情况下，最短路径可能不是跳数最少的路径，而是使所有权重之和最小的路径。 Dijkstra 最短路径的一个示例应用是查找地图上两点之间的最短路径。
- 深度优先搜索（DFS）：对于每个直接相邻的顶点，请先尽可能深入地探索其相邻的邻居，然后在耗尽邻居时开始回溯。 DFS 的应用示例包括查找拓扑排序和有向图的强连接组件。作为参考，拓扑排序是顶点的线性排列，以使线性顶点中的每个顶点都遵循下一个顶点的边缘方向（也就是说，它不会向后移动）。有关更多信息，请参见这个页面。
下图说明了在 BFS 和 DFS 之间查找未探索的节点的区别：

在 BFS 和 DFS 中查找未探索的顶点的顺序
连通组件和强连通组件：图的连通组件是一组顶点，其中任意两个顶点之间都有路径。注意，该定义仅指定必须存在路径，这意味着只要存在路径，两个顶点之间就不必具有边。在有向图的情况下，由于附加的方向约束，连通组件被称为“强连通组件”，这不仅要求任何顶点 A 都应具有通往任何其他顶点 B 的路径，而且 B 也必须具有通往 A 的路径。

下图显示了牢固连通组件或有向图示例：

有向图的强连接组件
中心：顶点的中心度指示符指示顶点相对于图中其他顶点的重要性。这些中心指数有多个重要的应用。例如，在社交网络中确定最有影响力的人或通过最重要的页面对网络搜索进行排名等。

中心性有多个指标，但我们将重点关注本章稍后将使用的以下四个指标：
- 阶数：顶点的阶数是该顶点是端点之一的边的数量。对于有向图，是顶点是源或目标的边数，我们称入度是顶点为目标的边的数量，出度是顶点为源的边的数量。
- PageRank：这是 Google，Larry Page 和 Sergey Brin 的创始人开发的著名算法。 PageRank 用于通过对给定网站的重要性进行衡量来对搜索结果进行排名，其中包括计算从其他网站到该网站的链接数。它还会评估这些链接的质量（即网站链接到您的链接的可信度）。
- 紧密度：紧密度中心度与给定顶点和图中所有其他顶点之间的最短路径的平均长度成反比。直觉是顶点离所有其他节点越近，它就越重要。
  
  紧密度中心度可以使用以下简单方程式计算：
  
  （来源：https://en.wikipedia.org/wiki/Centrality#Closeness_centrality）
  
  其中d(y, x)是节点x和y之间的边缘长度。
- 最短路径之间的间隔：根据给定顶点是任意两个节点之间最短路径的一部分的次数进行度量。直觉是，顶点对最短路径的贡献越大，它就越重要。这里提供了最短路径之间的数学方程式：
  
  （来源：https://en.wikipedia.org/wiki/Centrality#Betweenness_centrality）
  
  其中σ[st]是从顶点s到顶点t的最短路径总数，σ[st](v)是通过v的σ[st]的子集。
  
  注意
注意：有关集中性的更多信息，请参见这里。

图和大数据

到目前为止，我们的图讨论集中于可以容纳在一台机器中的数据，但是当我们拥有非常庞大的具有数十亿个顶点和边的图而无法将整个数据加载到内存中时，会发生什么？一个自然的解决方案是将数据分布在多个节点的集群中，这些节点并行处理数据并合并单个结果以形成最终答案。幸运的是，有多个框架提供了这种图并行功能，并且它们几乎都包含了大多数常用的图算法的实现。流行的开源框架的示例有 Apache Spark GraphX 和 Apache Giraph。 Facebook 目前正在使用来分析其社交网络。

无需过多讨论，重要的是要知道这些框架都是从分布式计算的批量同步并行（BSP）模型，它使用机器之间的消息在整个集群中查找顶点。要记住的关键点是这些框架通常非常易于使用，例如，使用 Apache Spark GraphX 编写本章的分析本来就很容易。

在本节中，我们仅回顾了所有可用的图算法中的一小部分，并且深入探讨将超出本书的范围。自己实现这些算法将花费大量时间，但是幸运的是，有很多开源库提供了图算法的相当完整的实现，并且易于使用并将其集成到您的应用中。在本章的其余部分，我们将使用networkx开源 Python 库。

NetworkX 图库入门

在开始之前，如果尚未完成，则需要使用pip工具安装networkx库。在自己的单元格中执行以下代码：

!pip install networkx

注意

注意：与往常一样，不要忘记在安装完成后重新启动内核。

networkx提供的大多数算法都可以直接从主模块调用。因此，用户将只需要以下import语句：

import networkx as nx

创建图

首先，让我们回顾一下networkx和创建空图的构造器支持的不同类型的图：

Graph：无向图，只允许顶点之间有一个边。允许自环边。构造器示例：
```
G = nx.Graph()
```
Digraph：实现有向图的Graph的子类。构造器示例：
```
G = nx.DiGraph()
```
MultiGraph：无向图，允许顶点之间有多个边。构造器示例：
```
G = nx.MultiGraph()
```
MultiDiGraph：有向图，允许顶点之间有多个边。构造器示例：
```
G = nx.MultiDiGraph()
```

Graph类提供了许多用于添加和删除顶点和边的方法。这是可用方法的子集：

add_edge(u_of_edge, v_of_edge, **attr)：在顶点u和顶点v之间添加一条边，并带有与该边相关联的可选附加属性。如果图中尚未存在顶点u和v，则会自动创建它们。
remove_edge(u, v)：移除u和v之间的边缘。
add_node(self, node_for_adding, **attr)：使用可选的附加属性将节点添加到图。
remove_node(n)：删除由给定参数n标识的节点。
add_edges_from(ebunch_to_add, **attr)：批量添加具有可选附加属性的多个边。边必须以两元组(u,v)或三元组(u,v,d)的列表形式给出，其中d是包含边数据的字典。
add_nodes_from(self, nodes_for_adding, **attr)：使用可选附加属性批量添加多个节点。可以将节点提供为列表，字典，集合，数组等。

作为练习，我们从头开始构建一个一直用作示例的有向图：

使用 NetworkX 以编程方式创建的示例图

以下代码首先创建一个DiGraph()对象，然后使用add_nodes_from()方法在一次调用中添加所有节点，然后使用add_edge()和add_edges_from()的组合开始添加边线：

G = nx.DiGraph()
G.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
G.add_edge('A', 'B')
G.add_edge('B', 'B')
G.add_edges_from([('A', 'E'),('A', 'D'),('B', 'C'),('C', 'E'),('D', 'C')])

Files

09.md

Latest commit

History

09.md

File metadata and controls

九、使用图的美国国内航班数据分析

图简介

图的表示

注意

图算法

注意

图和大数据

NetworkX 图库入门

注意

创建图

注意

注意

可视化图

注意

第 1 部分——将美国国内航班数据加载到图中

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

图的中心

注意

注意

注意

注意

注意

注意

注意

注意

注意

第 2 部分——创建USFlightsAnalysis PixieApp

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

第 3 部分——向USFlightsAnalysis PixieApp 添加数据浏览

注意

注意

注意

注意

注意

注意

注意

注意

注意

第 4 部分——创建 ARIMA 模型来预测航班延误

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

注意

第 2 部分——创建`USFlightsAnalysis` PixieApp

第 3 部分——向`USFlightsAnalysis` PixieApp 添加数据浏览