首页 > 其他分享 >cs224w(图机器学习)学习笔记1.3choice of graph representation

cs224w(图机器学习)学习笔记1.3choice of graph representation

时间:2022-11-27 21:23:41浏览次数:52  
标签:有向图 1.3 graph 邻接矩阵 节点 学习 cs224w 连接

@

目录

1.图的概念

  1. 图的组成部分
    在这里插入图片描述
  2. 图的意义
    作为一种解决问题的通用语言,将问题抽象成图,用同一种机器学习的算法可以求解多个问题。
    但为问题选择合适的表示是很难的问题——选择合适的点、边和问题域

2.design choice

  1. 有向图和无向图directed/undirected graphs
    在这里插入图片描述
  2. 节点度node degrees
    在这里插入图片描述
    1. 无向图的每个节点都被计算两次,平均节点度*2
    2. 自循环的无向图,增加一个节点会增加两个节点度
    3. 有向图分为入度in-degree和出度out-degree
    4. 如节点B,在无向图中节点度为2,在有向图中节点度为3
  3. 二部图bipartite graph
    在这里插入图片描述
    1. 通常有两种不同类型的节点,其中,A类型的节点只与B类型的节点进行交互且图的边仅从左侧开始
    2. 折叠网络即是里面一种节点类型所建的单独的网络
    3. 基于此,还可以类推出多部图multipartite

在这里插入图片描述
如上图,是作者U和文章V的图,当作者1,2,3一起写了文章A,那作者图里1,2,3即存在连边。所以,当我们有了二分图,可以将其投影到左侧或右侧。

3.图的表示representing graphs

  1. 使用邻接矩阵adjacency matrix
    无向图和有向图的邻接矩阵
    采用0-1两种选择,当两个节点间有边时,权重为1,否则权重为0.
    在这里插入图片描述
    无向图和有向图邻接矩阵在路径上的区别。
    在这里插入图片描述
    大多数的网络是稀疏的sparse,如:电网power-girds、互联网连接internet connection等
  2. 使用边列表egde list——在深度学习中很受欢迎
    edge list
    将两个节点之间的连接表示为二维矩阵two-dimensional matrix,常用于深度学习框架中,问题在于很难进行图的操作和分析,就算只是计算图中点的度数都会很难
  3. 使用邻接表adjacency list——便于进行图分析和处理graph analysis and mainpulation
    adjacency list
    1. 适用于大型和稀疏矩阵
    2. 能够快读检索给定节点的所有邻边

4.图的附加属性property/attributes

在这里插入图片描述

  1. 节点的重量——可以用邻接矩阵表示
    在这里插入图片描述
    节点的重量可以表示两个节点连接的强度
  2. 自环和多图
    具有自环的节点:如节点4的度为3
    多图:一对节点间可以有多条边
    在这里插入图片描述
  3. 图的连通性connectivity of undirected graphs
    1. 无向图的连通性
      在这里插入图片描述
      在这里插入图片描述
      当图没有连通时,邻接矩阵可以被分成几个对角块,所以在聚类系数里面只要弄清有几个对角块就可以知道有几类。
    2. 有向图的连通性
      在这里插入图片描述
      分为强连接和弱连接,强连接中的每对节点都相连,而弱连接则不是。
      在这里插入图片描述

标签:有向图,1.3,graph,邻接矩阵,节点,学习,cs224w,连接
From: https://www.cnblogs.com/churcee/p/16930703.html

相关文章