添加一名作者
翻译：何中华
校对：丁南亚
本文长约6,300 字，建议阅读至少20 分钟。
本文从图的概念和历史开始，介绍一些必要的术语，然后介绍networkx库，以航班信息数据集为例，引导读者进行基本分析。
介绍
俗话说，眼见为实。但图表的意义远不止于此。以图表形式可视化数据可以提供见解，帮助您做出更好的数据驱动决策。
但要真正理解图是什么以及为什么使用它们，您需要理解一个称为图论的概念。理解这一点可以让我们成为更好的程序员。
如果您曾经试图理解这个概念，您可能会遇到很多公式和枯燥的理论。这就是我们撰写这篇博文的原因。我将首先解释这个概念，然后举一个例子，以便您可以理解它是如何工作的。这是一篇详细的文章，因为我们相信提供概念的准确解释比简洁的定义更受欢迎。
在本文中，我们将了解图表是什么、它们的用途以及它们的历史背景。它还介绍了一些图论概念并使用案例研究来加深理解。
你准备好了吗？开始吧。
目录
图及其应用图论的历史以及为什么我们使用重要的图论术语图论概念熟悉Python 中图数据分析的示例图及其应用
让我们看一个简单的图表来理解这个概念。如下所示：
假设该图表示城市内热门旅游景点的位置以及游客所走的路径。设V 为景点位置，E 为从一个位置到另一位置的路线。
V={v1, v2, v3, v4, v5}
E={（v1，v2），（v2，v5），（v5，v5），（v4，v5），（v4，v4）}
边（u，v）与边（v，u）相同。这些是无序对。
具体来说，图是一种用于研究对象和实体之间的成对关系的数学结构。它是离散数学的一个分支，在计算机科学、化学、语言学、运筹学、社会学等领域有着广泛的应用。
数据科学和分析领域也使用图表来建模各种结构和问题。数据科学家必须能够有效地解决问题。当数据以某种方式排列时，图可以提供解决问题的机制。
正式地，
图是一对集合。 G=(V, E)，其中V 是顶点集，E 是边集。 E 由V 的元素对（无序对）组成。有向图（DiGraph）也是一对集合。 D=(V, A)，其中V 是顶点集，A 是弧集。 A 由V 的元素对（有序对）组成。对于有向图，(u, v) 和(v, u) 之间存在差异。通常在这种情况下，边缘被称为弧线来传达方向的想法。
R 和Python 都有使用图论概念分析数据的包。在本文中，我们将简要介绍一些概念并使用Networkx Python 包分析数据集。
IPython.display 来自导入图像
图像（\'图像/网络.PNG\'）
图像（\'图像/usecase.PNG\'）
从上面的例子可以清楚地看出，图表广泛用于数据分析。让我们看一些用例场景。
您可以使用营销分析图表来识别社交网络上最有影响力的人。广告商和营销人员可以通过社交网络上最有影响力的人传达他们的信息来报价最高的营销价格。
银行交易图表可让您发现异常模式，有助于减少欺诈交易。在某些情况下，恐怖活动是通过分析银行网络的资金流动来发现的。
供应链地图有助于确定送货卡车的最佳路线并定位仓库和配送中心。
制药公司制药公司可以使用图论来优化其销售代表的出行路线。这有助于减少销售人员成本和差旅时间。
电信行业电信公司经常使用图表（Voronoi 图）来了解基站的数量和位置，以确保最大的覆盖范围。
图表的历史及其使用原因
图表的历史
如果您想了解更多有关图形想法如何形成的信息，请继续阅读。
该理论的起源可以追溯到柯尼斯堡的七桥问题（大约1730 年代）。询问在以下限制下是否可以穿越柯尼斯堡市的七座桥梁：
每座桥只经过一次（即不重复）。它从哪里开始和结束？ 短篇故事：欧拉于1736 年研究并解决了这个问题。他把这个问题简化为“一笔”问题。他的论文《柯尼斯堡七桥》成功解决了这个问题，并创建了数学的一个新分支：图论。
这相当于询问具有4 个节点和7 个边的多重图是否具有欧拉循环（欧拉循环是在同一顶点开始和结束的欧拉路径。欧拉路径是遍历每条边的路径）。详细条款仅一次）。这个问题引出了欧拉图的概念。柯尼斯堡七桥问题的答案是否定的，由欧拉首先解决。
译者注：在图论中，多重图（与简单图相对）是指图内出现多条边（也称为平行边）。这意味着两个顶点可以通过多条边连接。下图是多边形边，因此该图像是多图片的。
1840年，A.F莫比乌斯提出了完全图和二分图的概念，库拉托夫斯基通过一个有趣的谜题证明了它们是平面的。树（无环的连通图）的概念由Gustav Kirchhoff 于1845 年提出，他在计算电网和电路中的电流时使用了图论的思想。
1852 年，Thomas Guthrie 发现了著名的四色问题。然后，在1856 年，托马斯·P·柯克曼(Thomas P. Kirkman) 和威廉·R·汉密尔顿(William R. Hamilton) 通过研究多面体循环和仅到特定位置一次的行程，发明了一种称为汉密尔顿图的概念。 1913 年，H.Dudeney 解决了一个难题。四色问题被发明了，但肯尼思·阿佩尔和沃尔夫冈·哈肯花了一个世纪才解决它。这次被认为是图论的真正诞生。
卡利研究了一种特殊的微积分分析形式来研究树。这对理论化学有很多影响。这也导致了枚举图论的发明。不管怎样，“图”这个术语是由Sylvester 于1878 年引入的，他在“量子不变量”与代数图和分子图的协变量之间进行了类比。
1941年，拉姆齐研究了着色问题，并创建了图论的一个独立分支——极端图论。 1969年，海因里希用计算机解决了四色问题。对渐近图连通性的研究引发了随机图论。图论和拓扑的历史也密切相关，共享许多共同的概念和定理。
图像（\'images/Konigsberg.PNG\'，宽度=800）
为什么要使用图表？
以下几点将激发您在日常数据科学问题中使用图表。
图表提供了一种更好的方法来处理关系和交互等抽象概念。它还提供了一种直观的视觉方式来思考这些概念。图表自然而然地成为分析社会关系的基础。图数据库已成为常用的计算工具以及SQL 和NoSQL 数据库的替代品。图用于以DAG（有向无环图）的形式对分析工作流程进行建模。一些神经网络框架使用DAG 来模拟不同层的不同操作。图论用于研究和建模社交网络、欺诈模式、电力消耗模式、病毒式传播以及社交媒体的影响。社交网络分析（SNA）可能是图论在数据科学中最著名的应用。它用于聚类算法，尤其是K-means。系统动力学也使用图论，尤其是循环。路径优化是也使用图概念的优化问题的子集。从计算机科学的角度来看，图提高了计算效率。某些算法的Big O 复杂度对于以图形格式排列的数据（与表格数据相比）更好。所需条款
我们建议您在继续阅读本文之前先了解这些术语。
设顶点u 和v 为边(u, v) 的结束顶点。如果两条边具有相同的终端顶点，则它们是平行的。 (v, v) 形式的边是环。如果图没有平行边或环，则称为简单图。如果图没有边，则称为空图。即E为空。如果图没有顶点，则称为空图。即V和E为空。只有一个顶点的图是平凡图。具有公共顶点的边是相邻的。具有公共边的顶点是相邻的。顶点v的度记为d(v)，是指以v为结束顶点的边的条数。按照惯例，一个周期被计数两次，每个平行边贡献一次。孤立顶点是度数为1 的顶点。 d(1) 个顶点是分离的。如果图的边集包含所有顶点之间的所有可能的边，则图是完整的。图中的行走G=(V, E) 是指由图中的顶点和边组成的形状ViEiViEi 的有限交替序列。如果第一个和最后一个顶点不同，则步行是开放的。如果第一个顶点和最后一个顶点相同，则路径关闭。如果一条步行最多穿过边缘一次，那么它就是一条踪迹。如果一条踪迹最多穿过一个顶点一次，那么它就是一条路径（除了封闭的走道）。闭合路径是类似于电路的电路。图论概念
本节介绍一些概念来帮助您分析数据（排名不分先后）。请注意，还有许多其他概念，其深度超出了本文的范围。开始吧。
平均路径长度
所有可能节点对应的平均最短路径长度。它提供了图表“紧密度”的衡量标准，可用于了解网络中某些事物的流动速度。
广度优先搜索和深度优先搜索
广度优先搜索和深度优先搜索是在图中查找节点的两种不同算法。这些通常用于确定是否可以从特定节点到达特定节点。这也称为图遍历。
BFS 的目标是遍历图尽可能靠近根节点，而DFS 算法的目标是遍历图尽可能远离根节点。
中心性
用于分析网络的最广泛使用和最重要的概念工具之一。中心性旨在找到网络中最重要的节点。对“重要”可能有多种不同的理解，因此中心性指标也有多种。中心性标准本身可以分为很多类别。一些标准的特点是沿着边缘流动，而另一些标准则特点是步行结构。
一些最常用的标准包括：
度中心性- 中心性的第一个也是概念上最简单的定义。表示连接到节点的边的数量。对于有向图，我们可以获得2 度中心性的度量。流入和流出的中心性。 Closeness Centrality - 从一个节点到所有其他节点的最短路径的平均长度。介数中心性- 节点位于最短路径上的节点对的数量。这些中心性度量有很多变化，可以使用不同的算法来定义。总的来说，这个领域有很多定义和算法。
网络密度
图中边数的度量。实际的定义取决于图表的类型和提出的问题。对于完全无向图，密度为1，对于空图，密度为0。在某些情况下（当涉及循环时），图密度可能大于1。
图随机化
一些图表指标很容易计算，但理解它们的相对重要性却不容易。在这种情况下，请使用网络/图随机化。计算手头的图表和其他几个随机生成的类似图表的指标。例如，这些相似性图可以具有相同数量的密度和节点。通常，您可以通过生成1000 个相似的随机图表、计算每个图表的指标并将其与当前图表上的相同指标进行比较来创建基准。
在数据科学中，当试图阐述有关图表的观点时，将其与随机生成的图表进行比较会很有帮助。
熟悉Python 图表
使用Python 中的networkx 包。可以安装在Anaconda 根环境中（如果您使用的是Anaconda 的Python 发行版）。您也可以使用pip install 来安装它。
让我们看看使用Networkx 包可以完成的一些常见事情。包含导入和创建图表以及图表可视化的方法。
图形制作
将网络x 导入为nx
#创建一个图表
G=nx.Graph() # G 此时为空
#添加节点
G.add_node(1)
G.add_nodes_from([2,3]) # 您还可以通过传递列表参数来添加节点列表
#添加边缘
G.add_edge(1,2)
e=(2,3)
G.add_edge(*e) # * 解压元组
G.add_edges_from([(1,2), (1,3)]) # 你可以像节点一样从列表中添加边
可以在创建时通过传递包含节点和属性字典的元组来添加节点和边属性。
除了逐节点或逐边构建图之外，还可以通过一些经典的图操作来生成图，例如：
subgraph(G, nbunch) - 在nbunch 的节点上诱导G 的子图视图
Union(G1,G2) - 图并集
disjoint_union(G1,G2) - 假设所有节点都不同的图并集
cartesian_product(G1,G2) - 返回笛卡尔积图
compose(G1,G2) - 组合标识两者共有节点的图。
补集(G) - 图补集
create_empty_copy(G) - 返回同一图类的空副本。
Convert_to_undirected(G) - 返回G 的无向表示。
Convert_to_directed(G) - 返回G 的有向表示。
每种类型的图表都有一个单独的类。例如，您可以使用nx.DiGraph 类来创建有向图。某些包含路径的图形可以使用单一方法直接创建。有关图表方法的完整列表，请参阅完整文档。本文末尾提供了链接。
图像（\'图像/graphclasses.PNG\'，宽度=400）
访问边和节点
可以使用G.nodes 和G.edges 方法访问节点和边。可以使用括号/下标方法访问各个节点和边。
G.nodes()
节点视图((1,2,3))
G.edges()
EdgeView([(1, 2), (1, 3), (2, 3)])
G[1] # 与G.adj[1] 相同
AtlasView({2: {}, 3: {}})
G[1][2]
{}
G.边缘[1, 2]
{}
图形可视化
尽管Networkx 提供了图形可视化的基本功能，但其主要目的是帮助图形分析而不是图形可视化。可视化图表很困难，因此我们使用专门为此任务设计的工具。 Matplotlib 提供了一些有用的函数。然而，GraphViz 可能是最好的工具，因为它提供了PyGraphViz 的Python 接口（链接位于文档末尾）。
%matplotlib 内联
将matplotlib.pyplot 导入为plt
nx.draw(G)
首先你需要安装Graphviz。然后使用命令pip install pygraphviz --install-option=。安装选项要求您指定库的路径并将文件夹包含在Graphviz 中。
将pygraphviz 导入为pgv
d={\'1\': {\'2\': 无}, \'2\': {\'1\': 无， \'3\': 无}, \'3\': {\'1\': 无}}
A=pgv.AGraph(数据=d)
print(A) # 这是“字符串”或图形的简单表示
输出：
精确图\\\'\\\' {
1 - 2；
23;
3 -- 1;
}
PyGraphviz 可以很好地控制边和节点的各种属性。这为您提供了非常好的可视化效果。
# 让我们创建另一个图表，我们可以单独控制每个节点的颜色
B=pgv.AGraph()
# 设置所有节点的公共节点属性
B.node_attr[\'style\']=\'fill\'
B.node_attr[\'形状\']=\'圆形\'
B.node_attr[\'fixedsize\']=\'true\'
B.node_attr[\'fontcolor\']=\'#FFFFFF\'
# 为每个节点创建并设置不同的节点属性（使用for循环）
对于(16): 范围内的i
B.add_edge(0,i)
n=B.get_node(i)
n.attr[\'fillcolor\']=\\\'#%2x0000\\\'%(i*16)
n.attr[\'高度\']=\\\'%s\\\'%(i/16.0+0.5)
n.attr[\'宽度\']=\\\'%s\\\'%(i/16.0+0.5)
B.draw(\'star.png\',prog=\\\'circo\\\') # 这将在本地目录中创建一个.png 文件，如下所示。
Image(\'images/star.png\', width=650) # 上面创建的图形可视化。
可视化通常被认为是与图形分析不同的任务。分析的图导出为点文件。然后仅显示点文件以显示您想要表示的内容。
数据分析示例
寻找一个通用数据集（不是特定于图的）并执行一些操作（在pandas 中），以便您可以将其以边列表的形式输入到图中。边列表是包含定义每条边的顶点的元组列表。
我们关注的数据集来自航空业。包含有关路线的基本信息。旅程有起点和终点。还有一些列显示行程中每段的到达和出发时间。正如您可以想象的那样，该数据集非常适合图形分析。想象一下通过路线（边缘）连接的多个城市（节点）。对于航空公司，您可以提出以下问题：
从距离和时间角度考虑，从A 到B 的最短路径是什么？有没有办法从C到D？哪个机场的交通最繁忙？哪个机场位于大多数其他机场之间？这使其成为当地的中转站。将pandas 导入为PD
将numpy 导入为np
数据=pd.read_csv(\'data/Airlines.csv\')
数据形状
(100, 16)
数据.dtypes
年int64
月份int64
日int64
dep_time float64
sched_dep_time int64
dep_delay float64
arr_time float64
sched_arr_time int64
arr_delay float64
载体对象
航班int64
尾数对象
原始对象
目标对象
播出时间float64
距离int64
dtype: 对象
我意识到起点和目的地是节点的良好候选者。一切都可以想象为节点或边的属性。一条边可以被认为是一段旅程。这些行程在时间、航班号、尾号和其他相关信息上有所不同。您可以看到年、月、日和时间信息分布在许多列中。所以我想创建一个包含所有这些信息的日期时间列。您还需要区分计划和实际的到达和出发时间。因此，您最终应该有四个日期/时间列：预计到达时间、预计出发时间、实际到达时间和实际出发时间。此外，时间列格式错误。 PM 4:30 表示为1630，而不是16:30。该列没有分隔符。一种方法是使用pandas 字符串方法和正则表达式。另请注意，sched_dep_time 和sched_arr_time 的类型为int64，而dep_time 和arr_time 的类型为float64。另一个问题是NaN 值。 # 将sched_dep_time 转换为\'std\' - 预定出发时间
data[\'std\']=data.sched_dep_time.astype(str).str.replace(\'(\\d{2}$)\', \'\') + \':\' + data.sched_dep_time.astype(str).str.提取(\'(\\d{2}$)\', Expand=False) + \':00\'
# 将sched_arr_time 转换为\'sta\' - 预计到达时间
data[\'sta\']=data.sched_arr_time.astype(str).str.replace(\'(\\d{2}$)\', \'\') + \':\' + data.sched_arr_time.astype(str).str.提取(\'(\\d{2}$)\', Expand=False) + \':00\'
# 将dep_time 转换为\'atd\' - 实际出发时间
data[\'atd\']=data.dep_time.fillna(0).astype(np.int64).astype(str).str.replace(\'(\\d{2}$)\', \'\') + \':\' + data.dep_time.fillna(0).astype(np.int64).astype(str).str.extract(\'(\\d{2}$)\', Expand=False) + \':00\'
# 将arr_time 转换为\'ata\' - 实际到达时间
data[\'ata\']=data.arr_time.fillna(0).astype(np.int64).astype(str).str.replace(\'(\\d{2}$)\', \'\') + \':\' + data.arr_time.fillna(0).astype(np.int64).astype(str).str.extract(\'(\\d{2}$)\', Expand=False) + \':00\'
时间列现已转换为您所需的格式。最后，您还可以将年、月和日列合并为日期列。这一步并不是绝对必要的。但是，您可以通过转换为日期时间格式轻松检索年、月、日（和其他）信息。
data[\'日期\']=pd.to_datetime(data[[\'年\', \'月\', \'日\']])
# 最后删除不需要的列
data=data.drop(column=[\'年\', \'月\', \'日\'])
现在我们将使用networkx函数导入数据集并直接读取pandas DataFrame。与创建图表一样，有多种方法可以将不同格式的数据输入到图表中。
将网络x 导入为nx
FG=nx.from_pandas_edgelist(data,source=\'origin\', target=\'dest\',edge_attr=True,)
FG.nodes()
输出：
NodeView((\'EWR\', \'MEM\', \'LGA\', \'FLL\', \'SEA\', \'JFK\', \'DEN\', \'ORD\', \'MIA\', \'PBI\', \'MCO\', \'CMH\' 、“MSP”、“IAD”、“CLT”、“TPA”、“DCA”、“SJU”、“ATL”、“BHM”、“SRQ”、“MSY”、“DTW”、“LAX”、“ JAX”、“RDU”、“MDW”、“DFW”、“IAH”、“SFO”、“STL”、“CVG”、“IND”、
\'RSW\', \'BOS\', \'CLE\'))
FG.edges()
输出：
EdgeView([(\'EWR\', \'MEM\'), (\'EWR\', \'SEA\'), (\'EWR\', \'MIA\'), (\'EWR\', \'ORD\'), (\'EWR\', \'MSP\'), (\'EWR\', \'TPA\'), (\'EWR\', \'MSY\'), (\'EWR\', \'DFW\'), (\'EWR\', \'IAH\'), (\'EWR\', \'SFO\'), (\'EWR\', \'CVG\'), (\'EWR\', \'IND\'), (\'EWR\', \'RDU\'), (\'EWR\', \'IAD\'), (\'EWR\', \'RSW\'), (\'EWR\', \'BOS\'), (\'EWR\', \'PBI\'), (\'EWR\', \'LAX\'), (\'EWR\', \'MCO\'), (\'EWR\', \'SJU\'), (\'LGA\', \'FLL\'), (\'LGA\', \'ORD\'), (\'LGA\', \'PBI\'), (\'LGA\', \'CMH\'), (\'LGA\', \'IAD\'), (\'LGA\', \'CLT\'), (\'LGA\', \'MIA\'), (\'LGA\', \'DCA\'), (\'LGA\', \'BHM\'), (\'LGA\', \'RDU\'), (\'LGA\', \'ATL\'), (\'LGA\', \'TPA\'), (\'LGA\', \'MDW\'), (\'LGA\', \'DEN\'), (\'LGA\', \'MSP\'), (\'LGA\', \'DTW\'), (\'LGA\', \'STL\'), (\'LGA\', \'MCO\'), (\'LGA\', \'CVG\'), (\'LGA\', \'IAH\'), (\'FLL\', \'JFK\'), (\'SEA\', \'JFK\'), (\'JFK\', \'DEN\'), (\'JFK\', \'MCO\'), (\'JFK\', \'TPA\'), (\'JFK\', \'SJU\'), (\'JFK\', \'ATL\'), (\'JFK\', \'SRQ\'), (\'JFK\', \'DCA\'), (\'JFK\', \'DTW\'), (\'JFK\', \'LAX\'), (\'JFK\', \'JAX\'), (\'JFK\', \'CLT\'), (\'JFK\', \'PBI\'), (\'JFK\', \'CLE\'), (\'JFK\', \'IAD\'), (\'JFK\', \'BOS\')])
nx.draw_networkx(FG, with_labels=True) # Quick view of the Graph. As expected we see 3 very busy airports
nx.algorithms.degree_centrality(FG) # Notice the 3 airports from which all of our 100 rows of data originates
nx.density(FG) # Average edge density of the Graphs
输出：
0.09047619047619047
nx.average_shortest_path_length(FG) # Average shortest path length for ALL paths in the Graph
输出：
2.36984126984127
nx.average_degree_connectivity(FG) # For a node of degree k - What is the average of its neighbours\' degree
输出：
{1: 19.307692307692307, 2: 19.0625, 3: 19.0, 17: 2.0588235294117645, 20: 1.95}
从可视化中（上面的方式）可以明显看出 - 从一些机场到其他机场有多条路径。 假如想要计算2个机场之间的最短路线。我们可以想到几种方法：
距离最短的路径。飞行时间最短的路径。我们可以通过距离或飞行时间来给路径赋予权重，并用算法计算最短路径。请注意，这是一个近似的解决方案 - 实际问题是计算当你到达中转机场时的航班可用性加候机的等待时间，这才是一种更完整的方法，也是人们计划旅行的方式。出于本文的目的，我们将假设你到达机场时可以随时使用航班并使用飞行时间作为权重，从而计算最短路径。
让我们以JAX和DFW机场为例：
# Let us find all the paths available
for path in nx.all_simple_paths(FG, source=\'JAX\', target=\'DFW\'):
print(path)
# Let us find the dijkstra path from JAX to DFW.
# You can read more in-depth on how dijkstra works from this resource - https://courses.csail.mit.edu/6.006/fall11/lectures/lecture16.pdf
dijpath = nx.dijkstra_path(FG, source=\'JAX\', target=\'DFW\')
dijpath
输出：
[\'JAX\', \'JFK\', \'SEA\', \'EWR\', \'DFW\']
# Let us try to find the dijkstra path weighted by airtime (approximate case)
shortpath = nx.dijkstra_path(FG, source=\'JAX\', target=\'DFW\', weight=\'air_time\')
shortpath
输出：
[\'JAX\', \'JFK\', \'BOS\', \'EWR\', \'DFW\']
结语
本文充其量只是对图论和网络分析这一非常有趣的领域进行了粗浅的介绍。对理论和Python软件包的了解将为任何数据科学家的工具库增加一个有价值的工具。 对于上面使用的数据集，可以提出一系列其他问题，例如：
在给定成本，飞行时间和可用性的情况下，找到两个机场之间的最短路径？作为一家航空公司，你们拥有一队飞机。你了解航班的需求。假设你有权再运营2架飞机（或者为你的机队添加2架飞机），把这两架飞机投入到哪条航线可以最大限度地提高盈利能力？你可以重新安排航班和时刻表以优化某个参数吗？（如时效性或盈利能力等）如果你解决了这些问题，请在下面的评论中告诉我们！
网络分析将有助于解决一些常见的数据科学问题，并在更大规模和抽象的情况下对其进行可视化。如果想了解更多有关其他内容的信息，请发表评论。
参考文献
1. History of Graph Theory || S.G. Shrinivas et. al
2. Big O Notation cheatsheet
3. Networkx reference documentation
4. Graphviz download
5. Pygraphvix
6. Star visualization
7. Dijkstra Algorithm
原文标题：
An Introduction to Graph Theory and Network Analysis (with Python codes)
链接：
https://www.analyticsvidhya.com/blog/2023/04/introduction-to-graph-theory-network-analysis-python-codes/
译者简介
和中华，留德软件工程硕士。由于对机器学习感兴趣，硕士论文选择了利用遗传算法思想改进传统kmeans。目前在杭州进行大数据相关实践。加入数据派THU希望为IT同行们尽自己一份绵薄之力，也希望结交许多志趣相投的小伙伴。
转载请注明THU数据派
运营人员：冉小山