图与网络：图论视角下的知识

第 5 章 · 知识图谱

知识图谱里的「图」不是比喻——在数学上它就是图论里的图。 一堆节点、用边连起来；边可以有向、可以带标签；节点有度，节点之间可以形成路径和连通分量。用图论的语言重新看「实体与关系」，既能严格定义「多跳」「邻居」「距离」，也能说清哪些图算法（最短路径、中心性、社区发现）在知识图谱里有用、用在哪。本章把图的基本概念、知识图谱作为「有向标注图」的对应关系、以及度/路径/连通分量与常见图算法在 KG 中的位置讲清楚。

一、图的基本概念：节点与边

在图论中，图（Graph）由两部分组成：顶点/节点（Vertex / Node）的集合 V，和边（Edge）的集合 E。每条边连接两个节点（在无向图中不分先后，在有向图中区分起点和终点）。知识图谱里，节点对应实体，边对应关系；一条边从主体实体指向客体实体，所以知识图谱天然是有向图。

若允许两个节点之间有多条同类型或不同类型的边，则称为多重图；若每条边只出现一次、且不考虑自环，则是简单图的推广。知识图谱通常允许多重边（例如 A 和 B 之间既有「合作」又有「师生」），有时也允许自环（实体与自身的关系，如「等同于」）。

有向图（Directed）

边有方向：A→B 与 B→A 是两条不同的边。知识图谱的关系「谁→谁」必须区分方向。

无向图（Undirected）

边无方向：A–B 表示双向。社交网络中的「认识」常视为无向；KG 中若关系对称可建两条反向边。

有向图与无向图：知识图谱通常采用有向图

左：有向图（箭头表示方向）；右：无向图（无箭头）

二、标签与权重：从「裸图」到「标注图」

若只考虑节点和边是否存在，得到的是「裸图」。知识图谱中，节点和边都带有标签：节点标签通常表示实体类型（人、地点、组织等），边标签表示关系类型（创立、位于、任教等）。这样的图称为有向标注图（Directed Labeled Graph）或属性图的一种抽象——节点和边上都可以挂键值对，图论里则常用「标签」概括。

边上还可以有权重（Weight），表示关系的强度、置信度或代价；查询「最短路径」时若按边权求和，就得到带权最短路径。在知识图谱中，权重常用于表示抽取置信度、或业务上的关联强度。

知识图谱 = 有向标注图：节点带类型标签，边带关系类型标签

三、知识图谱作为有向标注图

把前面几章的概念与图论对齐：知识图谱 = 有向图 + 节点标签（实体类型）+ 边标签（关系类型）。可选地，边上还有权重。形式化地说，可以写成 G = (V, E, L_V, L_E)，其中 V 是节点集，E 是有向边集，L_V 为节点上的标签函数，L_E 为边上的标签函数。三元组 (S, P, O) 对应一条从节点 S 到节点 O、标签为 P 的边。

这一对应带来的好处是：图论中所有关于「图」的定义与算法都可以在知识图谱上讨论——只要注意我们的图是有向的、带标签的、可能带权的。无向图上的概念（如连通分量）在有向图中会细分为「弱连通」「强连通」等，下一节会简要区分。

四、度、路径与连通分量

度（Degree）描述节点与多少条边相连。在有向图中区分入度（In-degree）——指向该节点的边数，和出度（Out-degree）——从该节点出发的边数。例如「爱因斯坦」节点：入度可能为 0（没有「谁→爱因斯坦」的关系被记录），出度可能为多条（创立、任教、获奖等）。度很大的节点往往是图中的「枢纽」，在中心性分析与推荐中常被重点关注。

路径（Path）是节点与边交替出现的序列，且相邻的边在节点处首尾相接。若路径上节点不重复，称为简单路径；若起点与终点相同且长度≥1，称为环（Cycle）。路径的长度可以是边数（跳数），也可以是边权之和（带权路径长）。「从 A 到 B 的最短路径」即边数或权值之和最小的路径，是图上查询与推理的常见需求。

连通分量：在无向图中，若任意两节点之间都存在路径，则图是连通的；否则可划分为多个连通分量（极大连通子图）。在有向图中，若忽略边的方向后连通，称为弱连通；若沿有向边能从任意点到达任意点，称为强连通。知识图谱通常不是强连通的（例如很多「叶子」实体只有入边没有出边），但常由少数大连通分量加大量小分量组成；社区发现与子图分析会用到这些概念。

度（入度/出度）、路径与环、连通分量示意

度（Degree）有向图中分入度（指向该节点）与出度（从该节点出发）；度大往往为枢纽节点。

路径（Path）节点与边交替的序列；简单路径不重复经过节点；环为起点=终点的路径。

连通分量无向图：极大连通子图；有向图：弱连通（忽略方向）或强连通（沿有向边互通）。

度、路径、连通分量要点

五、图算法在知识图谱中的位置

图论与图数据库提供了丰富的图算法，在知识图谱的存储、查询与挖掘中各有用途。

遍历（BFS/DFS）从某节点出发，按广度或深度访问邻居，是「多跳扩展」「子图抽取」的基础；SPARQL 与 Cypher 的图模式匹配底层也依赖遍历。
最短路径两节点间边数最少或权值之和最小的路径；用于「最少几跳能关联」「关系最近」等查询与推荐。
中心性（Centrality）度中心性、介数中心性、PageRank 等，用于识别「重要节点」——关键人物、核心概念、枢纽实体，支撑排序与推荐。
社区发现将节点划分为内部连接紧密、之间连接稀疏的簇，用于团伙发现、主题聚类、子图谱划分。
路径与模式匹配查找满足「从 A 经某类边到 B 再经某类边到 C」等模式的子图，对应 SPARQL/Cypher 中的路径查询与推理规则。

常见图算法在知识图谱中的应用层次

一句话： 知识图谱在图论上对应有向标注图：节点=实体（可带类型标签），边=关系（带类型，可选权重）。度分入度/出度；路径与环由边与节点序列定义；连通分量分无向连通与有向弱/强连通。图算法（遍历、最短路径、中心性、社区发现、模式匹配）在 KG 的查询、推荐与挖掘中广泛使用。

延伸： 若你用过图数据库（如 Neo4j），其文档中的「图数据科学」库（GDS）就封装了最短路径、PageRank、社区发现等算法；在 RDF 栈中，SPARQL 的属性路径与图模式也对应特定的遍历与匹配语义。下一章讲 RDF 数据模型时，会把这些概念与三元组存储对齐。

六、小结

图由节点集与边集组成；知识图谱是有向图，边带标签（关系类型），节点可带类型标签，即有向标注图。度分入度与出度；路径为节点–边交替序列，环为起点与终点相同的路径；连通分量在无向/有向图中有不同定义。图算法（遍历、最短路径、中心性、社区发现、模式匹配）支撑 KG 的查询、排序、推荐与挖掘。下一章进入RDF 与三元组数据模型，把「有向标注图」在 W3C 标准下的具体表示（IRI、字面量、序列化）讲清楚。