边列表与稀疏性 · 生物医学网络科学

另一种表示是边列表（edge list）：每行写一条边，如 a b、a c。STRING、BioGRID 等数据库下载的数据通常就是边列表（附带置信度等列）。第三种常用表示是邻接表（adjacency list）：为每个节点存一个邻居列表，如 c: a b d。NetworkX 的图对象在内部就是“字典套字典”的邻接表。

真实网络几乎都是稀疏的： $N$ 个节点最多有 $L_{\max}=N(N-1)/2$ 条边，而实际边数通常只是它的极小部分。例如一个含 2 万个蛋白的网络若有 20 万条边，密度只有约 0.1%。此时邻接矩阵绝大部分元素是 0，用边列表或稀疏矩阵存储更省内存。

稀疏网络：边数 $M$ 远小于 $L_{\max}$ 。理论上常把它表述为：网络增大时平均度 $\langle k\rangle=2M/N$ 保持有限（ $M$ 与 $N$ 同阶增长），于是密度 $\rho=\langle k\rangle/(N-1)\to 0$ 。若 $M$ 与 $N^2$ 同阶增长，则称为稠密网络。

规模有多大

生物系统的节点数横跨许多数量级：线虫神经系统 302 个神经元；人类约 2 万个蛋白编码基因；人脑神经元数长期被估计为约 $10^{11}$ 量级，Azevedo 等（2009）用各向同性分离法给出的估计约为 860 亿。这些系统的每个节点只与极少数其他节点直接相连：一个神经元的突触伙伴、一个蛋白的结合伙伴都远小于总数。稀疏性带来两个后果：

存储：以表 2.1 中的演员网络为例（ $N\approx7\times10^5$ ），稠密的 64 位浮点邻接矩阵约需 $N^2\times8$ 字节 $\approx 4\times10^{12}$ 字节（4 TB），而 2900 万条边的边列表只需数百 MB；
计算：基于边的算法（求度、广度优先搜索、连通分支）的代价是 $O(N+M)$ ，而基于稠密矩阵的代价是 $O(N^2)$ 或更高。

不同表示的比较

表示	存储	判断 $i,j$ 是否相邻	列出 $i$ 的邻居	适合
稠密邻接矩阵	$O(N^2)$	$O(1)$	$O(N)$	小网络（如数百个脑区）、线性代数运算
边列表	$O(M)$	$O(M)$	$O(M)$	文件交换、数据库下载、流式处理
邻接表	$O(N+M)$	$O(k_i)$ （用哈希表可近似 $O(1)$ ）	$O(k_i)$	遍历类算法（BFS、DFS）、增删边
稀疏矩阵（COO、CSR）	$O(N+M)$	$O(\log k_i)$ （CSR，列号已排序）	$O(k_i)$	大规模矩阵运算、谱方法、随机游走

压缩稀疏行（CSR）格式用三个数组存矩阵：非零值 data、对应列号 indices、每行起点 indptr。第 $i$ 行的邻居就是 indices[indptr[i]:indptr[i+1]]。SciPy 的 scipy.sparse.csr_array 与 NetworkX 的 to_scipy_sparse_array 都采用这一格式。代码示例“稀疏存储”比较了 2 万节点网络在两种表示下的内存，并手工从边列表构造 CSR。

脑网络是例外吗

基于图谱的宏观脑网络节点数少（几十到几百个脑区），功能连接矩阵通常是全连接的加权矩阵（每对脑区都有一个相关系数），按稠密矩阵存储完全合适。这时“稀疏”是研究者通过阈值制造出来的，而不是系统本身的属性，阈值选择会影响所有指标（见网络构建与统计验证）。

同一个系统可以画成很多张不同的网络。节点选什么粒度（基因还是蛋白、脑区按哪个图谱划分）、边用什么证据（实验验证、文本挖掘还是相关系数）、是否加阈值、是否保留方向和权重——每一个选择都会改变后续所有指标。在研究中，“网络是怎么构建的”必须交代得像实验方法一样清楚（详见网络构建与统计验证）。

规模有多大

不同表示的比较

脑网络是例外吗

继续阅读