1.5 真实网络是稀疏的

现实世界中，不同网络的节点数（N）和链接数（L）差异很大。例如，秀丽隐杆线虫的神经元网络——到目前为止唯一完整得到的生物体神经系统，拥有N=302个神经元（节点）。与之对应，人类大脑据估计大约有1000亿个神经元（N≈1011）。人类细胞的基因网络有大约2万个基因；社会网络中约有70亿个个体（N≈7×109）；万维网中据估计有超过1万亿个网页（N＞1012）。

网络大小上的巨大差异可以从表1-1中明显看出。表1-1列出了一些网络的节点数和链接数。有些网络是其所描述系统的完整连接关系，例如演员关系网络和秀丽隐杆线虫的神经元网络；而其他网络则只是整个网络的一部分，例如万维网和手机通话网络。

从表1-1中可以看出，网络的链接数差异也很大。从理论上讲，对于拥有N个节点的无向网络，其链接数最小为L=0，最大为Lmax。其中，

表示大小为N的完全图包含的链接总数（图1-6）。在完全图中，任意两个节点之间都有链接相连。

图1-6 完全图

包含N=16个节点的完全图，根据公式1.12，其链接数为Lmax=120。完全图的邻接矩阵中，对角线元素为0（Aii=0），其他元素都为1：Aij=1(i≠j)。完全图的平均度为=N-1。完全图通常被称为团（clique），第8章探讨社区识别问题时会经常使用这个词。

真实网络中，L远小于Lmax，说明大部分真实网络是稀疏的。当LLmax时，我们说该网络是稀疏的。例如，表1-1中的万维网包含大约150万个链接。不过，如果该万维网是完全图，根据公式1.12，它应该有Lmax≈5×1010个链接。也就是说，万维网实际包含的链接数占最大可能链接数的比例仅为3×10-5。实际上，表1-1中的所有网络都是稀疏的：实际链接数相对于最大可能链接数（具有同样节点数的完全图所包含的链接数）只占很小一部分比例。

真实网络的稀疏性意味着其邻接矩阵也是稀疏的。实际上，完全图的邻接矩阵中，所有非对角线元素都为1：Aij=1(i≠j)。真实网络的邻接矩阵中，只有很小一部分元素非零。图1-7展示了表1-1列出的蛋白质相互作用网络（图1-4a）的邻接矩阵。可以看出，该矩阵几乎是空的。

图1-7 稀疏邻接矩阵

酵母蛋白质相互作用网络的邻接矩阵。该网络包含2018个节点，每个节点表示一个酵母蛋白质（表1-1）。图中的每个点对应着邻接矩阵中的一个非零元素，表示存在一个蛋白质相互作用。对角线上没有点出现，因为所有对角线元素为0。只有很少的地方有点出现，体现了蛋白质相互作用网络的稀疏性。

稀疏性对于我们研究和存储真实网络有着重要意义。例如，在计算机中存储一个大网络时，只存储链接列表（邻接矩阵中的非零元素）相对于存储整个邻接矩阵会好很多，因为邻接矩阵中相当大比例的元素都是0。因此，使用矩阵表示网络时，零元素会浪费大量的内存空间（图1-7）。