图的定义与基本类型

两套术语的对应：网络（network）–图（graph），节点（node）–顶点（vertex），连边（link）–边（edge）。有向边也称弧（arc）。

按边的性质分类

• 无向图与有向图（directed graph, digraph）：蛋白质物理结合是对称的，用无向边 $\{i,j\}$；转录因子调控靶基因有方向，用有向边 $(i \to j)$。有些系统同时有两种边，称为混合图：代谢网络中可逆反应相当于无向（双向）边，不可逆反应是有向边；线虫神经系统中化学突触有方向，电突触（缝隙连接）没有方向。
• 无权图与加权图（weighted graph）：脑区之间的功能连接强度、纤维束数量、基因共表达的相关系数、STRING 的置信度都可以作为边权 $w_{ij}$。大多数真实网络本质上是加权的，只是权重常常测不准，于是被简化为 0/1 图。加权图中节点的强度（strength）$s_i=\sum_j w_{ij}$ 对应无权图中的度。
• 符号网络（signed network）：边带正负号。基因调控有激活（+）与抑制（−），信号通路有促进与抑制，功能连接和症状网络中的偏相关也可正可负。符号不是可以随手丢掉的细节：把负相关取绝对值，等于把“此消彼长”当成“同进同退”。
• 简单图、多重图与自环：简单图没有自环（self-loop，$i$ 与自身相连）和重边（multi-edge，同一对节点之间多条边）。蛋白质自身二聚化（同源二聚体）、转录因子的自调控在图上表现为自环；七桥问题中两块陆地之间有两座桥，必须用多重图表示。分析前要说明如何处理自环和重边，因为它们会改变度和许多指标的数值。

在调控网络里，环路的符号有直接的动力学含义：正反馈环（偶数个抑制边）倾向于产生双稳态与“开关”行为，负反馈环（奇数个抑制边）倾向于稳态维持或振荡（见生物分子网络与拓扑特征）。

几种特殊的图与子结构

• 完全图（complete graph）$K_N$：每对节点都相连，共 $N(N-1)/2$ 条边，平均度 $N-1$。网络中任意两两相连的节点子集称为团（clique），蛋白质复合物在 PPI 网络中常表现为近似的团。
• 子图（subgraph）：节点和边都取自原图的图。由节点子集 $S$ 及原图中 $S$ 内部的全部边构成的子图称为诱导子图（induced subgraph）。“疾病模块”就是疾病基因集合在互作组中的诱导子图（见疾病模块、网络邻近度与药物重定位）。
• 自我中心网络（ego network）：一个节点、它的所有邻居以及邻居之间的边。
• 树（tree）：连通且无环的图；多棵树组成森林。系统发育树、谱系树、最小生成树都是树。
• 图同构（graph isomorphism）：两张图若存在保持邻接关系的节点一一对应，则视为同一张图。同一张图可以有无穷多种画法，节点位置、边的长短都不携带信息——这是读网络图时最容易被误导的地方。

常见网络的图论性质速查