图结构基础与传统图算法局限性分析

图作为一种描述实体间关系的通用数据结构，自欧拉在1736年通过哥尼斯堡七桥问题奠定图论基础以来，一直是数学、计算机科学、社会学、分子生物学等领域的核心研究工具。随着大数据时代的到来，现实世界中大量非欧几里得数据——从社交网络的用户关系、知识图谱的实体关联，到分子结构的原子连接、交通路网的路径关系——都可以抽象为图结构进行建模。传统图算法经过数十年的发展，已经在最短路径计算、社区发现、节点排序等场景中形成了成熟的方法体系，但随着应用场景的复杂度不断提升，传统方法在复杂结构建模、语义特征提取、端到端学习等方面的固有局限逐渐显现，这也直接推动了图神经网络（Graph Neural Network, GNN）的诞生与快速发展。本章将从数学层面严格定义图的核心要素，梳理图的类型分类与核心属性指标，深入分析传统图算法的核心思路与适用场景，最终明确传统方法的局限性，为后续章节讲解图神经网络的核心技术奠定基础。

1.1 图的数学定义与核心分类

1.1.1 图的严格数学定义

从数学角度，图是描述对象间关联关系的最通用抽象模型。给定有限非空节点集合$V = \{v_1, v_2, ..., v_n\}$和边集合$E = \{e_1, e_2, ..., e_m\}$，图$G$可严格定义为二元组$G = (V, E)$，其中每条边$e_{ij} = (v_i, v_j)$表示节点$v_i$与$v_j$之间存在关联关系。若边无方向性，则满足$e_{ij} = e_{ji}$，该图为无向图；若边具有指向性，则$e_{ij} \neq e_{ji}$，该图为有向图，通常用箭头标注边的指向。

边的权重$w_{ij}$用于量化关联的强度，不同场景下权重的语义不同：在交通路网中，权重可以是两个站点之间的通行时间；在社交网络中，权重可以是用户之间的互动频次；在分子结构中，权重可以是原子之间的键能。若所有权重均为1，则称为无权图，否则为有权图。

图的规模通常用节点数$n = |V|$和边数$m = |E|$衡量，图的密度定义为$\rho =

图的密度定义为$\rho = \frac{2|E|}{|V|(|V|-1)}$（无向图）或$\rho = \frac{|E|}{|V|(|V|-1)}$（有向图），用于衡量图中边的密集程度：当$\rho$接近1时称为稠密图，如分子结构中原子之间的连接通常高度密集；当$\rho$远小于1时称为稀疏图，如社交网络中用户的好友关系通常仅占所有可能关系的万分之一以下，属于典型的稀疏图。不同密度的图需要采用不同的存储和计算策略，这是图算法设计的基础前提。

除了邻接矩阵的数学表示外，图的存储还常用邻接表结构：为每个节点存储其所有邻居节点的列表，空间复杂度仅为$O(|V|+|E|)$，特别适合大规模稀疏图的存储，是目前工业界处理大规模图的主流存储方式。对于带权图，邻接表中每个邻居条目还会额外存储对应边的权重。在实际工程实践中，通常会根据图的规模选择存储方式：当节点数小于1万时优先使用邻接矩阵，方便快速进行矩阵运算；当节点数超过10万时则必须使用稀疏矩阵或邻接表存储，避免内存溢出。

1.1.2 图的核心类型分类

根据不同的划分维度，图可以分为多个核心类型，不同类型的图适配的算法和场景存在显著差异。

按边方向性分类：无向图与有向图

无向图的边没有方向性，若节点$v_i$与$v_j$之间存在边，则二者等价关联，典型的应用场景包括社交网络的好友关系、分子结构的原子键合、交通路网的 undirected 道路连接等。无向图的邻接矩阵是对称矩阵，即$A_{ij}=A_{ji}$，节点的度等于其邻居节点总数。 有向图的边具有明确的方向性，边$e_{ij}=(v_i,v_j)$表示从$v_i$指向$v_j$的关联，典型场景包括学术论文的引用网络（论文A引用论文B，则存在从A指向B的有向边）、社交网络的关注关系（用户A关注用户B，则存在从A指向B的有向边）、知识图谱的实体关系（实体“苹果”通过“生产”关系指向实体“iPhone”）等。有向图中节点的关联分为入度（In-degree，指向该节点的边数）和出度（Out-degree，该节点指向的边数），邻接矩阵为非对称矩阵。

按节点/边类型分类：同质图与异质图

同质图（Homogeneous Graph）中所有节点属于同一类型，所有边也属于同一类型，是最简单的图结构，也是传统图算法主要研究的对象，比如学术论文引用网络中所有节点都是论文，所有边都是引用关系；社交网络的好友关系中所有节点都是用户，所有边都是好友关联。 异质图（Heterogeneous Graph）中包含多种类型的节点和多种类型的边，是描述复杂现实系统的更通用模型，也被称为异质信息网络（Heterogeneous Information Network, HIN）。典型的异质图包括电商平台的用户交互网络：节点类型包括用户、商品、商家、评论、店铺，边类型包括用户-商品的购买/浏览关系、用户-商家的关注关系、商品-商家的所属关系、用户-评论的发布关系等。异质图的核心优势是可以保留现实系统的多维度语义信息，比如在电商推荐场景中，用户的购买行为和浏览行为代表了不同的兴趣强度，同质图无法区分这两种边的语义差异，而异质图可以天然建模这种多模态关联。

按时间演化分类：静态图与动态图

静态图的节点、边及其属性都不随时间发生变化，比如蛋白质的三维分子结构一旦形成就会保持稳定，属于典型的静态图；知识图谱中的实体关系在短时间内也不会发生大规模变化，也可以近似为静态图。 动态图的节点、边或属性会随时间动态演化，是当前图研究的热点方向。典型的动态图包括社交网络的关注关系（用户会随时添加或取消关注）、交通路网的流量变化（不同时段的边权重即通行时间会发生变化）、时序知识图谱（新的实体和关系会不断加入，比如新闻事件中的实体关联会随时间更新）等。动态图的核心挑战是需要建模图结构的时序演化规律，而静态图算法无法处理这种动态变化。 ```mermaid graph TD A[图] --> B[按边方向分类] A --> C[按节点/边类型分类] A --> D[按时间演化分类] B --> B1[无向图：边无方向<br/>场景：好友关系、分子结构] B --> B2[有向图：边有方向<br/>场景：引用网络、知识图谱] C --> C1[同质图：单节点/边类型<br/>场景：论文引用网络、社交好友网络] C --> C2[异质图：多节点/边类型<br/>场景：电商交互网络、知识图谱] D --> D1[静态图：结构不随时间变化<br/>场景：蛋白质结构、静态知识图谱] D --> D2[动态图：结构/属性随时间演化<br/>场景：社交关注网络、时序知识图谱] ```

1.2 图的核心属性指标

图的属性指标是对图的结构特性的量化描述，是传统图算法进行分析的核心依据，也是评估图结构特性的重要标准。核心属性指标可以分为节点级指标、图级指标两类。

1.2.1 节点级属性指标

度（Degree）

度是最基础的节点属性指标，用于衡量节点的连接规模：无向图中节点$v_i$的度$d(v_i)$等于其关联的边数，等价于邻接矩阵中第$i$行的元素和，即$d(v_i) = \sum_{j=1}^{|V|} A_{ij}$；有向图中分为入度$d_{in}(v_i) = \sum_{j=1}^{|V|} A_{ji}$和出度$d_{out}(v_i) = \sum_{j=1}^{|V|} A_{ij}$。 度的分布是衡量图整体特性的重要指标：真实世界的大规模图（如社交网络、互联网、学术引用网络）的度分布通常服从幂律分布（Power-law Distribution），即度数为$k$的节点占比$P(k) \propto k^{-\gamma}$，其中$\gamma$是幂指数，通常介于2到3之间。这类图被称为无标度网络（Scale-free Network），核心特性是少数节点拥有极高的度（被称为枢纽节点，Hub），大部分节点的度都很低。比如Twitter社交网络中，不到1%的用户拥有超过1万个粉丝，而超过80%的用户粉丝数不足100个，就是典型的幂律分布。 度中心性（Degree Centrality）是度的归一化形式，用于衡量节点在局部范围内的中心程度，计算方式为$C_D(v_i) = \frac{d(v_i)}{|V|-1}$，取值范围为0到1，值越高说明节点的局部连接能力越强。

聚类系数（Clustering Coefficient）

聚类系数用于衡量节点的邻居之间的连接紧密程度，反映图的“团簇”特性，分为局部聚类系数和全局聚类系数两种：

• 局部聚类系数$C(v_i)$衡量节点$v_i$的邻居之间互相连接的概率，对于无向图，其计算公式为：

$$C(v_i) = \frac{2e_i}{d(v_i)(d(v_i)-1)}$$ 其中$e_i$是节点$v_i$的邻居之间的边数，$d(v_i)(d(v_i)-1)/2$是节点$v_i$的邻居之间可能存在的最大边数。比如在微信社交网络中，用户A有10个好友，这10个好友之间共有8条边，则A的局部聚类系数为$2*8/(10*9) \approx 0.18$，意味着A的好友之间有18%的概率互相是好友。

• 全局聚类系数$C$是所有节点局部聚类系数的平均值，或者用图中闭合三元组的比例衡量，反映整个图的团簇紧密程度。

真实世界的大规模图通常同时具备小世界特性（Small-world Property）：即全局聚类系数远高于随机图，同时任意两个节点之间的平均最短路径长度很短（通常仅需经过3到6个中间节点），这就是广为人知的“六度分隔”理论的核心依据。1967年米尔格拉姆的经典实验中，美国任意两个陌生人之间平均仅需经过5.5个中间人就能建立联系，验证了小世界特性的普遍存在。

中心性（Centrality）

中心性是衡量节点在整个图中重要程度的综合指标，除了度中心性外，常用的中心性指标还包括：

• **接近中心性（Closeness Centrality）**：衡量节点到图中其他所有节点的平均最短路径的倒数，计算公式为$C_C(v_i) = \frac{|V|-1}{\sum_{j=1}^{|V|} d(v_i,v_j)}$，其中$d(v_i,v_j)$是节点$v_i$到$v_j$的最短路径长度。接近中心性越高的节点，信息传播到整个图的速度越快，比如疫情传播中的核心传播节点、社交网络中的信息扩散源，通常接近中心性较高。
• **中介中心性（Betweenness Centrality）**：衡量节点作为“桥梁”的重要程度，计算方式为所有节点对之间的最短路径中经过该节点的比例，计算公式为$C_B(v_i) = \sum_{s \neq v_i \neq t \in V} \frac{\sigma_{st}(v_i)}{\sigma_{st}}$，其中$\sigma_{st}$是节点$s$到$t$的最短路径总数，$\sigma_{st}(v_i)$是经过$v_i$的最短路径数量。中介中心性越高的节点，越可能是不同社区之间的连接枢纽，比如交通网络中的枢纽城市、社交网络中的跨界连接者，通常中介中心性很高。
• **特征向量中心性（Eigenvector Centrality）**：衡量节点“邻居的重要性”，核心思想是“重要的节点连接的邻居也更重要”，是PageRank算法的理论基础。其满足方程$C_E(v_i) = \frac{1}{\lambda} \sum_{j=1}^{|V|} A_{ij} C_E(v_j)$，其中$\lambda$是邻接矩阵的最大特征值，可以通过求解特征方程得到。

1.2.2 图级属性指标

平均路径长度与直径

平均路径长度（Average Path Length, APL）是图中所有节点对之间最短路径长度的平均值，是衡量图连通性的重要指标，小世界网络的APL通常仅为$O(\log |V|)$，远低于同规模的随机图。 图的直径（Diameter）是图中所有节点对之间最短路径长度的最大值，反映图的“大小”，比如学术合作网络的直径通常为6到8，意味着任意两个研究者之间最多经过6到8个合作者就能建立联系。

模块度（Modularity）

模块度是衡量社区划分质量的指标，由Newman和Girvan在2004年提出，计算公式为： $$Q = \frac{1}{2|E|} \sum_{i,j} \left( A_{ij} - \frac{d(v_i)d(v_j)}{2|E|} \right) \delta(c_i, c_j)$$ 其中$A_{ij}$是邻接矩阵的元素，$d(v_i)、d(v_j)$是节点$v_i、v_j$的度，$c_i、c_j$是节点所属的社区编号，$\delta$是克罗内克函数（当两个节点属于同一社区时为1，否则为0）。模块度的取值范围为[-0.5, 1)，值越高说明社区内部连接越紧密、社区之间连接越稀疏，社区划分的质量越好。通常模块度大于0.3说明社区划分结果具有较高的可信度。

1.3 传统图算法的核心思路与适用场景

传统图算法经过数十年的发展，已经在最短路径计算、社区发现、节点排序、图匹配等场景中形成了成熟的方法体系，本节将梳理核心算法的思路与适用场景，并结合实践案例说明其使用方法。

1.3.1 最短路径算法

最短路径算法是应用最广泛的图算法之一，核心目标是计算图中两个节点之间的最短路径（路径长度最短或权重和最小），代表算法包括Dijkstra算法、Floyd算法、Bellman-Ford算法。

Dijkstra算法

Dijkstra算法是典型的贪心算法，核心思路是每次选择当前距离起点最近的未访问节点，更新其邻居节点的最短距离，直到找到目标节点或所有节点都被

接上文未完成的Dijkstra算法介绍，首先补全该算法的完整技术细节与适用边界，再依次展开其余传统图算法的核心逻辑与实践案例，最后深入分析传统方法的固有局限，为后续图神经网络的内容铺垫。

---

Dijkstra算法是典型的贪心算法，核心思路是每次选择当前距离起点最近的未访问节点，更新其邻居节点的最短距离，直到找到目标节点或所有节点都被访问完毕。其正确性基于贪心选择性质：一旦某个节点的最短距离被确定，后续不会再有更短的路径经过未访问节点更新该距离，这一性质成立的前提是图中所有边的权重非负。以北京地铁2号线部分站点的无权图为例，从西直门到北京站的最短路径经过9个站点，Dijkstra算法可以通过优先队列优化实现$O(m + n \log n)$的时间复杂度（$n$为节点数，$m$为边数），远优于朴素实现的$O(n^2)$复杂度，是目前工业界处理非负权最短路径查询的主流算法，广泛应用于导航软件、网络路由、物流路径规划等场景。

```python <!-- 纸书注释：此处可插入北京地铁2号线站点拓扑示意图 --> import networkx as nx

构建北京地铁2号线部分站点的无权图

G = nx.Graph() stations = ["西直门", "积水潭", "鼓楼大街", "安定门", "雍和宫", "东直门", "东四十条", "朝阳门", "建国门", "北京站"] edges = [("西直门", "积水潭"), ("积水潭", "鼓楼大街"), ("鼓楼大街", "安定门"), ("安定门", "雍和宫"), ("雍和宫", "东直门"), ("东直门", "东四十条"), ("东四十条", "朝阳门"), ("朝阳门", "建国门"), ("建国门", "北京站")] G.add_nodes_from(stations) G.add_edges_from(edges)

计算西直门到北京站的最短路径

shortest_path = nx.shortest_path(G, source="西直门", target="北京站") print(f"西直门到北京站的最短路径：{shortest_path}，共经过{len(shortest_path)-1}个站点")

输出：西直门到北京站的最短路径：['西直门', '积水潭', '鼓楼大街', '安定门', '雍和宫', '东直门', '东四十条', '朝阳门', '建国门', '北京站']，共经过9个站点

```

💡 电子版侧边栏提示：在处理大规模稀疏图的最短路径查询时，优先使用优先队列优化的Dijkstra算法，时间复杂度为$O(m + n \log n)$，比邻接矩阵实现的$O(n^2)$效率高10倍以上。对于无负权边的大规模图（如交通路网、社交网络），Dijkstra算法是首选的最短路径算法。

但Dijkstra算法存在明确的适用边界：无法处理带负权边的图，因为其贪心策略假设一旦确定节点的最短距离就不会再更新，而负权边可能导致后续找到更短的路径。针对含负权边的场景，通常使用Bellman-Ford算法或Floyd-Warshall算法。

Floyd-Warshall算法是基于动态规划的多源最短路径算法，核心思路是逐步加入中间节点，逐步更新任意两点之间的最短路径，其递推公式为： $$d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right)$$ 其中$d_{ij}^{(k)}$表示只允许经过前$k$个节点作为中间节点时，节点$i$到节点$j$的最短路径长度。该算法的时间复杂度为$O(n^3)$，空间复杂度为$O(n^2)$，仅适合节点数不超过1000的小规模稠密图场景，典型应用是地图APP的离线路径预计算：提前计算全国数百个主要城市之间的所有最短路径，用户查询时直接返回预计算结果，无需实时计算，将查询延迟从数百毫秒降低到毫秒级。

Bellman-Ford算法是另一种支持负权边的单源最短路径算法，核心思路是通过松弛操作迭代更新最短距离：对所有边进行$n-1$轮松弛（每轮遍历所有边，若边$e_{ij}$满足$d(v_i) + w_{ij} < d(v_j)$则更新$d(v_j)$），第$n$轮松弛若还能更新节点距离则说明图中存在负权环。该算法的时间复杂度为$O(nm)$，虽然效率低于Dijkstra算法，但可以处理负权边场景，典型应用是金融市场的套利路径检测：若两种货币之间的兑换汇率满足“A→B→C→A的兑换收益大于1”，则对应图中存在负权环，代表无风险套利机会。2022年某量化基金就用改进的Bellman-Ford算法监测加密货币交易对的套利空间，单日套利收益超过百万美元。

1.3.2 社区发现算法

社区（Community）是图中连接紧密的子图集合，社区内部的节点之间连接密度远高于社区之间的连接密度，社区发现的核心目标是挖掘图中隐含的社区结构，是