图论应用 | Python进行图计算和图论理论及其应用

放假一直懒得动笔，加上学生们放假，新技术都在不断学习中，还不是很成熟，有些知识越学越感觉不够了解。主要还是贪玩了，今天写一篇，是因为看到国外一篇非常不错的简单介绍了Graph Theory的文章，我从2004年开始关注SNA，社会网路分析技术，当然理解图理论也有助于理解现在人工智能的深度学习框架。

有必要给同学们再次梳理一下图的理论。

“Grahp图有一种揭示关系的魔力。节点和关系的概况揭示了图形呈现的整个情况 - 一个繁荣时代的关系社会的生活图景。关系告诉大脑，可以唤醒您的想象力，也更有说服力。“

- 亨利D.哈伯德

可视化是简化和解释数据中底层模式的有效方法。每当我们处理新数据集时，都期望通过可视化来探索它和洞察数据内在的模式、趋势和相关性。基于图的关系这种方法效果很好。当我们看到很多人使用大数据的实时可视化，都可以让我们感知这个社会，并与世界分享数据的一些“秘密”！

图形本身天生就是具有可视化技术特征。非常有用，可帮助决策者快速做出更好的数据驱动决策。但要详细了解图的概念，我们必须首先理解它的理论基础 - 图论。

在本文中，我们将学习图和图形理论的概念。我们还将解释图论的基本原理和基本属性，以及不同类型的图形。

我们将通过使用Python应用Graph Theory的概念来研究一个案例研究特定的解决航空业中航班和航线的图可视化常见的问题。

目录

1. 图表简介

2. 为什么图表？

3. 图论的起源：柯尼斯堡的七座桥

4. 图的基本原理

5. 与图形相关的基本属性和术语

6. 图的类型

7. 继续解决柯尼斯堡的七座桥问题

8. 树木简介

9. 图遍历

10. 实施图论理论解决航空挑战

图表简介

考虑下面的情节：

这是一个很直观的可视化表述特定商店销售份额。但这不是图表grahp，而是图表charts。可能想知道为什么这是图表charts而不是图graph？

一般来讲，图表charts代表一个函数的图形。通过扩展上面的例子来解释这一点。

在特定商品的总单位中，15.1％来自商店A，15.4％来自商店B，依此类推。我们可以用表来表示它：

对应每个商店是他们对整体销售的贡献（％）。在图中，我们将商店A的贡献率为15.1％，商店B的贡献率为15.4％，依此类推。最后，我们使用饼图将其可视化。但那么这张图表和图之间有什么区别？

要回答这个问题，请考虑以下所示的视觉效果

上述视觉中的点代表一种权力的游戏，而连接这些点的线代表它们之间的联系。Jon Snow与多个角色有联系，Tyrion，Cersei，Jamie等也是如此。这就是图graph的样子。单个点可能与多个点连接，甚至可能与单个点连接。通常，图是顶点（节点）和边的组合。在上面的视觉可视化中，所有字符都是顶点，它们之间的连接（关系）是边。

我们现在知道图是什么，但为什么我们首先需要图表？

 为什么图表？

假设您预订了优步出租车。对优步运作至关重要的最重要的事情之一是它能够以有效的方式将驾驶员与司机相匹配。考虑您可以匹配的6种可能的路线优化。那么，优步如何分配给你？我们可以利用图表来描述和理解分配行程的过程如何：

你可以解释，打车人可以选择或搭配6种可能的出租行程方案（乘坐1，乘坐2，......乘坐6）。以图graph形式表示这一点使得更容易可视化并最终实现我们的目标，即匹配最接近用户。上图中的数字表示打车者与他/她相应行车之间的距离（以千米为单位）。我们（当然还有优步）可以清楚地看到Ride 3是最接近的选择。

注意：为简单起见，我们只采用距离度量来决定将哪个出行分配给出租车。但在真实生活中的情况下，可能有多个指标来计算该乘坐的分配决定，例如考虑为不同的路线，时间的消耗，驾驶人是空闲的等双方之间的匹配和意愿和信用等级等。

同样，像类似物流配送地能够在线外卖配送平台可以选择从相应餐厅接收订单并将其交付给我们的外卖送货。这只是图的众多用例之一，通过它我们可以解决许多挑战。图形和图论使可视化更容易，更易于理解。

为了详细了解图的概念，我们必须首先理解图论。

图论的起源：柯尼斯堡的七座桥

图论的起源，以便直观地理解图。它的起源背后有一个有趣的故事，图论和可视化目标是使用绘图和可视化使其更具吸引力。

这一切都始于柯尼斯堡的七桥问题。Königsberg的桥梁面临的挑战（或只是一个脑筋急转弯），只能穿过所有七座桥梁一次穿过城市。让我们首先想象它，以便清楚地了解问题：

试一试，看看你是否可以通过这种克制来穿越城市。在尝试解决上述问题时，你必须记住两件事（或者我应该说谜语？）：

• 你只能走桥梁抵达另一个城市

• 每个桥梁不得超过一次（只能走一次）

您可以尝试任意数量的行走组合，但仍然是一个不可能的挑战。只有一次穿越每座桥，人们无法穿过城市。欧拉深入研究了这个难题，想出了为什么这是一项不可能完成的任务。让我们分析他是如何做到的：

上图中有四个不同的位置：两个岛屿（B和D），两个大陆（A和C）和七个桥梁。让我们先分别看看每块土地，并尝试找到模式（如果有的话）：

从上面的图我们得出的一个推论：每个陆地与奇数个桥连接。如果您只希望每个桥跨过一次，那么只有当它连接到偶数桥时才可以进入和离开。换句话说，我们可以概括地说，如果有偶数个桥梁，就有可能离开陆地，而用奇数不可能这样做。

让我们尝试为当前问题添加一个桥接器，看看它是否可以解决这个问题

现在我们有2个连接有偶数桥的连接，2个连接有奇数个连接的连接。让我们在添加新桥后绘制一条新路线

我们得出结论，增加一个单桥解决了这个问题！您可能想知道桥梁的数量是否在解决此问题中起了重要作用？它应该一直都是吗？情况并非总是如此。欧拉解释说，随着桥梁的数量，具有奇数个连接桥梁的土地数量也很重要。欧拉将这个问题从陆地和桥梁转换为图形，将土地表示为顶点，将桥梁表示为边缘

这时候通过简单的可视化，事情变得简单明了。进一步深入研究这个问题之前，让我们先了解一下图的基本原理和基本属性。

 图的基本原理

在处理图形时，我们应该记住许多关键点和关键词。在本节中，我们将详细讨论所有这些关键字。

• 顶点：这是多条线相交的点。它也被称为  节点。顶点通常用字母表示，如上所示

  
  

• 边缘：它是连接两个顶点的线

  
  

• 图：如上一节所述，图是顶点（节点）和边的组合。G =（V，E）其中V表示所有顶点的集合，E表示图形的所有边缘的集合。
  

• 顶点度数：顶点的度数是连接到它的边数。在下面的例子中，顶点A的度，deg（A）=顶点B的3Degree，deg（B）= 2

  
  

• 平行边：如果两个顶点通过多个边连接，则这些边称为平行边

  
  

• 多图：这些是具有平行边的图

  
  

这些是处理图时必须牢记的一些基础知识。现在了解图的基本属性。

 

与图相关的基本属性和术语

到目前为止，我们已经看到了图的样子，它是不同的组件。现在，我们将把重点转向与图形相关的一些基本属性和术语。我们将使用下面给出的图（称为G）并使用相同的术语来理解每个术语：

花点时间考虑以下问题的可能解决方案：

1. 距图其他顶点的顶点有多远？

2. 顶点和所有其他顶点之间的最大距离是多少？

3. 是否有任何顶点最接近所有其他顶点？如果是这样，最短的距离是多少？

4. 图的中心点是什么？

尝试使用基本图形术语回答所有这些问题：

• 两个顶点之间的距离：它是两个顶点之间最短路径中的边数。让我们尝试计算顶点A和D之间的距离：A和D 
  之间的可能路径是：
  AB - > BC - > CD 
  AD 
  AB - > BD 
  在这三条路径中，AD是最短的，只有一条边。因此，A和D之间的距离是1. 
  类似地，我们可以计算每对顶点之间的距离。所以，这回答了我们确定任何一对顶点之间距离的第一个问题。

  
  

• 顶点的偏心：它是顶点到所有其他顶点之间距离的最大值。要计算任何顶点的偏心率，我们必须知道该顶点与所有其他顶点之间的距离。让我们计算顶点A的偏心率。因此，距离是：
  A和B 
  之间的距离- 1 A和C 
  之间的距离- A A和D之间的距离 - 1 
  所有这些距离的最大值是顶点的偏心率。
  A的偏心率，e（A）= 2 
  当顶点的偏心率高时，意味着有一些顶点远离该顶点。这回答了我们的第二个问题，我们的目标是计算顶点到所有其他顶点之间的距离的最大值。

  
  

• 连通图的半径：图的所有顶点的最小偏心率称为该图的半径。我们首先要计算每个顶点的偏心率。尝试自己计算偏心率，如果发现计算有任何困难，请随时在评论部分询问。所有顶点的偏心率为：
  e（A）= 2 
  e（B）= 1 
  e（C） = 2 
  e（D）= 1 
  所有顶点的偏心率的最小值是该图的半径。在我们的例子中，最小偏心率是1，因此图的半径是：r（G）= 1 
  它告诉我们最接近所有其他顶点的顶点的距离。

• 连接图的直径：图的半径是所有顶点的偏心率的最小值，类似地，图的直径是所有顶点的偏心率的最大值。在我们的例子中，图的直径是：d（G）= 2

• 中部的曲线图的点：顶点的量，偏心率是等于该图的半径被称为该图的中心点。图也可以有多个中心点。在例子中，图的半径是1，偏心率等于1的顶点是B和D.因此'B'和'D'是图G的中心点。

这回答了我们确定中心点的最后一个问题。图，考虑机场连接图的示例。因此，与大多数其他机场相连的机场可以被视为中央机场。

这些是与图形相关的一些术语。接下来我们将讨论不同类型的图形。

图的类型

有各种类型的图。我们将讨论一些最常用的。

• 空图：这些是不包含任何边的图。

  
  顶点之间没有连接。

• 非定向图：这些是具有边的图，但这些边没有任何特定的方向

  
  

• 有向图：当图的边具有特定方向时，它们被称为有向图。

  
  考虑Facebook和Twitter连接的例子。当您将某人添加到Facebook上的朋友列表时，您也将被添加到他们的朋友列表中。这是双向关系，连接图将是非定向关系。如果您在Twitter上关注某个人，那么该人可能不会关注您。这是一个有向图。

• 连通图：当没有无法到达的顶点时，即每对顶点之间存在一条路径，这种图形称为连通图形

  
  

• 断开连接的图形：这些是具有无法到达的顶点的图形，即每对顶点之间不存在路径。

• 如果连接了图形，则始终存在从每个顶点到该图形的所有其他顶点的路径。如果图形断开连接，则始终至少有一个顶点不会与图形的所有其他顶点建立连接。这可以帮助航空公司决定是否所有机场都已连接。他们可以看到连接，如果有任何未连接的机场，可以引入新航班以改善现有情况。

• 正则图：当图中的所有顶点具有相同的度数时，这些图称为k-正则图（其中k是任何顶点的度数）。考虑下面显示的两个图：
  

• 对于Graph-1，每个顶点的度数为2，因此图-1是常规图。图-2不是规则图，因为每个顶点的度数不相同（A和D度是3，而B和D度是2）。

现在我们已经了解了不同类型的图，它们的组件以及一些与图相关的基本术语，让我们回到我们试图解决的问题，即柯尼斯堡的七桥问题。我们将更详细地探讨欧拉如何接近并解释他的推理。

 柯尼斯堡七桥的问题

我们之前看到Euler使用图形转换了这个问题

这里，A，B，C和D代表陆地，连接它们的线是桥。我们可以计算每个顶点的程度。

deg（B）= 5

deg（A）= deg（C）= deg（D）= 3

欧拉表明，使用每个边（桥）只走一次图（城市）的可能性，严格依赖于顶点（陆地）的程度。并且这样的路径仅包含图形的每个边缘，称为欧拉路径。

你能算出欧拉的问题路径吗？咱们试试吧

这就是使用图形和欧拉的路径来解决经典的柯林斯堡七桥问题。这基本上是图论的起源。感谢Leonhard Euler！

 

树木简介

树是表示图形的最有效和最有效的方法之一。了解二叉搜索树是什么，它们如何工作，以及它们如何使可视化更易于解释。但在此之前，花点时间了解树在这种情况下究竟是什么。

树是甚至不包含单个循环的图：

在上面的例子中，第一个图没有循环（也就是树），而第二个图有一个循环（ABECA，因此它不是树）。

树的元素称为节点。（A，B，C，D和E）是上述树中的节点。树的第一个节点（或最顶层节点）称为根节点（树根），而最后一个节点（上例中的节点C，D和E）称为叶节点。所有剩余的节点都称为子节点（在我们的例子中是节点B）。

现在是时候进入图论的一个最重要的主题，即图遍历。

 图遍历

假设我们想要在图中标识特定节点的位置。可以用什么方法来识别图的节点？怎么开始？应该是什么起点？一旦我们知道起点，如何进一步前进？我将通过解释Graph Traversal的概念来尝试回答所有这些问题。

图遍历是指以明确定义的顺序访问图的每个顶点和边缘一次。因为遍历的目的是仅访问每个顶点一次，所以我们保持覆盖顶点的轨迹，这样我们就不会覆盖相同的顶点两次。图遍历有各种方法，我们将讨论一些着名的方法：

• 广度优先搜索（BFS）

我们从源节点（根节点）开始并逐层遍历图。广度优先搜索的步骤是：

• 首先水平移动并访问当前图层的所有节点。

• 移至下一层并重复上述步骤。

让我用可视化来解释它：

因此，在广度优先搜索中，我们从源节点（在我们的例子中是A）开始，然后向下移动到第一层，即第1层。我们通过水平移动（B - > C）覆盖该层中的所有节点。然后我们转到下一层，即第2层并重复相同的步骤（我们从D - > E - > F移动）。我们继续此步骤，直到覆盖所有图层和顶点。

这种方法的主要优点是我们总能找到达到目标的最短路径。这适用于小图和树，但对于更复杂和更大的图，它的性能非常慢，并且还需要消耗大量内存。我们将研究另一种遍历方法，与BFS相比，它占用更少的内存空间。

• 深度优先搜索（DFS）

我们先来看看这种方法涉及的步骤：

• 我们首先选择源节点并存储其所有相邻节点。

• 然后，我们从存储的节点中获取节点并存储其所有相邻节点。

• 重复此过程，直到没有节点可用。
  
  

深度优先搜索以上示例的顺序为：

A - > B - > D - > E - > C - > F.

一旦路径被完全探索，它就可以从内存中删除，因此DFS只需要存储根节点，根节点的所有子节点以及它当前的位置。因此，它克服了BFS的内存问题。

• 二叉搜索树（BST）

在该方法中，树的所有节点按排序顺序排列。让我们看一下二进制搜索树的示例：

如前所述，上述树中的所有节点都是根据条件排列的。假设我们想要访问值为45的节点。如果我们要遵循BFS或DFS，我们需要大量的计算时间才能达到它。现在让我们看看二进制搜索树如何帮助我们使用最少的步骤访问所需的节点。使用二进制搜索树到达值为45的节点的步骤：

• 我们从根节点开始，即50。

• 现在45小于50（45 <50），所以我们移动到根节点的左边。

• 然后我们比较这些值。事实证明45大于40（45> 40），所以我们移动到该节点的右侧。

• 这里我们处于值为45的节点。

这种方法非常快，并且内存也非常少。图论的大多数概念都已被涵盖。接下来，我们将尝试实现这些概念，以使用Python解决实际问题。

 用Python实现图论解决航空挑战

我们开始使用Python中的数据！在这个数据集中，我们记录了来自美国的700多万个航班。提供了以下变量：

• 起源和目的地

• 预定的抵达和离开时间

• 实际到达和离开时间

• 旅程日期

• 源和目标之间的距离

• 航班的总播放时间

这是一个巨大的数据集，我从这篇文章中只拿了一个样本。我们的想法是让您了解使用此样本数据集的概念，然后您可以将它们应用于整个数据集。下载将用于案例研究的数据集。

https://drive.google.com/file/d/1S5c2z89SdzxSVeflWuwVT9EWHXB7Iv8Y/view

我们将首先导入常用的库，并读取以.csv格式提供的数据集：

import pandas as pd
import numpy as np
data = pd.read_csv（'data.csv'）

让我们看一下使用head（）函数的数据集的前几行：

data.head（）

这里，CRSDepTime，CRSArrTime，DepTime和ArrTime分别代表预定的出发时间，预定的到达时间，实际出发时间和实际到达时间。出发地和目的地的旅程的起点和终点。

从一个机场到另一个机场通常可以有多条路径，目的是找到所有机场之间最短的路径。我们可以通过两种方式将路径定义为最短路径：

• 按飞行距离

• 乘飞机时间

我们可以使用迄今为止学到的图的概念来解决这些问题。

答案是识别顶点和边缘！我们可以通过将所有机场表示为顶点以及它们之间的路径作为边来将问题转换为图形。

我们将使用NetworkX来创建和可视化图形。NetworkX是一个Python包，用于创建，操作和研究复杂网络的结构，动态和功能。您可以参阅NetworkX的文档。

安装NetworkX后，我们将使用数据集为图形创建边和顶点：

import networkx as nx
df = nx.from_pandas_edgelist（data，source ='Origin'，target ='Dest'，edge_attr = True）

它将自动存储顶点和边。快速浏览一下我们创建的图形的边和顶点：

df.nodes（）

df.edges（）

使用networkx的matplotlib和draw_networkx（）函数绘制和可视化图形  。

import matplotlib.pyplot as plt
％matplotlib inline
plt.figure（figsize =（12,8））nx.draw_networkx（df，with_labels = True）

上述可视化代表了不同的飞行路线。假设乘客想要从AMA到PBI采取最短路线。图论k可以揭示这一点！

让我们尝试根据机场AMA和PBI之间的通话时间来计算最短路径。我们将使用Dijkstra的最短路径算法。该算法找到从源顶点到给定图的所有顶点的最短路径。让我简要介绍一下该算法遵循的步骤：

1. 创建一个sptSet（最短路径树集），它跟踪最短路径树中包含的顶点，即计算并最终确定与源顶点的最小距离。最初，此设置为空。

2. 为输入图中的所有顶点指定距离值。我们为源顶点指定值0，为所有剩余顶点指定INFINITE值。

3. 直到sptSet不包含所有顶点，我们遵循以下子步骤：

• 选择一个不在sptSet中并且最接近源顶点的顶点

• 在sptSet中包含该顶点

• 更新所有相邻顶点的距离

让我们举一个例子来更好地理解这个算法：

这里的源顶点是A.数字表示顶点之间的距离。最初，sptSet为空，因此我们将为所有顶点指定距离。距离是：

{0，INF，INF，INF，INF，INF}，其中INF代表INFINITE。

现在，我们将选择具有最小距离的顶点，即A，它将包含在sptSet中。所以，新的sptSet是{A}。下一步是选择一个不在sptSet中并且最接近源顶点的顶点。在我们的例子中，这是B，距离值为2.所以这将被添加到sptSet。

sptSet = {A，B}

现在我们将更新与顶点B相邻的顶点的距离：

 

顶点F的距离值变为6.我们将再次选择具有最小距离值的顶点，该距离值尚未包括在SPT中（距离值为4的C）。

sptSet = {A，B，C}

我们将遵循类似的步骤，直到sptSet中包含所有顶点。让我们实现这个算法，并尝试计算机场之间的最短距离。我们将使用networkx 的  dijkstra_path（）函数来执行此操作：

shortest_path_distance = nx.dijkstra_path（df，source ='AMA'，target ='PBI'，weight ='Distance'）Shortest_path_distance

这是两个机场之间根据它们之间的距离尽可能短的路径。我们还可以通过改变超参数权重='AirTime'来计算基于通话时间的最短路径：

shortest_path_airtime = nx.dijkstra_path（df，source ='AMA'，target ='PBI'，weight ='AirTime'）shortest_path_airtime

这是基于通话时间的最短路径。直观且易于理解，这完全是关于图论的！

 

总结

这只是图论的众多应用之一。我们可以将它应用于几乎任何类型的问题，并获得解决方案和可视化。图论的一些应用是：

• 找到发布帖子的最佳途径（传播路径可视化）

• 通信网络基站。例如，可以使用有向图来表示网站的链接结构。

• 使用人们的社交连接图，确定一个人的社交行为

• 航空公司案例研究中讨论的旅行计划（优化问题）

当然，图的可视化有很多软件工具：Ucinet（Netddraw）、Gephi、Cytoscape、Yed、NetworkX、iGraph

另外很多技术可以实现：Echarts、D3js、Zoomcharts等JS技术。

俺用的比较多的是Python和Cytoscape，并且可以通过Python计算图的各种测量，实时抓取数据，计算图和重构数据结构，在Cytoscape中展现和可视化。当然最酷炫的技术是JS技术，配合WebGL技术和地理信息可以酷炫大屏实时展现关系和流量！

可视化特朗普的性格分析与世界领导人的性格特征分析（案例）