图神经网络系列- 斯坦福CS224W《图机器学习》-学习笔记1
图神经网络系列- 斯坦福CS224W《图机器学习》-学习笔记1
复杂数据可以以结构化形式呈现为对象之间的关系图。图网络被视为构建社会、技术和生物系统模型的核心工具。CS224W课程着重分析大规模图数据所涉及的计算挑战、算法优化以及建模难点。通过深入探索图的结构特征及其内在属性，学生们被引入机器学习方法和数据挖掘技术，以期全面理解各种网络的运行机制和潜在规律。课程涵盖的主要主题包括表示学习与图神经网络、万维网算法、知识图推理以及社会网络分析。
目录
教师团队
图的构成要素
有向图与无向图的定义
节点的度数计算方法
完全图的特性分析
二分图的性质探讨
二分图投影的应用实例
邻接矩阵的表示方法
边列表的组织方式
邻接列表的结构特点
无权图与有权图的分类
自环边图的定义及其意义
多路径图的结构分析
图的连通性分析
强连通图与弱连通图的比较
教师团队
图的基本结构
对象：节点，顶点—— N
互动：链接，边—— E
系统：网络图—— G(N, E)
有向图及无向图
在图论中，有向图结构由顶点集合V和有向边集合E构成，其中每条边都具有方向性。
节点的度
无向图：
节点的度数：与节点i相连的边的数量。其中，KA=4，表示节点A连接了4条边。
平均度：图中所有节点度数之和与节点数量的比值。无向图的平均度为2E/N（边数的两倍除以节点数量）。
有向图的结构如下：
入度定义为指向节点node的边的数量，出度则表示从节点出发的边的数量。总度是入度与出度之和。
在此示例中，节点KC的入度为2，出度为1，因此总度为3。
有向图的平均度数计算公式为E/N，其中E代表边的数量，N代表节点的数量。
完全图
在N个节点中选择两个不同节点进行连接，最大边数为N（N-1）/2。完全无向图的平均度等于2E除以N，而2E等于N（N-1），因此平均度为N-1。
二分图
二分图是节点被划分为两个互不相交的集合U和V，每条边都连接一个U节点到一个V节点；U和V是互不相交的集合。
二分图投影
从U的角度，U集合的投影：
在图U中，节点1、2、3均连接至V中的A节点，由此，投影后的节点1、2、3之间也会形成连接关系。节点2和5在图U中均连接至V中的B节点，由此，投影后的节点2和5之间也会产生连接。在图U中，节点4和5均连接至V中的C节点，由此，投影后的节点4和5之间也会形成连接。节点5、6、7在图U中均连接至V中的D节点，由此，投影后的节点5、6、7之间也会产生连接。
从V的角度，V集合的投影：
在V中，节点A和节点B分别与U中的2个节点关联，因此它们在映射到U后会相互关联。在V中，节点B、节点C和节点D分别与U中的5个节点关联，因此它们在映射到U后会相互关联。
邻接矩阵（Adjacency matrix）
A ij =1 表示 有边连接 节点i 到节点j
A ij =0 表示 节点i 到节点j 没有边连接
无向图的邻接矩阵具有对称性。无向图的邻接矩阵不具有对称性。通过统计对应行或列的和，可以计算出该节点的度。
边列表（Edge List）
记录每一条边的起点和边的终点
邻接列表（Adjacency List）
从邻接矩阵获取，每一行节点中有边连接的对应节点
图可以使用邻接矩阵或邻接链表来表示。
- 当图的密度较高或规模较小时，可以通过邻接矩阵的方式来表示，实现相对简便的处理。
- 对于稀疏图而言，由于邻接矩阵中存在大量0元素，使用其进行表示会导致空间浪费，因此通常采用邻接链表作为替代方案。
现实世界中的图是极度稀疏的
无权重图、有权重图
无权重图的每条边用1表示，有权重图中的每一条边的权重不同
自环边图 多路径图
在邻接矩阵A中，第1个节点和第4个节点的位置被标记为1，具体对应于矩阵中的(1,1)和(4,4)位置。
连通性
非连通图的邻接矩阵具有区块对角化矩阵的结构。在该网络中，节点2与节点4之间的边被识别为桥边，它将两个子图连接在一起。
强连通 弱连通
强连通关系指的是图中任意两个节点之间都存在一条路径。弱连通关系表示图中某些节点之间不存在路径，例如F节点至G节点之间没有路径。
