1.1.1　图的定义和属性

在本小节中, 我们主要关注无权图, 并介绍相关重要定义。

定义 1.1　图　图可以表示为 ,其中 表示节点集合, 表示边集合。连接节点 和 的边可以表示为 。

以社交图为例, 节点表示人, 边表示社交关系, 如朋友、同学、师生关系或者家长-子女关系; 在推荐图中, 节点表示人或商品, 边表示购买行为; 在化学中, 化合物可以表示为以原子作为节点、以化学键作为边的图。如果节点 和 之间存在一条边,则节点 与 相邻。图 可以等价表示为描述节点连通性的邻接矩阵。

定义 1.2　邻接矩阵　给定一个图 ,我们可以使用邻接矩阵 表示边的分布。该邻接矩阵的第 个元素 ,表示节点 和 之间的连通性。 表示存在边, 表示没有边存在。

特别地, 在有向图中, 边从一个节点指向另一个节点; 而在无向图中, 两个节点的则序没有区别,即两个节点的顺序不影响它们之间的边。在无向图中,当且仅当节点 与 相连时,节点 与 相连,即对于图中的所有节点 和 。因此,无向图的邻接矩阵是对称的。请注意, 除非特别说明, 否则这里我们的讨论仅针对无向图。通过邻接矩阵, 我们可以轻松计算节点与其他节点相邻的次数, 即节点的度。

定义 1.3　邻居节点　图 中节点 的邻居节点集合表示为 ,其中包含所有与 相连的节点。

定义 1.4　度　节点 的度为 。节点 的度等于邻居节点集合 的大小,即 。对角线度矩阵可以表示为 。

以一个包含 5 个节点和 7 条边的图为例,如图 1.1 (a) 所示,节点集合表示为 ,边集合表示为 。这个图的邻接矩阵可以表示为图 1.1 (b) 中的 ,节点 的一阶邻居是节点集合 ,节点 的度为 3 。这个图的度矩阵可以表示为图 1.1 (c) 中的 。

图1.1　图及其矩阵表示

在许多实际应用中, 节点通常会关联一些特征或属性。这种数据可以看作图信号, 它同时捕捉了节点间的结构信息和节点的属性。图信号的目标是将节点特征（通过图域中定义的映射函数 ) 映射到实数值上。映射函数可以形式化地表示为 ,其中是与每个节点关联的值（向量）的维数。

此外, 谱图理论通过分析一个图的拉普拉斯矩阵的特征值和特征向量来研究该图的性质。接下来, 我们将定义一个图的拉普拉斯矩阵并讨论其关键属性。拉普拉斯矩阵的另一个定义是其归一化版本。由于度矩阵 和邻接矩阵 都是对称的,因此拉普拉斯矩阵也是对称的。

定义 1.5　拉普拉斯矩阵　对于具有邻接矩阵 的图 ,其拉普拉斯矩阵定义为 ,其中 为对角线度矩阵。

定义 1.6　归一化拉普拉斯矩阵　对于给定的以 为邻接矩阵的图 ,其归一化普拉斯矩阵 定义为

　　(1.1)