Introduction to some representations, neighbors and degrees of Graphs

Preface

Recently, we need to learn graph neural network , The ultimate goal is to use R-GAT, But it can't be achieved overnight , It should not be difficult to copy the code and run it , But if you can understand the code , Modify the code , You may still need to understand the corresponding model theory . Let's start with the representation of the graph …
The picture below is b From the station video , Because it is really clear from the picture
https://www.bilibili.com/video/BV1U44y1K7yP?p=2&vd_source=f57738ab6bbbbd5fe07aae2e1fa1280f

The representation of the figure

adjacency matrix

Adjacency matrix is a basic graphical representation . Suppose the number of nodes in a graph is N, Then generate a N*N Matrix . The value in the matrix is the relationship between the nodes in the corresponding position, which is generally used as A Express .

If the node i And nodes j Right link , Then the corresponding position of the adjacency matrix is assigned 1 that will do

Undirected graph （ There is no direction on the side , That is, do not distinguish 1->2 and 2->1）：

Directed graph ：

Weighted digraph ：
The values in the matrix can be expressed by weight

Adjacency list method

Adjacency lists are very friendly to sparse large graphs

There is no direction, no right ：

A directed power chart ：

Edge set method

The tuple of the head and tail nodes to represent a set of edges

Directed graph ：

Undirected graph ：

A directed power chart ：

Neighbor sum degree

The neighbor of a node refers to the node on the same side and at the other end of the node .
The degree of a node refers to the number of its neighbors

Undirected graph ：

Directed graph ：

The neighbors of a directed graph are divided into the former and the latter , Degrees can be divided into in degrees and out degrees .
A former stepneighbor ： The head node to which the target node is connected when it is the tail node .
Successor neighbor ： When the target node is the head node , The tail node connected to it .
Read in ： Number of previous neighbors
The degree of ： Number of subsequent neighbors