Graph--概念及应用

2023-05-11 本文已影响0人倪桦

1、图 (graph) 概念

图（Graph）是由节点（Node）和边（Edge）组成的一种数据结构，用于描述事物之间的关系。在图中，节点表示事物，边表示事物之间的关系。图可以用来描述各种复杂的关系网络，例如社交网络、交通网络、生物网络等。

在图中，节点可以表示各种实体，例如人、物、地点、基因等。边可以表示各种关系，例如人与人之间的社交关系、物品之间的相似性关系、地点之间的距离关系、基因之间的相互作用关系等。图可以用来描述各种不同类型的关系网络，从而帮助我们更好地理解事物之间的联系和相互作用。图可以分为有向图和无向图两种类型。在有向图中，边有方向，表示从一个节点到另一个节点的单向关系；在无向图中，边没有方向，表示两个节点之间的双向关系。此外，图还可以包含权重，用于表示边的强度或者权重。

图是计算机科学中的重要概念，被广泛应用于各种领域，例如社交网络分析、生物信息学、交通网络规划等。

2、图的基本表示

图的基本构成 ：节点(nodes, vertices, $N$ )，连接(links,edges, $E$ )，从而图可以被系统描述 $G(N,E)$ .
图的本体（Ontology）: 图的本体是对知识图谱的正式描述，用以描述一个领域内的一组概念以及它们之间的关系。要构建一个图，需要清楚图的本体，哪些信息可以被描述为节点对象，哪些关系用以描述对象连接。

2.2 图的分类:

根据连接关系的指向性有无分成 无向图，有向图

如果一张图里存在不同类型的节点或连接，则形成 异质图(heterogeneous graph) ， $G(V,E,R,T)$
这种图结构复杂性较高，是目前大部分图神经网络论文的主要关注对象。

Nodes with node types $v_i \in V$
Edges with relation types $(v_i,r,v_j) \in E$
Node type $T(v_i)$
Relation type $r \in R$

基于边的连接是否带权重，可以分为连接带权重的图

2.3 节点度(degree)

在一个网络中，如果一个节点与其它节点广泛连接（连接的边很多），意味着它在该图所表示的关系中起着非常重要的作用，所以 node degree 可以简单的反映出一个节点的重要度(中心度，枢纽度)。类比社交网络中，当一个人认识的人越多，那么他就是社交中枢。

3、图的矩阵表示--邻接矩阵

描述图结构的矩阵称为 邻接矩阵( $Adjacency \ Matrix$ )，用以描述图中任意两个节点的邻接关系。

对于无向图，节点的间的连接是互为指向的关系，所以图矩阵为对称阵，如果节点不存在指向自己的连接，则矩阵的对角线为0；图的总连接数为 $L = \frac {1}{2}{sum(X)}$
对于有向图，矩阵的行方向为 source，列方向为 target 的格式，非对称阵；对有向图矩阵，对某列求和可得节点 $k_j$ 总入度( $k_j^{(in)}$ )，对某行求和可得节点 $k_i$ 总出度( $k_i^{(out)}$ )，图的总连接数为 $L = \sum_{i=1}^N{k_i^{(in)}} = \sum_{j=1}^N{k_j^{(out)}} = sum(X)$

3.2 图的连接列表和邻接列表

由于现实中大部分关系图都是稀疏的( $k << N-1$ )，每个节点邻接的其它节点不会太多，所以邻接矩阵也是个非常稀疏的矩阵，直接用稠密矩阵表示图关系将非常耗费计算资源。所以扩展出来图的 连接列表 和邻接列表 表示方式。

连接列表(list of edges) 相比起邻接矩阵，只记录存在连接的节点对，一个三元组表("source,target,weight,label,...")；
邻接列表(Adjacency list) 相比起 连接列表 进一步压缩了信息，图中有 $N$ 个节点，只需要创建 $N$ 个 $elements$ 来表示。

Graphs in Python - Theory and Implementation - Representing Graphs in Code (stackabuse.com)

2、图的应用

最短路径搜索(地图导航)
节点重要度分析，搜索重要节点(度中心性评价)
社群检测(community detection)，如 Louvain 社群检测算法（节点聚类）
连接预测(Link Prediction)
节点相似性分析，分析图即使连接遥远，但是在属性特征等方面相似的节点
Embeddings，将一个节点映射成 d维向量，该嵌入向量表征了节点在图中的语义和连接关系，以用作下游分析。
...