图的基本表示【斯坦福CS224W图机器学习】
Task2-1 图的基本表示
自带了关联结构
图嵌入 用d维向量表示图的结点及关联信息
图的本体设计 ontology
图的种类
- Undirected
- Dorected
- heterogeneous(异质图)
- G = （V,E,R,T） 节点种类不止一种
- Biparttite Graph（二分图）
- 用 u和v表示两类节点
- 二分图的展开
节点连接数
节点连接数很多，可以反应节点的重要度
图的基本表示-邻接矩阵
！无向图邻接矩阵为对称阵，有向图不是
- 节点度的计算
！存在自己到自己的连接，对角线元素为1
！绝大多数矩阵时稀疏的 sparse,用邻接矩阵占用内存
图的基本表示-连接列表和邻接列表
- 连接列表
- 邻接列表：记录每个元素及指出的元素
- 例子
- 带权重和不带权重的图
- 自己指向自己连接
图的连通性
Connected graph
!disconneted图的邻接矩阵呈现分块对角形式，若几个connected components中有节点连接起来，会打破分块对角形式
- 有向图中，若任意两节点可相互触达，称为强连通图，若忽略方向后连通，称为weakly connected
- 强连通域 SCCs
- SCC的分解
