“绘制拥堵图：利用图论进行交通分析”

Traffic Analysis Using Graph Theory Drawing Congestion Maps

学习如何利用图论找到城市基础设施中的潜在关键点

图论在社交网络、分子生物学或地理空间数据等实际问题中有很多应用。今天，我将介绍最后一个应用，即分析城市道路布局以预测关键街道、交叉口以及基础设施变化对其的影响。但首先，让我们从基础知识开始。

图和它们的中心性指标

图由顶点和它们的边构成：

边表示节点之间的连接关系。如果边没有方向，我们称之为无向图。无向图的一个实际例子可以是化学分子，其中顶点是原子，边表示化学键。

然而，有时我们需要了解边是从 u 到 v，从 v 到 u，还是双向的。例如，如果马克喜欢爱丽丝，并不意味着这种喜欢是相互的（ ☹ ）。在这种情况下，我们可以将边定义为有序元组，而不是无序元组。

• “复杂理论在知识边界上的50年之旅”
• 谷歌测试提供生活建议的AI助手
• 大型语言模型：对真实世界CX应用的全面分析

利用图的结构，我们可以定义中心性指标。它是一种用于回答以下问题的度量标准：

这个顶点/边在图中有多重要？

有很多方法可以回答这个问题。

评估图组件重要性的不同方法

根据任务的不同，我们可以从不同的角度评估中心性。其中最常见的度量标准有：度、紧密度和介数。我们将使用扎卡里的空手道俱乐部图来讨论它们[更多信息]。它展示了不同空手道俱乐部成员之间的联系。你可以在下面找到用于生成图片的代码。

度中心性

最基本的中心性指标。它仅适用于顶点，且等于顶点的度（即其相邻顶点的数量）。以人际关系图为例，对于人与人之间的友谊关系，这个指标将回答以下问题

这个人有多受欢迎？

图中的路径

对于接下来的两个中心性指标，我们需要介绍一些图论知识的概念。所有这些概念都非常直观，从边的权重开始。我们可以给边添加权重，以标记它们之间的差异。例如，在交通图中，这可以是道路长度。

在图中，我们可以定义路径，即我们需要遍历的顶点列表，以从A到B。路径中的连续顶点是相邻的，第一个顶点是A，最后一个是B。路径距离是沿路径的边的权重之和。A和B之间的最短路径是距离最小的路径。

紧密中心性

有了这些新的知识，我们可以回到我们的指标上。下一个指标是紧密中心性，它告诉我们一个节点与图中其他节点的接近程度。对于特定的顶点，它被定义为到图中所有其他顶点的最短路径的平均值的倒数。因此，较短的平均路径会导致更高的紧密中心性。

介数中心性

介数中心性给我们提供了有关图中哪些节点对通过它的流量至关重要的信息。想象一个具有广阔道路网络的城市，其中每个路口都是一个节点。其中一些在日常通勤中起到关键连接器的作用，而其他一些可能是近乎封闭的死胡同，对交通流量几乎没有影响。前者具有较高的介数中心性得分，该得分计算为通过交叉路口的最短路径的比例。

城市规划与图

现在，我们具备了描述和分析图的工具，我们可以将城市规划提取为图形形式。为此，我们可以使用Open Street Maps（OSM）将其作为NX图导入Python，使用osmnx库。我们将从一个较小的示例开始，讨论我们需要应用的其他流程，以提高工作的时间和效率。

Grzegórzki是克拉科夫市的十八个行政区之一，拥有两个复杂的环形交叉口-莫吉尔斯基和格热戈热茨基，以及许多路口。因此，我们能够看到大部分潜在的数据工程问题。

Grzegórzki的行政边界。[©Google]

让我们从OSM存储库中导入数据到Python图中，并绘制结果：

这个图有问题-你能发现是什么问题吗？

我们对道路的单个部分获得了多个边，导致图形中几乎有3,000个“交叉口”。这并不能提供适当的表示（我们不能在道路中间掉头，每个节点都会导致计算速度变慢）。为了解决这个问题，我们将通过删除两个交叉口之间道路上的所有节点来执行图形拓扑简化。在OSMnx中，我们有一个名为ox.simplify_graph()的函数来完成这个操作。

还有一个问题 —— 如您所见，大多数道路有两个边，分别对应两个方向。由于这个原因，每个交叉口都有多个节点，这是不希望的行为。想象一下，我们在一个交叉口，我们要左转，但没有专门的左转道（或者已经满了）。只要我们不能完成转弯，其他车辆就会被阻塞。在我们当前的图中，这不是真实情况。左转由两个独立的节点组成，一个用于左转，另一个用于穿过相反的车道。这会导致它们是两个独立的操作，但实际上它们并不是。

这就是为什么我们要合并交叉口，将靠近彼此的多个节点合并为一个节点。我们将选择足够大的合并半径，将交叉口的多个部分合并为一个，但另一方面保持环形交叉口作为多个节点结构，因为它们可能只被部分阻塞。为了做到这一点，我们将使用osmnx函数ox.consolidate_intersections()。

经过这些操作，我们几乎准备好进行分析了。最后一个注意事项是克拉科夫市的边界 —— 由于许多人从附近的城镇出行，图形分析只包括图中的数据，我们需要包含这些区域。我将在下一章节中介绍不这样做的影响。以下是我们的图形：

您可以在此Jupyter笔记本中找到用于生成此地图的源代码，以及下一章节中使用的所有图形。

道路布局的中间度中心性

在这个案例研究中，我们只关注中间度中心性测量来估计道路交通情况。将来，这可能会扩展到图论中的其他技术，包括GNN的使用（图神经网络）。

我们将从计算道路布局表示中所有节点和边的中间度中心性开始。为此，我们将使用NetworkX库。

由于图上有大量的道路，很难看出哪些组件最有可能对交通产生重要影响。让我们来看看图中的中心性测量分布。

我们可以使用这些分布来筛选出较不重要的交叉口和街道。我们将选择每个分布的前2%，阈值如下：

• 节点为0.047
• 边为0.021

我们可以看到根据介数最重要的道路段包括：

• A4高速公路和S7，它们是克拉科夫的环城公路（请注意，克拉科夫没有环城公路的北部部分）
• 第二环路的西部部分及其与A4的连接
• 第三环路的北部部分（代替缺失的北部环城公路）
• Nowohucka街连接第二环路与城市的东北部分
• Wielicka路，从市中心通往东南部的高速公路

让我们将这些信息与Google地图上的克拉科夫实时交通地图进行比较：

我们可以看到我们的洞察结果与交通雷达的结果相吻合。其背后的机制非常简单——具有较高介数中心性的组件是在图中大多数最短路径上通勤的组件。如果驾车者选择最佳路径进行行驶，那么交通量最大的街道和交叉口就是具有最高介数中心性的街道和交叉口。

让我们回到图形工程的最后一部分——扩展图形边界。我们可以检查一下如果我们只考虑城市边界进行分析会发生什么：

A4高速公路，作为环城公路的重要组成部分之一，在整个图中具有最低的中心性测量值！这是因为A4位于城市的边缘，大部分交通来自外部，我们不能将该因素纳入介数中心性的计算中。

如何使用介数中心性分析布局变化对交通的影响

让我们来看一个不同的图形分析场景。假设我们想预测道路封闭（例如由于事故）对交通的影响。我们可以使用中心性测量来比较两个图形之间的差异，从而检查中心性的变化。

在这项研究中，我们将模拟A4–7高速公路段的车祸，这是一种常见情况。事故将导致该路段完全封闭。

我们将首先通过从图中删除A4–7段来创建一个新的道路网络，并重新计算中心性测量。

让我们来看看中心度分布：

我们可以看到它与原始布局仍然非常相似。为了检查中心度测量的变化，我们将计算剩余图，其中中心度测量是原始道路布局与事故后的差异。正值将表示事故后的更高中心度。在其中一个图中缺失的节点和交叉口（如A4-7）将不包含在剩余图中。以下是剩余量的测量分布：

同样，我们将过滤掉受影响的街道和节点的前2%。这次的阈值值为：

• 节点为0.018，
• 边为0.017。

我们可以看到，连接环城公路的分离部分与市中心的道路增加，其中第二环路位于城市的西侧，变化最大。

在道路网络上，图中心度分析无法做到的事情

在图分析中，有几件事情是无法考虑的。其中两个最重要的，我们在这个分析中可以看到的是：

• 图中心度分析假设节点之间的交通均匀分布。

这在大多数情况下是错误的，因为乡村和城市具有不同的人口密度。然而，还有其他因素可以减少这一影响，例如住在附近村庄的人群更倾向于选择开车通勤，而不是居住在市中心的人群。

• 图分析只考虑图中存在的事物。

这在提供的示例中比较难看出，特别是对于不熟悉克拉科夫的人来说。让我们看看扎科皮安卡。它是连接市中心和克拉科夫南部大部分自治市的主要交通干线，也是DK7（全国7号公路）的一部分，横跨整个国家。

如果我们将克拉科夫的DK7上的典型交通与我们的中心度测量进行比较，它们完全不同。平均介数中心度约为0.01，这是比前2%阈值小两倍的值。然而在现实中，它是最拥堵的区域之一。

总结

图论及其分析在多个场景中都有应用，如本研究中所呈现的交通分析。通过对图进行基本操作和度量，我们可以在比构建整个模拟模型更短的时间内获得有价值的洞察。

这整个分析可以使用几十行Python代码来完成，并且不限于一种道路布局。我们还可以很容易地切换到图论的其他分析工具。

就像所有事物一样，这种方法也有其缺点。主要的缺点是对均匀交通分布的假设和范围仅限于图结构。

本研究中使用的代码的Github存储库可以在此处找到。