【从零开始】CS224W-图机器学习-2021冬季学习笔记1:Introduction; Machine Learning for Graphs

发布于:2023-01-26 ⋅ 阅读:(14) ⋅ 点赞:(0) ⋅ 评论:(0)

课程主页:CS224W | Home
课程视频链接:【双语字幕】斯坦福CS224W《图机器学习》课程(2021) by Jure Leskovec

目  录

0 前言

1 为什么要研究网络?

1.1 网络和图的区别

1.2 网络分析的研究方向​编辑

2 网络和图的基础知识

2.1 图的定义

2.2 图的类型

2.3 图的数据表现形式

2.4 图的连通性

2.4.1 对于无向图

2.4.2 对于有向图

3 参考文章


0 前言

本篇是CS224W-图机器学习笔记的第一篇,主要梳理一些图相关的基本概念。

1 为什么要研究网络?

1.1 网络和图的区别

  • Network:表示现实世界的系统。如:互联网、社交网络等。对应描述:网络, 点, 边。
  • Graph:是 Network 的数学表示。如:社交图、知识图谱等。对应描述:图, 点, 边。
  • 注:两者并不做太严格的区分。

1.2 网络分析的研究方向

  • 预测节点的类型——节点分类
  • 预测两个节点之间是否有连接——链接预测
  • 辨别一群节点之间是否是密集连接——社团发现、节点聚类
  • 测量和量化不同 节点/图 之间的相似性——网络相似度

2 网络和图的基础知识

2.1 图的定义

网络的结构有三类重要的元素:

  • Objects(对象):Nodes(节点)、顶点(Vertices),用N来表示。
  • Interactions(相互作用): links(链接), edges(边),用 E来表示。
  • System(系统) : network(网络), graph(图),用G(N,E)来表示。

2.2 图的类型

  • 有向图和无向图、加权图和非加权图、连通图和非连通图:《离散数学》图论中具体介绍,此处不再介绍。
  • 完全图:任意不同的节点之间都有一条边相连。
  • 自环图:自己与自己相连。邻接矩阵的对角线不为0。
  • 多重图 :存在两点之间大于一条边。
  • 二分图:图G中的所有节点被分成两个不相交的节点集合U和V。在这种图中,每条边都是从U内的节点连接到V内的节点,而集合内部不存在边相连。如:作者和论文构成的图,电影和演员构成的图以及用户和商品之间构成的图等等。

注:二分图的折叠(folded) :若一个集合中的某些节点有连接到另一个集合的同一个节点,则认为他们之间存在一定的关系。

2.3 图的数据表现形式

  • 邻接矩阵(Adjacency matrix)
  • 邻接列表(Adjacency list)

注:Adjacency matrix往往是稀疏(sparse,有很多0)的,因此在实际应用中,Adjacency list比较常用,只需要用列表存储临近节点。但是,在理论分析中,我们往往使用Adjacency matrix。

2.4 图的连通性

2.4.1 对于无向图

  • 连通图:任意两节点间存在直接或间接的链路关系。

2.4.2 对于有向图

  • 强连通有向图:图的任意两个节点间存在路径,相互可以遍历到达。
  • 弱连通有向图:忽略方向时才连通的图。
  • 强连通分量(Strongly connected components (SCCs)):子图任意两个节点间存在路径,相互可以遍历到达。

3 参考文章

cs224w 图神经网络 学习笔记(一)Introduction_喵木木的博客-CSDN博客

CS224W-图神经网络 笔记1:Introduction : Structure of Graphs_Johnny__Wang__的博客-CSDN博客