复杂网络的结构与功能 · 生物医学网络科学

一句话看懂

这篇约 90 页的综述把 1998–2003 年间爆发式增长的网络研究整理成三部分：真实网络有哪些共同的统计特征，有哪些模型能解释或重现这些特征，这些结构对网络上的动力学过程有什么影响。很多今天常用的定义和记号都以它为标准出处。

研究背景与问题

Watts–Strogatz 小世界模型（1998）和 Barabási–Albert 优先连接模型（1999）发表后，物理学、计算机科学、生物学、社会学的研究者在短短几年内分析了大量真实网络，概念和术语一度相当混乱：同一个“聚集系数”有两种不同定义，“无标度”与“幂律”混用，社会学几十年的积累与物理学的新工作互不引用。Newman 写这篇综述，是想给这个新领域一个统一的框架和一份可靠的“工具清单”。

核心思想与方法

综述按“经验—模型—过程”组织：

真实网络（第 II 节）：社会网络、信息网络（引文、万维网）、技术网络（互联网、电网）、生物网络（代谢、蛋白质相互作用、食物网、神经网络）。
网络性质（第 III 节）：小世界效应、传递性（聚集）、度分布、鲁棒性、混合模式与度相关、社团结构、网络导航等。
模型（第 IV–VII 节）：泊松随机图与配置模型、指数随机图、小世界模型、Price 模型与 BA 模型等增长模型。
网络上的过程（第 VIII 节）：渗流与鲁棒性、SIR 与 SIS 传播、网络搜索、相变。

其中几个定义在本站各专题中反复使用：

聚集系数的两种定义： $C^{(1)}=\dfrac{3\times\text{三角形数}}{\text{连通三元组数}}$ （全局传递性）； $C^{(2)}$ 为各节点局部聚集系数的平均。两者在同一网络上可以相差很大。

度相关系数 $r$ ：一条边两端节点度的皮尔逊相关系数。 $r>0$ 称同配（assortative）， $r<0$ 称异配（disassortative）。

巨分支判据：配置模型中巨分支存在的条件为 $\sum_k k(k-2)p_k>0$ ，即 $\langle k^2\rangle-2\langle k\rangle>0$ 。

方法上，综述大量使用生成函数：用 $G_0(x)=\sum_k p_k x^k$ 和 $G_1(x)=G_0'(x)/G_0'(1)$ 一次性处理任意度分布下的分支大小、巨分支比例、渗流阈值和 SIR 最终规模。

主要发现

作为综述，它的“发现”是对当时文献的归纳：

小世界效应普遍存在：表 II 汇总的数十个网络，平均最短路径都远小于节点数。Newman 还建议在不连通网络上用“调和平均”距离，使不连通的节点对贡献为零，这正是后来“全局效率”的思路。
高聚类普遍存在：许多真实网络的聚集系数远高于同等规模的随机图。
度分布高度右偏：许多网络的度分布呈重尾。作者建议用累积分布而不是分箱直方图来作图，这比 Clauset 等（2009）的系统方法更早地提醒了直方图尾部噪声的问题。
度相关的规律：表 II 中测得的社会网络几乎都是同配的，而信息、技术和生物网络多为异配。作者坦言这一差异的原因尚不清楚。
研究工具尚不成体系：结尾指出，当时的网络分析指标“只是一堆零散的工具”，还不知道哪些量才是真正重要的。这个判断至今仍有警示意义。

怎样读这篇论文

不要从头读到尾。推荐的路线：

配合复杂系统与网络的数学表示读第 I 节和第 II 节，了解网络的类型，尤其是第 II.D 节的生物网络；
配合网络结构指标与随机图读第 III.A–C 节和表 II，把表中的 $\ell$ 、 $C$ 、 $r$ 与站内的定义对照；
配合小世界与无标度网络模型读第 VI、VII 节（小世界模型与增长模型）；
读过网络上的传播与免疫和网络可控性与稳定性后，再回来读第 IV.B 节（配置模型与生成函数）和第 VIII.A–B 节（渗流与传播）。

第 V 节（指数随机图）和第 VIII.C 节（网络搜索）可以暂时跳过。

局限与后续工作

时效性：综述写于 2003 年，多层网络、时序网络、高阶相互作用、图神经网络等后来的方向都不在其中。Newman 后来把内容扩展为教科书 Networks: An Introduction（2010 年第一版）。
对幂律的处理：表 II 中列出的幂律指数大多来自原始文献的目测拟合。Clauset、Shalizi 与 Newman（2009）随后给出了严格的统计方法，Broido 与 Clauset（2019）进一步发现严格的无标度网络并不常见。
社团结构：第 III.G 节只简单介绍了社团结构；模块度（Newman 与 Girvan 2004）和谱方法（Newman 2006）是在综述之后才系统发展起来的。
生物网络数据的质量：综述中引用的蛋白质相互作用网络来自早期高通量实验，假阳性和假阴性都很高，基于这些数据的统计量需要谨慎解读。

关联知识

生物医学中的网络类型可以与综述第 II 节的网络分类对照阅读。
网络结构指标与随机图中的度分布、平均路径长度、聚集系数（含两种网络层面的定义）都可在综述第 III 节找到标准表述，该专题的延伸资源推荐的就是这部分。
小世界与无标度网络模型中的小世界模型和 BA 模型，对应综述第 VI、VII 节；小世界与无标度的统计判别关于幂律判断的陷阱可与综述第 III.C 节对照。

延伸思考

综述给出的聚集系数有 $C^{(1)}$ 和 $C^{(2)}$ 两种。在一个星形加若干三角形的小网络上，两者可能相差很大。在脑网络论文中，你会选择报告哪一种？为什么？
社会网络多为同配、生物网络多为异配。对蛋白质相互作用网络，异配性可能有什么生物学或数据采集上的原因？
作者在结论中说，我们还不知道哪些网络量才是重要的。结合你的研究问题，你认为应该先确定“要回答什么问题”，还是先计算所有常见指标再看哪个有用？