当前位置：首页 > news >正文

同济子豪兄--图的基本表示【斯坦福CS224W图机器学习】

news 2024/10/22 17:31:46

无向图（Undirected Graph）：
- 在无向图中，边没有方向，即如果顶点A和顶点B之间有一条边，那么这条边既表示A到B的关系，也表示B到A的关系。换句话说，边是双向的。
- 无向图的边通常用一条线段表示，两端不区分方向。
- 无向图中的路径和回路的概念是对称的，即从A到B的路径与从B到A的路径是相同的。
有向图（Directed Graph）或有向图（Digraph）：
- 有向图中的边有方向，即从一个顶点指向另一个顶点。如果顶点A到顶点B有一条有向边，那么这条边表示从A到B的单向关系，与从B到A的关系是不同的。
- 有向图的边通常用箭头表示，箭头的方向指示边的方向。
- 在有向图中，路径的概念是方向敏感的，即从A到B的路径与从B到A的路径是不同的。
异质图（Heterogeneous Graph）或多重图（Multigraph）：
- 异质图是一种通用的图模型，它允许图中存在不同类型的顶点和边，以及同一对顶点之间可以有多条边（多条边就是多条不同类型的边）。
- 在异质图中，顶点可以有不同的属性或类型，边也可以有不同的类型或属性，这使得异质图能够表示更复杂的关系和结构。
- 异质图可以用于表示多种实体和关系，例如社交网络中的用户和用户之间的关系，以及用户和内容之间的关系等。

异质图：节点会是不同的类型、边也是不同的类型比如视频中讲的红楼梦和医疗知识图片图谱的例子就是异质图。同时若节点的种类是2个的话则称为二分图。

展开二分图：

根据中间的U、V关系展开如图ProjectionU和ProjectionV。解释：1和2都和A有联系则在U图中1和2连接一条边，同理3和2都和A有联系则在U图中3和2连接一条边，其他以此类推构成图U（图V同理）。

节点连接数：

出度（Out-degree）：
- 出度是指从一个顶点出发的边的数量。换句话说，它是指向其他顶点的边的数量。
- 如果一个顶点A有3条边指向其他顶点，那么顶点A的出度就是3。
入度（In-degree）：
- 入度是指指向一个顶点的边的数量。也就是说，它是从其他顶点指向该顶点的边的数量。
- 如果有3条边从不同的顶点指向顶点B，那么顶点B的入度就是3。

应用：可以直接用Node Degress直接表示节点的重要程度。

邻接矩阵：图论中用来表示图的一种矩阵形式，特别适用于表示有向图和无向图的顶点间连接关系。邻接矩阵是一个方阵，其行和列分别代表图中的顶点，矩阵中的元素表示顶点之间的边。

无向图的邻接矩阵：对于无向图，邻接矩阵是一个对称矩阵。如果顶点 ii 和顶点 jj 之间有一条边，则邻接矩阵中第 ii 行第 jj 列和第 jj 行第 ii 列的元素为1（或边的权重，如果是加权图），否则为0。

无向图的邻接矩阵：对于有向图，邻接矩阵不一定是对称的。如果从顶点 ii 到顶点 jj 有一条有向边，则邻接矩阵中第 ii 行第 jj 列的元素为1（或边的权重，如果是加权图），否则为0。

连接列表

邻接列表

连通域：

强连通域：

在有向图中，强连通域是指图中的一个最大的子图，在这个子图中，任意两个顶点都是相互强连通的。这意味着对于子图中的任意两个顶点 uu 和 vv，都存在从 uu 到 vv 的有向路径，同时也存在从 vv 到 uu 的有向路径。
一个有向图可以被分割成若干个强连通域。每个强连通域内部是强连通的，但不同强连通域之间可能没有直接的边相连。
强连通域的概念在分析有向图的结构时非常重要，例如在社交网络分析、网页排名算法等领域。

弱连通域：

在有向图中，弱连通域是指图中的一个最大的子图，在这个子图中，如果忽略边的方向，任意两个顶点都是相互连通的。也就是说，如果我们将有向图转换为无向图，那么弱连通域就是这个无向图中的连通域。
弱连通域的概念比强连通域要弱，因为它只要求在忽略边的方向后，顶点之间是连通的。
一个有向图可以被分割成若干个弱连通域。每个弱连通域内部在忽略方向后是连通的，但不同弱连通域之间没有直接的边相连。