是来自b站up主同济子豪兄的中文精讲,自己做来总结给自己学习滴,如果感兴趣的话可以去b站搜索或者去子豪兄的github图神经进行学习:
https://github.com/TommyZihao/zihao_course/blob/main/CS224W/1-Intro.md
Introduction | Machine Learning for Graph
1、图的基本表示
2、图的本体设计
3、图的种类(有向、无向、异质、二分、连接带权重)
4、节点连接数
5、图的基本表示 -邻接矩阵
6、图的基本表示-连接列表和邻接列表
7、图的连通性
1、图的基本表示
图是有节点(nodes or vertices)和连接(links or edges)组成
生活中的很多关系(relationship)都可以用图来表示
2、本体图(Ontology) :
节点的类型以及节点之间可能存在的连接(关系)
How to build a graph:
What are nodes?
What are edges?
关键是如何确定节点和边,你想要解决什么问题
Choice of the proper network representation of a given doman/problem determines our ability to use networks successfully:
In some cases, there is a unique, unambiguous representation
(有些时候,本体图是唯一的、无歧义的)
In other cases,the representation is by no means unique
The way you assign links will determine the nature of the question you can study.
Instance: 红楼梦知识图谱
(https://grapheco.org/InteractiveGraph/dist/examples/example1.html )
3、图的种类
异质图(heterogeneous graph) :
Nodes with node types (结点种类可以不同)
Edges with relation types
Node type
Relation type
两类结点之间的关系抽象成二分图
可以展开二分图(根据关系连接)
如 U中 1、2、3都连到A,把他们连在一起
4、节点连接数(Node degree)
Node degree 来表示结点重要度、中心度、枢纽度
Source 、Sink
in-degree(入度)、out-degree(出度)
5、图的基本表示-邻接矩阵(Adjacency Matrix)
结点的度怎么计算(degree)
为什么要把图表示成矩阵的形式?
邻接矩阵保留了图的全部信息,是全息的;计算机、算法都是通过矩阵的运算
(图翻译为计算机的语言)
drawback: sparse matrix
可以看到用邻接矩阵很浪费空间,所以一般用连接列表和邻接列表
6、图的基本表示-连接列表和邻接列表
Multigraph:
结点与结点之间存在多种关系(能吃、不能吃、推荐吃)
7、图的连通性
undirected graph:
总有一条路能让图的任意两个结点之间触达,称之为”虽远必诛“ (connected components)
connected components: Any two vertices can be jointed by a path.
A disconnected graph is made up by two or more connected components(连通域).
最大的连通域(Giant Component)
instance:
directed graph:
有向图中,任意两个节点可以相处触达:
Strongly connected directed graph(强连通图)
has a path from each node to every other node and vice versa (e.g., A-B path and B-A path)
Weakly connected directed graph(弱连通图)
is connected if we disregrad the edge directions
instance:
subset is strong directed graph can be named strongly connected components(SCCs)
Summary