Graph--概念及应用

1、图 (graph) 概念

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

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

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

2、图的基本表示

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

2.2 图的分类:

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

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

Nodes with node types
Edges with relation types
Node type
Relation type

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

  
  

2.3 节点度(degree)

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

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

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

• 对于无向图，节点的间的连接是互为指向的关系，所以图矩阵为对称阵，如果节点不存在指向自己的连接，则矩阵的对角线为0；图的总连接数为
• 对于有向图，矩阵的行方向为 source，列方向为 target 的格式，非对称阵；对有向图矩阵，对某列求和可得节点 总入度()，对某行求和可得节点 总出度()，图的总连接数为

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

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

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

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

2、图的应用

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