- 深入浅出图神经网络:GNN原理解析
- 刘忠雨 李彦霖 周洋
- 496字
- 2025-02-24 15:59:52
1.1.1 图的基本类型
1.有向图和无向图
如果图中的边存在方向性,则称这样的边为有向边eij=<vi,vj>,其中vi是这条有向边的起点,vj是这条有向边的终点,包含有向边的图称为有向图,如图1-2所示。与有向图相对应的是无向图,无向图中的边都是无向边,我们可以认为无向边是对称的,同时包含两个方向:eij=<vi,vj>=<vj,vi>=eji。

图1-2 有向图
2.非加权图与加权图
如果图里的每条边都有一个实数与之对应,我们称这样的图为加权图,如图1-3所示,该实数称为对应边上的权重。在实际场景中,权重可以代表两地之间的路程或运输成本。一般情况下,我们习惯把权重抽象成两个顶点之间的连接强度。与之相反的是非加权图,我们可以认为非加权图各边上的权重是一样的。

图1-3 加权图
3.连通图与非连通图
如果图中存在孤立的顶点,没有任何边与之相连,这样的图被称为非连通图,如图1-4所示。相反,不存在孤立顶点的图称为连通图。
4.二部图
二部图是一类特殊的图。我们将G中的顶点集合V拆分成两个子集A和B,如果对于图中的任意一条边eij均有vi∈A,vj∈B或者vi∈B,vj∈A,则称图G为二部图,如图1-5所示。二部图是一种十分常见的图数据对象,描述了两类对象之间的交互关系,比如:用户与商品、作者与论文。

图1-4 非连通图

图1-5 二部图