1.1 关于图的基本概念¶
图是用以表示实体及其关系的结构，记为 \(G=(V, E)\) 。图由两个集合组成，一是节点的集合 \(V\) ，一个是边的集合 \(E\) 。 在边集 \(E\) 中，一条边 \((u, v)\) 连接一对节点 \(u\) 和 \(v\) ，表明两节点间存在关系。关系可以是无向的， 如描述节点之间的对称关系；也可以是有向的，如描述非对称关系。例如，若用图对社交网络中人们的友谊关系进行建模，因为友谊是相互的，则边是无向的； 若用图对Twitter用户的关注行为进行建模，则边是有向的。图可以是 有向的 或 无向的 ，这取决于图中边的方向性。
图可以是 加权的 或 未加权的 。在加权图中，每条边都与一个标量权重值相关联。例如，该权重可以表示长度或连接的强度。
图可以是 同构的 或是 异构的 。在同构图中，所有节点表示同一类型的实体，所有边表示同一类型的关系。 例如，社交网络的图由表示同一实体类型的人及其相互之间的社交关系组成。
相对地，在异构图中，节点和边的类型可以是不同的。例如，编码市场的图可以有表示”顾客”、”商家”和”商品”的节点， 它们通过“想购买”、“已经购买”、“是顾客”和“正在销售”的边互相连接。二分图是一类特殊的、常用的异构图， 其中的边连接两类不同类型的节点。例如，在推荐系统中，可以使用二分图表示”用户”和”物品”之间的关系。想了解更多信息，读者可参考 1.5 异构图。
在多重图中，同一对节点之间可以有多条（有向）边，包括自循环的边。例如，两名作者可以在不同年份共同署名文章， 这就带来了具有不同特征的多条边。