目录
图论是数学的一个基础分支，涉及对图和网络的研究。
图是复杂数据结构的可视化表示，帮助我们理解不同实体之间的关系。图论为我们提供了建模和分析各种现实世界问题的工具，例如交通系统、社交网络和互联网连接。
在本章中，我们将深入探讨图论的基础知识，涵盖三个主要主题：图属性、图概念和图算法。我们将首先定义图及其组件。然后我们将介绍不同类型的图，解释它们的属性和应用。接下来，我们将介绍基本的图概念、对象和度量，包括邻接矩阵。最后，我们将深入研究图算法，重点关注两个基本算法，广度优先搜索（BFS）和深度优先搜索（DFS）。
通过本章的学习，您将建立起扎实的图论基础，使您能够应对更高级的主题并设计图神经网络。
在本章中，我们将涵盖以下主要主题：
- 介绍图属性
- 发现图概念
- 探索图算法
技术要求
本章的所有代码示例都可以在GitHub上找到：https://github.com/PacktPublishing/Hands-On-Graph-Neural-Networks-Using-Python/tree/main/Chapter02。
在您的本地计算机上运行代码所需的安装步骤可以在本书的前言中找到。
介绍图属性
在图论中，图是一种数学结构，由一组对象组成，称为顶点或节点，用于表示一组连接，其中边是连接顶点对的集合。用数学符号表示为G = (V, E)，其中V表示顶点的集合，E表示边的集合。
图的节点可以表示任何对象，如城市、人员、网页或分子，而边表示它们之间的关系或连接，如实际道路、社交关系、超链接或化学键。
本节概述了后续章节中广泛使用的基本图属性。
有向图
图的最基本属性之一是它是有向图还是无向图。在有向图中，也称为有向图，每条边都有一个方向或定向。这意味着边以特定方向连接两个节点，其中一个节点是源节点，另一个是目标节点。相反，无向图具有无向边，边没有方向。这意味着两个顶点之间的边可以在任何方向上遍历，并且我们访问节点的顺序不重要。
在Python中，我们可以使用networkx库来定义一个无向图，如下所示：nx.Graph()。
import networkx as nx
G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F'), ('C', 'G')])
G图对应于以下图示：
图2.1 无向图示例
创建有向图的代码类似；我们只需将nx.Graph()替换为nx.DiGraph()：
DG = nx.DiGraph()
DG.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F'), ('C', 'G')])
DG图对应于以下图示：
图2.2 有向图示例
在有向图中，通常使用箭头表示边的方向，如图2.2所示。
加权图
图的另一个重要属性是边是否带权。在加权图中，每条边都有一个与之相关的权重或成本。这些权重可以表示各种因素，如距离、行程时间或成本。
例如，在一个交通网络中，边的权重可能表示不同城市之间的距离或旅行所需的时间。相比之下，无权图的边没有与之相关的权重。这些类型的图通常在节点之间的关系是二进制的情况下使用，边只表示它们之间的连接存在与否。
我们可以修改之前的无向图，给边添加权重。在networkx中，图的边由一个元组来定义，包含起始节点、结束节点和一个指定边权重的字典：
WG = nx.Graph()
WG.add_edges_from([('A', 'B', {"weight": 10}), ('A', 'C', {"weight": 20}), ('B', 'D', {"weight": 30}), ('B', 'E', {"weight": 40}), ('C', 'F', {"weight": 50}), ('C', 'G', {"weight": 60})])
labels = nx.get_edge_attributes(WG, "weight")
WG图对应以下图示：
图2.3 加权图示例
连通图
图的连通性是图论中的一个基本概念，与图的结构和功能密切相关。
在一个连通图中，图中任意两个顶点之间都存在一条路径。形式上，如果对于图中的每一对顶点，存在从到的路径，则图是连通的。相反，如果图不是连通的，则称为不连通图，这意味着至少有两个顶点之间没有路径连接。
networkx库提供了一个内置函数来验证图是否连通。在下面的示例中，第一个图包含孤立节点（4和5），而第二个图没有。这在图2.4中可视化如下：
G1 = nx.Graph()
G1.add_edges_from([(1, 2), (2, 3), (3, 1), (4, 5)])
print(f"Is graph 1 connected? {nx.is_connected(G1)}")
G2 = nx.Graph()
G2.add_edges_from([(1, 2), (2, 3), (3, 1), (1, 4)])
print(f"Is graph 2 connected? {nx.is_connected(G2)}")
这段代码输出如下内容：
Is graph 1 connected? False
Is graph 2 connected? True
第一个图由于节点4和5的存在是不连通的。另一方面，第二个图是连通的。这个属性在小图中很容易可视化，如下图所示：
图2.4 – 左侧：具有孤立节点的图1（不连通图）；右侧：图2，其中每个节点至少连接到另一个节点（连通图）
连通图具有几个有趣的属性和应用。例如，在通信网络中，连通图确保任意两个节点可以通过一条路径进行通信。相比之下，不连通图可能有孤立节点，这些节点无法与网络中的其他节点通信，这使得设计高效的路由算法具有挑战性。
衡量图的连通性有不同的方式。其中一个最常见的衡量标准是需要删除的最小边数，以断开图的连接，这称为图的最小割。最小割问题在网络流优化、聚类和社区检测中有几个应用。
图类型
除了常用的图类型之外，还有一些特殊类型的图，具有独特的属性和特征：
- 树是一个连通的、无向的无环图（就像图2.1中的图）。由于在树中任意两个节点之间只有一条路径，因此树是图的一种特殊情况。树经常用于建模分层结构，如家谱、组织结构或分类树。
- 根树(rooted tree)是一种树，其中一个节点被指定为根节点，并且所有其他顶点都通过唯一路径连接到它。根树经常用于计算机科学中表示分层数据结构，如文件系统或XML文档的结构。
- 有向无环图（DAG）是一种无环的有向图（就像图2.2中的图）。这意味着边只能沿着特定方向遍历，并且没有环路或循环。DAG经常用于建模任务或事件之间的依赖关系 - 例如，在项目管理中或计算作业的关键路径时。
- 二分(bipartite)图是一种图，其中顶点可以划分为两个不相交的集合，使得所有边连接到不同集合中的顶点。二分图经常用于数学和计算机科学中建模两种不同类型对象之间的关系，如买家和卖家，或员工和项目。
- 完全图是一种图，其中每对顶点之间都由一条边连接。完全图经常用于组合学中建模涉及所有可能成对连接的问题，并用于计算机网络中建模完全连接的网络。
图2.5 常见类型的图
现在我们已经回顾了图的基本类型，让我们继续探讨一些最重要的图对象。理解这些概念将有助于我们有效地分析和操作图。
探索图概念
在本节中，我们将探讨图论中的一些基本概念，包括图对象（如度和邻居）、图度量（如中心性和密度）以及邻接矩阵表示法。
基本对象
图论中的一个关键概念是节点的度，即与该节点相连的边的数量。如果一个节点是边的端点之一，则称该边与该节点相连。在无向图中，节点的度通常用 deg(v) 表示，它定义为与该节点相连的边的数量。对于有向图和无向图，节点的度的定义都是连接到它的有向边的数量：
请注意，如果节点与自身相连（称为环，或自环），则度增加两个。
在有向图中，度分为入度和出度两种类型。入度（表示为 $deg^-(v)$）表示指向该节点的边的数量，出度（表示为 $deg^+(v)$）表示从该节点开始指向其他节点的边的数量。在这种情况下，自环会增加一个单位到入度和出度。
入度和出度对于分析和理解有向图至关重要，因为它们提供了有关信息或资源在图中分布方式的见解。例如，具有高入度的节点可能是重要的信息或资源来源。相反，具有高出度的节点可能是信息或资源的重要目的地或消费者。
在 networkx 中，我们可以使用内置方法简单地计算节点的度、入度或出度。让我们为图2.1中的无向图和图2.2中的有向图计算它们：
G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F'), ('C', 'G')])
print(f"deg(A) = {G.degree['A']}")
DG = nx.DiGraph()
DG.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F'), ('C', 'G')])
print(f"deg^-(A) = {DG.in_degree['A']}")
print(f"deg^+(A) = {DG.out_degree['A']}")
这段代码打印以下输出：
deg(A) = 2
deg^-(A) = 0
deg^+(A) = 2
我们可以将其与图2.1和图2.2中的图进行比较：节点连接到两条边（度=2），但与它们中任何一个的目标不相关（入度=0）。
邻居（Neighbors）是指通过边直接连接到特定节点的节点。此外，如果两个节点共享至少一个公共邻居，则称它们是相邻的(adjacent)。邻居和邻接的概念对于许多图算法和应用非常重要，例如搜索两个节点之间的路径或识别网络中的群集。
在图论中，路径是连接图中两个节点（或更多）的一系列边。路径的长度是沿着路径遍历的边的数量。有不同类型的路径，但其中两种特别重要：
- 简单路径是一条路径，除了起点和终点顶点外，不访问任何节点超过一次
- 环(cycle)是一条路径，其中第一个和最后一个顶点相同。如果图中不包含循环，则称为无环图（例如树和DAG）
度和路径可以用来确定网络中节点的重要性。这个度量称为中心性(centrality)。
图度量
中心性量化了网络中顶点或节点的重要性。它帮助我们根据节点的连接性和对网络内信息流或交互的影响来识别图中的关键节点。中心性有几种度量方法，每种方法都提供了对节点重要性不同角度的视角：
- 度中心性(Degree centrality)是最简单和最常用的中心性度量之一。它简单地定义为节点的度数。高度中心性表示顶点与图中其他顶点高度连接，从而对网络产生重大影响。
- 紧密中心性(Closeness centrality)衡量节点与图中所有其他节点的接近程度。它对应于目标节点与图中所有其他节点之间最短路径的平均长度。具有高接近中心性的节点可以快速到达网络中的所有其他顶点。
- 中介中心性(Betweenness centrality)衡量了节点在图中其他节点之间最短路径上出现的次数。具有高中介中心性的节点充当图中不同部分之间的瓶颈或桥梁。
让我们使用networkx的内置函数在之前的图中计算这些度量，并分析结果：
print(f"Degree centrality = {nx.degree_centrality(G)}")
print(f"Closeness centrality = {nx.closeness_centrality(G)}")
print(f"Betweenness centrality = {nx.betweenness_centrality(G)}")
前面的代码打印了包含每个节点得分的字典：
Degree centrality = {'A': 0.3333333333333333, 'B': 0.5, 'C': 0.5, 'D': 0.16666666666666666, 'E': 0.16666666666666666, 'F': 0.16666666666666666, 'G': 0.16666666666666666}
Closeness centrality = {'A': 0.6, 'B': 0.5454545454545454, 'C': 0.5454545454545454, 'D': 0.375, 'E': 0.375, 'F': 0.375, 'G': 0.375}
Betweenness centrality = {'A': 0.6, 'B': 0.6, 'C': 0.6, 'D': 0.0, 'E': 0.0, 'F': 0.0, 'G': 0.0}
在图中，节点的重要性取决于所使用的中心性类型。度中心性认为节点和比节点更重要，因为它们与图中的更多邻居连接。然而，在接近中心性中，节点是最重要的，因为它可以最短路径到达图中的任何其他节点。另一方面，节点之间的最短路径数相等，因此它们的中介中心性相同。
除了这些度量之外，在接下来的章节中，我们将看到如何使用机器学习技术计算节点的重要性。然而，这并不是我们将涵盖的唯一度量。
事实上，密度(density)是另一个重要的度量，表示图的连接性。它是实际边数与图中可能的最大边数之间的比率。密度较高的图被认为更连接，并且具有比密度较低的图更多的信息流。
计算密度的公式取决于图是有向的还是无向的。对于节点数为n的无向图，最大可能的边数是n(n-1)/2，而有向图为n(n-1)。因此，图的密度计算为实际边数除以最大可能边数。例如，图2.1中的稠密图具有密度约为0.2857。计算方法为：最大可能边数为7(7-1)/2=21，6/21=0.2857。
没有严格的规则来定义何为稠密图或稀疏图，但通常来说，如果图的密度大于0.5，则被认为是稠密的，如果密度小于0.1，则被认为是稀疏的。这个度量与图的一个基本问题直接相关：如何表示邻接矩阵。
邻接矩阵(adjacency matrix)表示法
邻接矩阵表示法是表示图中边的一种矩阵形式，其中每个单元格表示图中的两个节点之间是否有边相连。邻接矩阵是一个方阵，其大小为n×n，其中n是节点的数量。矩阵中的值为1表示存在节点之间的边，而值为0表示没有边。对于无向图，矩阵是对称的，而对于有向图，矩阵不一定对称。
以下图示出了与图相关的邻接矩阵：
图2.6 邻接矩阵示例
在Python中，可以将邻接矩阵实现为一个列表的列表，如下例所示：
adj = [[0,1,1,0,0,0,0],
[1,0,0,1,1,0,0],
[1,0,0,0,0,1,1],
[0,1,0,0,0,0,0],
[0,1,0,0,0,0,0],
[0,0,1,0,0,0,0],
[0,0,1,0,0,0,0]]
邻接矩阵是一种直观的表示方法，可以轻松地将其视为二维数组。使用邻接矩阵的一个主要优势是检查两个节点是否相连是一个常数时间的操作。这使得它成为测试图中边的存在性的有效方式。此外，它可用于执行矩阵运算，这对于某些图算法，如计算两个节点之间的最短路径，非常有用。
然而，添加或删除节点可能会很昂贵，因为需要调整矩阵的大小或位置。使用邻接矩阵的主要缺点之一是其空间复杂度：随着图中节点数量的增加，存储邻接矩阵所需的空间将呈指数增长【译注：应该是平方增长】。形式上，我们说邻接矩阵的空间复杂度为$O(\vert V \vert^2)$，其中n表示节点数。
总的来说，虽然邻接矩阵是表示小型图的有用数据结构，但对于较大的图来说可能不实用，因为其空间复杂度较高。此外，添加或删除节点的开销可能使其在动态变化的图中效率低下。
这就是为什么其他表示方法可能会有所帮助。例如，存储图的另一种流行方式是边列表(edge list)。边列表是图中所有边的列表，每条边由两个顶点的元组或对表示。边列表还可以包括每条边的权重或成本。这就是我们使用的数据结构来创建具有networkx的图的方式。
edge_list = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]
当我们比较应用于我们的图的两种数据结构时，很明显，边列表更简洁。这是因为我们的图相当稀疏。另一方面，如果我们的图是完全的，我们将需要边元组的数量而不是6个。这可以通过边列表来解释，它对于存储稀疏图（其中边的数量远小于节点数）更有效，其空间复杂度为$O(\vert E \vert)$，其中$\vert E \vert$是边数。
然而，检查两个顶点是否在边列表中相连需要遍历整个列表，对于具有许多边的大型图来说可能会很耗时。因此，在空间是一个关键因素的应用中更常用边列表。
第三种流行的表示方法是邻接表(adjacency list)。它由一组对组成，其中每对表示图中的一个节点及其相邻节点。这些对可以存储在链表、字典或其他数据结构中，具体取决于实现方式。例如，我们图的邻接表可能如下所示：
adj_list = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5, 6],
3: [1],
4: [1],
5: [2],
6: [2]
}
邻接表比邻接矩阵或边列表有几个优点。首先，它的空间复杂度比邻接矩阵更有效率（$O(\vert V \vert + \vert E \vert)$，其中$\vert V \vert$是节点数，$\vert E \vert$是边数）。其次，它允许高效遍历节点的相邻顶点，这在许多图算法中非常有用。最后，添加节点或边可以在恒定时间内完成。
然而，检查两个顶点是否相连可能比使用邻接矩阵更慢。这是因为它需要遍历一个顶点的邻接表，对于具有许多边的大型图来说可能会耗时。
每种数据结构都有其自身的优缺点，这取决于具体的应用和要求。在下一节中，我们将处理图并介绍两个最基本的图算法。
探索图算法
图算法在解决与图相关的问题中至关重要，例如查找两个节点之间的最短路径或检测循环。本节将讨论两种图遍历算法：BFS 和 DFS。
广度优先(Breadth-first)搜索(BFS)
BFS 是一种图遍历算法，它从根节点开始，先探索特定级别的所有相邻节点，然后再移动到下一级别的节点。它通过维护一个节点队列来工作，将每个访问过的节点标记为添加到队列中时。然后，该算法出队队列中的下一个节点，并探索其所有相邻节点，如果它们尚未被访问，则将它们添加到队列中。
BFS 的行为如图 2.7 所示：
图 2.7 – 广度优先搜索进行的图遍历示例
现在让我们看看如何在 Python 中实现它：
1.我们创建一个空图，并使用 add_edges_from() 方法添加边：
G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F'), ('C', 'G')])
2.我们定义一个名为 bfs() 的函数，该函数在图上实现 BFS 算法。该函数接受两个参数：图对象和搜索的起始节点：
def bfs(graph, node):
3.我们初始化两个列表（visited 和 queue），并添加起始节点。visited 列表跟踪在搜索过程中已访问的节点，而 queue 列表存储需要访问的节点：
visited, queue = [node], [node]
4.我们进入一个 while 循环，直到队列列表为空为止。在循环内部，我们使用 pop(0) 方法从队列列表中移除第一个节点，并将结果存储在 node 变量中：
while queue:
node = queue.pop(0)
5.我们通过 for 循环遍历节点的相邻节点。对于尚未访问过的每个相邻节点，我们将其添加到 visited 列表和 queue 列表的末尾，使用 append() 方法。完成后，我们返回 visited 列表：
for neighbor in graph[node]:
if neighbor not in visited:
visited.append(neighbor)
queue.append(neighbor)
return visited
6.我们使用 G 参数和 ‘A’ 起始节点调用 bfs() 函数：
bfs(G, 'A')
7.函数返回按访问顺序排列的访问过的节点列表：
['A', 'B', 'C', 'D', 'E', 'F', 'G']
我们得到的顺序与图 2.7 中预期的顺序相同。
BFS 在查找无权图中两个节点之间的最短路径方面特别有用。这是因为该算法按照节点距离起始节点的顺序访问节点，因此第一次访问目标节点时，它必须沿着从起始节点到目标节点的最短路径。
除了查找最短路径外，BFS 还可用于检查图是否连通或查找图的所有连通分量。它还用于诸如网络爬虫、社交网络分析和网络中的最短路径路由等应用中。
对于度数高或稀疏图的问题，这种时间复杂度可以是一个重要问题。BFS 的时间复杂度是 $O(\vert V \vert+\vert E \vert)$，其中 $\vert V \vert $ 是节点数，$\vert E \vert$ 是边数。针对这种问题，已经开发出了几种 BFS 变体来缓解这个问题，例如双向 BFS 和 A* 搜索，它们使用启发式方法来减少需要探索的节点数。
深度优先(depth-first)搜索
深度优先搜索（DFS）是一种递归算法，从根节点开始沿着每条分支尽可能远地探索，然后再回溯。
它选择一个节点并探索其所有未访问过的邻居，只有当所有邻居都被访问过时，它才会回溯。通过这样做，它沿着尽可能深的路径从起始节点开始探索图，然后再回溯到其他分支。这一过程一直持续到所有节点都被探索过为止。
DFS的行为在图2.8中有所体现：
图 2.7 – 深度优先搜索进行的图遍历示例
让我们在Python中实现DFS：
1.首先，我们初始化一个名为visited的空列表。
visited = []
2.我们定义一个名为dfs()的函数，它以visited、graph和node作为参数。
def dfs(visited, graph, node):
3.如果当前节点不在visited列表中，我们将其添加到列表中。
if node not in visited:
visited.append(node)
4.然后，我们遍历当前节点的每个邻居。对于每个邻居，我们递归调用dfs()函数，传入visited、graph和邻居作为参数。
for neighbor in graph[node]:
visited = dfs(visited, graph, neighbor)
5.dfs()函数继续以深度优先的方式探索图，访问每个节点的所有邻居，直到没有更多未访问的邻居。最后，返回visited列表。
return visited
6.我们调用dfs()函数，visited设置为空列表，图设为G，起始节点设为’A’。
dfs(visited, G, 'A')
7.函数返回按访问顺序排列的visited节点列表。
['A', 'B', 'D', 'E', 'C', 'F', 'G']
我们获得的顺序与图2.8中的预期顺序相同。
DFS在解决各种问题方面非常有用，例如找到连通分量、拓扑排序和解决迷宫问题。它特别适用于在图中找到循环，因为它以深度优先的顺序遍历图，只有在遍历过程中某个节点被访问两次时才存在循环。
与BFS类似，DFS在图中的时间复杂度为$O(\vert V \vert+\vert E \vert)$，其中 $\vert V \vert $ 是节点数，$\vert E \vert$ 是边数。它需要较少的内存，但不能保证找到最浅的路径解。最后，与BFS不同的是，DFS可能会陷入无限循环。【译注：有了Visited保存访问过的节点，应该不会死循环了。】
此外，图论中许多其他算法都建立在BFS和DFS的基础上，例如Dijkstra的最短路径算法、Kruskal的最小生成树算法和Tarjan的强连通分量算法。因此，对于希望处理图并开发更复杂图算法的人来说，对BFS和DFS的扎实理解至关重要。
总结
在本章中，我们涵盖了图论的基本内容，这是研究图和网络的数学分支。我们首先定义了图的概念，并解释了不同类型的图，如有向图、加权图和连通图。然后，我们介绍了基本的图对象（包括邻居）和度量（如中心性和密度），这些度量用于理解和分析图结构。
此外，我们讨论了邻接矩阵及其不同的表示方法。最后，我们探讨了两种基本的图算法，BFS和DFS，它们为开发更复杂的图算法打下了基础。
在第三章《使用DeepWalk创建节点表示》中，我们将探讨DeepWalk架构及其两个组件：Word2Vec和随机游走。我们将首先了解Word2Vec架构，然后使用专门的库实现它。然后，我们将深入研究DeepWalk算法，并在图上实现随机游走。
- 显示Disqus评论(需要科学上网)