图论基础：从数学定义到数据结构

图论基础：从数学定义到数据结构

图论作为数学与计算机科学的交叉领域，其核心思想是用点和线构成的网络来描述事物之间的关系。在现实世界中，从社交网络中的用户关系，到交通网络中的道路连接，再到分子结构中的原子键合，无一不可以用图来抽象表示。正是这种强大的抽象能力，使得图论成为理解复杂系统的一把钥匙，也为图神经网络的诞生与发展奠定了坚实的理论基础。

本章将系统介绍图论的核心概念及其在计算机中的表示方法。我们首先从图的基本定义出发，探讨无向图、有向图、加权图、多重图等不同类型图结构的数学本质；随后深入讲解邻接矩阵、度矩阵、拉普拉斯矩阵等代数表示方法，揭示图结构背后的数学性质；接着介绍PageRank、特征向量中心性等节点重要性度量指标，帮助读者理解如何从图结构中提取有价值的节点信息；最后讨论图的存储数据结构选择策略，为后续章节的算法实现提供工程实践指导。通过本章的学习，读者将建立起完整的图论知识体系，为深入学习图神经网络算法做好充分准备。

图的基本定义与分类

形式化定义与核心要素

从数学的角度来看，图（Graph）是由顶点（Vertex）和边（Edge）组成的二元组结构。更形式化地说，一个图 $G$ 可以表示为 $G = (V, E)$，其中 $V$ 是非空有限集合，称为顶点集（Vertex Set），其中的元素称为顶点（Vertex）或节点（Node）；$E$ 是顶点集合的二元组集合，称为边集（Edge Set），其中的元素称为边（Edge）。顶点的数量称为图的阶（Order），记作 $|V|$ 或 $n$；边的数量称为图的规模（Size），记作 $|E|$ 或 $m$。

在计算机科学中，顶点通常被编号为 $1, 2, 3, \ldots, n$，边的集合可以表示为：

$$E \subseteq \{ \{u, v\} : u, v \in V, u \neq v \}$$

这个定义表明，每条边连接两个不同的顶点。根据边是否有方向，图可以分为不同的类型，这一分类对后续的算法设计具有重要影响。

无向图与有向图

无向图（Undirected Graph）是最基础的图类型，其特点是边没有方向性，即边 $\{u, v\}$ 与边 $\{v, u\}$ 表示同一条边。在无向图中，如果两个顶点之间存在边，则称这两个顶点相邻（Adjacent）或邻接的。以顶点 $v$ 为端点的边的数目称为该顶点的度（Degree），记作 $d(v)$ 或 $\deg(v)$。根据握手定理（Handshaking Lemma），无向图中所有顶点的度之和等于边数的两倍：

$$\sum_{v \in V} \deg(v) = 2|E|$$

这一一定理的理解非常直观：每条边恰好贡献两个度，分别连接到它的两个端点。

有向图（Directed Graph 或 Digraph）与无向图的根本区别在于边具有方向性。在有向图中，边被表示为有序对 $(u, v)$，表示从顶点 $u$ 指向顶点 $v$ 的有向边，其中 $u$ 称为起点（Source）或尾（Tail），$v$ 称为终点（Target）或头（Head）。从顶点 $v$ 发出的边的数目称为该顶点的出度（Out-degree），记作 $d^+(v)$ 或 $\deg^+(v)$；指向顶点 $v$ 的边的数目称为该顶点的入度（In-degree），记作 $d^-(v)$ 或 $\deg^-(v)$。对于有向图，所有顶点的出度之和等于所有顶点的入度之和，都等于边数 $m$：

$$\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |E|$$

在有向图中，如果同时存在边 $(u, v)$ 和 $(v, u)$，则称这两个顶点之间存在双向连接。在某些应用场景下，有向图可以进一步划分为强连通图、弱连通图等类型，这将在后续的连通性分析中详细讨论。

考虑一个具体的社交网络例子：微博平台中的关注关系就可以用有向图表示，其中顶点代表用户，有向边 $(u, v)$ 表示用户 $u$ 关注了用户 $v$。在这种表示下，入度就是用户的粉丝数，出度就是用户关注的人数。这种建模方式清晰地揭示了有向图在表示非对称关系时的优势。

加权图与多重图

加权图（Weighted Graph）在图的基本定义基础上为边赋予数值权重，用于表示边的“成本”“距离”“容量”等属性。在加权无向图中，权重函数 $w: E \rightarrow \mathbb{R}$ 为每条边分配一个实数值，且满足 $w(u, v) = w(v, u)$；在加权有向图中，权重函数可能为不同方向的边分配不同权重。加权图在现实生活中应用广泛：道路网络中边的权重可以表示道路长度或行驶时间；通信网络中边的权重可以表示带宽或延迟；社交网络中边的权重可以表示用户之间的互动强度。

加权图的一个重要扩展是符号图（Signed Graph），其边带有正负符号，分别表示正向关系（如朋友、信任、支持）和负向关系（如敌人、不信任、反对）。符号图在社交网络分析中具有重要应用，例如分析观点极化、检测社区分裂等问题。

多重图（Multigraph）允许两个顶点之间存在多条边，这与简单图（Simple Graph）形成对比。简单图要求任意两个顶点之间至多存在一条边，且不存在自环（Loop，即连接顶点自身的边）。多重图中的多条平行边可以用边的多重性（Multiplicity）来描述，当多重性为 $k$ 时，表示两个顶点之间存在 $k$ 条边。多重图在建模交通网络时特别有用，例如两个城市之间可能存在多条公路或航线。

完全图与正则图

完全图（Complete Graph）是一种特殊的简单图，其中任意两个不同的顶点之间都恰好存在一条边。$n$ 个顶点的完全图记作 $K_n$，其边数为 $\binom{n}{2} = \frac{n(n-1)}{2}$。完全图是图论研究中重要的基准图结构，许多图算法的复杂度下界都基于完全图进行分析。

正则图（Regular Graph）中所有顶点具有相同的度。如果一个正则图的每个顶点度数为 $k$，则称其为 $k$-正则图（$k$-Regular Graph）。正则图在网络设计中具有重要意义，因为它们具有良好的对称性和均匀性。著名的彼得森图（Petersen Graph）是一个经典的3-正则图，包含10个顶点和15条边，因其独特的性质而在图论研究中占据重要地位。

连通性与子图结构

在无向图中，如果从任意顶点出发都存在一条路径到达其他任意顶点，则称该图是连通图（Connected Graph）。不连通的无向图可以分解为若干连通分量（Connected Component），每个连通分量都是极大的连通子图。连通性是图结构的核心性质之一，它决定了信息在网络中传播的能力。

有向图的连通性概念更为复杂。如果有向图中任意两个顶点 $u$ 和 $v$ 之间都存在从 $u$ 到 $v$ 的有向路径和从 $v$ 到 $u$ 的有向路径，则称该有向图是强连通的（Strongly Connected）。如果忽略边的方向后图是连通的，则称该有向图是弱连通的（Weakly Connected）。

子图（Subgraph）是由图的顶点子集和边子集构成的图。给定图 $G = (V, E)$ 和顶点子集 $V' \subseteq V$，由 $V'$ 导出的子图（Induced Subgraph）$G[V']$ 包含 $V'$ 中的所有顶点，以及 $E$ 中两端点都在 $V'$ 中的所有边。导出子图的概念在社区检测、图聚类等任务中具有重要应用。

图的代数表示方法

邻接矩阵

邻接矩阵（Adjacency Matrix）是表示图结构最直接的方式。给定一个包含 $n$ 个顶点的图，其邻接矩阵是一个 $n \times n$ 的方阵 $\mathbf{A}$，其中元素 $A_{ij}$ 表示顶点 $i$ 和顶点 $j$ 之间的关系。

对于无向图，邻接矩阵是对称的，即 $A_{ij} = A_{ji}$；对于有向图，邻接矩阵通常是非对称的。简单的二值邻接矩阵定义如下：

$$A_{ij} = \begin{cases} 1 & \text{如果} (i, j) \in E \\ 0 & \text{否则} \end{cases}$$

对于加权图，邻接矩阵的元素可以是边的权重：

$$A_{ij} = \begin{cases} w(i, j) & \text{如果} (i, j) \in E \\ 0 & \text{否则} \end{cases}$$

邻接矩阵的主要优点是查询任意两个顶点之间是否存在边的时间复杂度为 $O(1)$，且矩阵运算可以高效地实现图的代数操作。例如，两个邻接矩阵的乘积 $\mathbf{A} \cdot \mathbf{A}$ 的结果矩阵中，元素 $(i, j)$ 表示从顶点 $i$ 到顶点 $j$ 长度为2的路径数目。这一性质在分析图的路径结构时非常有用。

然而，邻接矩阵的主要缺点是空间复杂度为 $O(n^2)$，对于稀疏图（Sparse Graph）而言造成严重的空间浪费。在实际应用中，许多图的边数远小于顶点数平方，例如社交网络中用户之间的好友关系通常是稀疏的。因此，稀疏矩阵表示成为处理大规模图数据的关键技术。

考虑一个包含一百万个顶点的社交网络图，即使每个用户平均有100个好友，其边数约为1亿，远小于 $10^{12}$ 的矩阵元素总数。在这种情况下，稠密的邻接矩阵需要约1TB的存储空间，而稀疏表示可能只需要几十GB。

度矩阵

度矩阵（Degree Matrix）是一个对角矩阵，其对角线上的元素表示对应顶点的度。对于无向图，度矩阵 $\mathbf{D}$ 定义为：

$$D_{ii} = \deg(i), \quad D_{ij} = 0 \text{ 对于 } i \neq j$$

对于有向图，需要分别定义出度矩阵 $\mathbf{D}^+$ 和入度矩阵 $\mathbf{D}^-$：

$$D^+_{ii} = \deg^+(i), \quad D^-_{ii} = \deg^-(i)$$

度矩阵与邻接矩阵结合使用可以完成许多重要的图分析任务。在后续讨论拉普拉斯矩阵时，我们将看到度矩阵如何与邻接矩阵协同工作以揭示图的结构性质。

拉普拉斯矩阵

拉普拉斯矩阵（Laplacian Matrix）是图论中最重要的矩阵之一，它在谱图理论、图神经网络和许多图算法中扮演核心角色。拉普拉斯矩阵有多种等价定义，最常用的是：

$$\mathbf{L} = \mathbf{D} - \mathbf{A}$$

其中 $\mathbf{D}$ 是度矩阵，$\mathbf{A}$ 是邻接矩阵。对于无向图，$\mathbf{L}$ 是对称半正定矩阵。

拉普拉斯矩阵具有许多优美的数学性质。首先，它的行和为零：

$$\sum_{j} L_{ij} = D_{ii} - \sum_{j} A_{ij} = \deg(i) - \deg(i) = 0$$

这意味着 $\mathbf{L}$ 至少有一个特征值为0，对应的特征向量是全1向量 $\mathbf{1}$。拉普拉斯矩阵的第二个重要性质是它是半正定的，即对于任意向量 $\mathbf{x} \in \mathbb{R}^n$：

$$\mathbf{x}^\top \mathbf{L} \mathbf{x} = \frac{1}{2} \sum_{(i,j) \in E} w_{ij} (x_i - x_j)^2 \geq 0$$

这一二次型的表达式称为图的Dirichlet形式（Dirichlet Form），它揭示了拉普拉斯矩阵与图的边权重之间的深层联系。直观上，如果把 $\mathbf{x}$ 看作定义在图顶点上的函数，那么 $\mathbf{x}^\top \mathbf{L} \mathbf{x}$ 度量了该函数在相邻顶点之间的变化程度。

拉普拉斯矩阵的特征值具有明确的图论意义。对于连通图，拉普拉斯矩阵的最小非零特征值 $\lambda_2$（称为谱 gap 或Fiedler值）与图的连通性密切相关。$\lambda_2$ 越大，图的结构越紧密；$\lambda_2$ 越小，图越接近分裂。这一性质被广泛应用于图分割、社区检测等任务。

标准化拉普拉斯矩阵

在图神经网络中，标准化的拉普拉斯矩阵比原始拉普拉斯矩阵更常用，因为它们避免了特征值尺度问题。最常用的两种标准化形式是：

对称标准化拉普拉斯矩阵：

$$\mathbf{L}_{sym} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$$

随机游走标准化拉普拉斯矩阵（也称为转移矩阵的拉普拉斯形式）：

$$\mathbf{L}_{rw} = \mathbf{D}^{-1} \mathbf{L} = \mathbf{I} - \mathbf{D}^{-1} \mathbf{A}$$

对称标准化拉普拉斯矩阵是对称矩阵，具有实数特征值，且特征值范围在 $[0, 2]$ 之间。随机游走标准化拉普拉斯矩阵是非对称的，但其特征值与随机游走过程密切相关。

在实际应用中，选择哪种标准化形式取决于具体任务。GCN（Graph Convolutional Network）模型默认使用 $\mathbf{L}_{rw}$ 的变体，而图小波神经网络则可能使用对称标准化形式。理解这些矩阵的数学性质对于设计和分析图神经网络架构至关重要。

邻接矩阵的幂与图的结构

邻接矩阵的幂运算揭示了图的路径结构。设 $\mathbf{A}$ 是图 $G$ 的邻接矩阵，则矩阵 $(\mathbf{A}^k)_{ij}$ 表示从顶点 $i$ 到顶点 $j$ 长度为 $k$ 的路径数量。这一事实在图神经网络的消息传递机制中具有重要意义。

对于无权图，邻接矩阵的特征多项式系数与图的树数目、子图模式等结构信息相关。对于加权图，邻接矩阵的特征值谱反映了图的周期性、对称性等高级结构性质。谱图理论正是基于这些性质建立起图结构与代数性质之间的桥梁。

节点重要性度量

度中心性

度中心性（Degree Centrality）是最简单直观的节点重要性指标，直接使用顶点的度来衡量其重要性。在无向图中，顶点 $v$ 的度中心性定义为：

$$C_D(v) = \frac{\deg(v)}{n-1}$$

其中 $n-1$ 是最大可能的邻接点数，使得中心性值归一化到 $[0, 1]$ 区间。

对于有向图，度中心性可以分别基于入度、出度或两者之和计算。入度中心性反映了一个节点被其他节点“指向”或“选择”的程度，在网页排名、学术引用等场景中具有实际意义；出度中心性则反映了一个节点主动连接外部的能力。

度中心性的优点是计算简单、时间复杂度低，适用于大规模图的初步分析。然而，它也有明显的局限性：度中心性只考虑了直接邻居的数量，忽略了邻居的质量和整个图的结构信息。一个高度节点可能连接到许多不重要的节点，而一个低度节点可能位于连接不同社区的关键位置。

特征向量中心性

特征向量中心性（Eigenvector Centrality）通过考虑邻居的重要性来度量节点的重要性，克服了度中心性的一个重要缺陷。其核心思想是：一个节点的重要性既取决于其邻居的数量，也取决于其邻居的重要性。

形式上，节点 $v$ 的特征向量中心性 $x_v$ 满足以下递归关系：

$$x_v = \frac{1}{\lambda} \sum_{u \in N(v)} x_u$$

其中 $N(v)$ 是节点 $v$ 的邻居集合，$\lambda$ 是一个常数。将这个定义向量化，得到：

$$\mathbf{A} \mathbf{x} = \lambda \mathbf{x}$$

这表明 $\mathbf{x}$ 是邻接矩阵 $\mathbf{A}$ 的特征向量，$\lambda$ 是对应的特征值。根据Perron-Frobenius定理，对于连通的正矩阵，最大特征值对应的特征向量是唯一且所有分量同号的。因此，取最大特征值 $\lambda_{\max}$ 对应的特征向量，其分量即为各节点的特征向量中心性。

特征向量中心性在PageRank算法中得到了进一步发展和应用。两者的区别在于：特征向量中心性考虑所有特征路径，而PageRank引入了阻尼因子来处理“悬挂节点”（没有出边的节点）问题。

PageRank算法

PageRank算法由Google创始人Larry Page和Sergey Brin提出，用于网页重要性排序，是现代搜索引擎的核心技术之一。PageRank将互联网建模为有向图，网页作为节点，超链接作为有向边。算法假设一个随机浏览者以概率 $d$（称为阻尼系数，通常设为0.85）跟随链接浏览网页，以概率 $1-d$ 随机跳转到任意网页。根据这一随机游走模型，每个网页被访问的稳态概率即为该网页的PageRank值。

设 $n$ 为网页总数，$\mathbf{M}$ 为转移概率矩阵（每列归一化的邻接矩阵），则PageRank向量 $\mathbf{p}$ 满足：

$$\mathbf{p} = d \mathbf{M} \mathbf{p} + \frac{1-d}{n} \mathbf{1}$$

其中 $\mathbf{1}$ 是全1向量。另一种等价形式是：

$$\mathbf{p} = \left( d \mathbf{M} + \frac{1-d}{n} \mathbf{1} \mathbf{1}^\top \right) \mathbf{p}$$

注意到矩阵 $\mathbf{S} = d \mathbf{M} + \frac{1-d}{n} \mathbf{1} \mathbf{1}^\top$ 是一个列随机矩阵（每列和为1），因此PageRank实际上是矩阵 $\mathbf{S}$ 的主特征向量。

PageRank的计算通常采用幂迭代法：从初始分布 $\mathbf{p}^{(0)}$ 开始，迭代计算 $\mathbf{p}^{(t+1)} = \mathbf{S}^\top \mathbf{p}^{(t)}$，直到收敛。在实际互联网规模的数据上，PageRank可以在几秒内完成计算。

PageRank的拓展形式包括个性化PageRank（Personalized PageRank），它允许从特定节点出发的随机游走，广泛应用于推荐系统和社区检测。HITS算法（Hyperlink-Induced Topic Search）则同时考虑了枢纽分数（Hub Score）和权威分数（Authority Score），与PageRank形成互补。

###