第 1 章精校翻译：引言

第 1 章　引言

网络（network）是彼此相互作用的对象所构成的集合。网络出现在众多科学学科中：统计物理中的原子或相互作用粒子、分子生物学中的蛋白质相互作用、社会学中的社交网络、计算机科学中的互联网 web 图，不一而足。相互作用存在多种类型。二值相互作用是最简单的（Alice 今天与 Bob 互动了吗？），而加权相互作用（Alice 与 Bob 今天的互动次数）或时序相互作用（Alice 与 Bob 在什么确切时刻互动？）则提供了额外的宝贵信息。

具有二值相互作用的网络可以方便地用图（graph）表示。图 $G$ 是一个二元组 $(V, E)$，其中 $V$ 是对象的集合（也称为节点（node）或顶点（vertex）），$E$ 是相互作用的节点对的集合（也称为边（edge）或连接（link））。通过考虑加权边或边的时间序列，这一标准图表示可以推广到加权网络（weighted network）或时序网络（temporal network）。在本引言节的第一和第二部分中，我们将给出若干真实世界网络的实例，并描述它们的共同性质。

1.1　网络实例（Examples of Networks）

让我们给出若干真实世界网络的实例。尽管为了叙述清晰，我们按类型对网络进行分类，但这种分类是主观的，一个网络可以同时属于两个或更多类型。

社交网络最早的实例之一是 Zachary 空手道俱乐部，它表示一个空手道俱乐部 74 名成员之间的友谊关系（见图 1.1）。在为期两年的研究（Zachary, 1977）中，俱乐部成员在总教练与俱乐部主席发生争执后分裂为两个群体。这场争执使得该数据集在网络科学界极受欢迎。我们希望回答这个引人入胜的问题：仅凭友谊图，能否预测最终形成的两个群体？这为社区检测（community detection）问题奠定了基础，我们将在第 4 章详细讨论。

Zachary 空手道俱乐部友谊网络：节点为俱乐部成员，边为友谊关系，按分裂后的两个群体着色 — 图 1.1　空手道俱乐部。

关于现实生活社会关系（熟人、互动）的社交网络数据出了名地难以收集。事实上，问卷是纸质的且分析耗时，使得从大量个体处收集数据十分困难。此外，它们容易出现人为错误和主观解读。幸运的是，在线社交网络的数据集实例要容易收集得多。

因此，大多数大型社交网络数据集的实例来自在线社交网络或网络博客，也就不足为奇了。

一个这样的实例是 LiveJournal 数据集。LiveJournal 是一个在线博客社区，用户可以在其中互相加为好友。用户还可以自由创建其他用户能够加入的群组。这些群组可以视为真值社区（ground-truth communities）。图 1.2 展示了限制在两个最大社区上的 LiveJournal 友谊网络。

LiveJournal 友谊网络限制在两个最大社区上的可视化，两个社区的节点以不同颜色区分 — 图 1.2　LiveJournal 网络中最大的两个社区。

Adamic 和 Glance（2005）研究了 2004 年美国总统大选期间政治博主的链接模式。他们共考察了 1494 个博客，其中 759 个为自由派、735 个为保守派，并通过识别一个博客是否引用另一个博客来构建相互作用。如图 1.3 所示，自由派与保守派博客圈之间的差异十分明显。事实上，90% 的相互作用发生在属于同一政治社区的博客之间。

政治博客网络：1494 个博客按自由派与保守派分为两簇，链接多发生在同一政治阵营内部 — 图 1.3　政治博客（Political Blogs）网络。

其他著名的在线社交网络还有 Twitter、Facebook 和 LinkedIn。

面对面互动网络（Face-to-face interaction networks）

高中数据集记录了法国一所高中学生之间的近距离接触事件。学生之间的互动通过可穿戴传感器每 20 秒记录一次，实验跨越数个工作日。同一实验在连续三年中进行（Fournet and Barrat, 2014；Mastrandrea et al., 2015），各数据集的维度见表 1.1。我们还在图 1.4 中画出了 2013 年的加权图，其中权重对应两名学生之间记录到的互动次数。最后，由于每名学生都属于一个班级，如何基于时序相互作用恢复班级的问题随之产生。我们将在第 6 章更详细地研究这个数据集。

三个高中生互动数据集的维度表：2011 年 n=118、K=3、T=5609；2012 年 n=180、K=5、T=11273；2013 年 n=327、K=9、T=7375 — 表 1.1　三个高中生互动数据集的维度：学生数 $n$、班级数 $K$ 与快照数 $T$。

2013 年高中互动网络的时间聚合加权图，节点按班级着色，边权为互动次数 — 图 1.4　由高中互动网络（2013 年）得到的时间聚合网络。

我们注意到，时间聚合可能导致重要信息的丢失，而这些信息本可以从数据集的时序性质中推断出来。例如，

单日过程中每名学生平均互动次数随时间变化的曲线，阴影区域对应课间休息，峰值出现在休息开始与结束时刻 — 图 1.5　单日过程中的平均度（每名学生的平均互动次数）。阴影区域对应课间休息。

图 1.5 按快照展示了某一天内每名学生的平均互动次数。观察到的峰值对应课间休息的开始与结束时刻，因为学生们在这些时刻离开和进入教室。

通信网络（Communication networks）

通信网络构成一个重要类别，包括各种交通网络（公路、航线图等）以及个体之间的电话与消息通信。

Enron 电子邮件数据集¹包含 Enron 公司（现已破产）约 150 名员工（大部分来自高级管理团队）的约 500,000 封电子邮件。这些邮件由联邦能源监管委员会在欺诈调查期间恢复。该数据集已被公开，并被许多研究者用于各种信息处理任务，如文档分类或社交网络分析（Carley and Skillicorn, 2005）。

哥本哈根网络研究数据集（Sapiezynski et al., 2019）记录了 700 名大学生在 4 周内的互动，包括近距离接触互动、电话通话和 Facebook 好友关系。

信息与协作网络（Information and collaboration networks）

合著网络的构建方式是：若两名作者共同发表过一篇论文，则将他们相连。由于自动化的引文索引如今已很普遍，大规模的合著网络数据集现已可得。实例包括 DBLP（Yang and Leskovec, 2015）、Citeseer、Cora、WebKB（Getoor, 2005）和 PubMed（Namata et al., 2012）数据集。这一做法可以推广到其他领域。例如，利用 IMDB 数据可以构建一个电影演员网络，若两名演员共同出演过一部电影，则将他们相连。

Web 图是信息网络的另一个实例。其构建方式是：若网页 A 引用了网页 B，则从网页 A 向网页 B 连一条（通常是有向的）链接。若干 Web 图与 Wikipedia 网络可从 NetSet 数据库²和网络算法实验室（Laboratory for Web Algorithmics，LAW）³获得。

生物网络（Biological networks）

生物网络这一类别包括蛋白质相互作用网络、食物网和动物社交网络。

让我们给出一个动物社交网络的实例。海豚网络（Lusseau et al., 2003）是由 62 只海豚构成的社交网络，边表示社会互动。在研究期间，一只海豚离开了群体，导致网络分裂为两个社区（见图 1.6）。后来，当这只神秘的海豚回家时，群体重新团聚了。

海豚网络：62 只海豚的社会互动网络，颜色显示一只海豚离开群体后网络分裂为两个社区的方式 — 图 1.6　海豚网络（Lusseau et al., 2003）。颜色显示当一只海豚离开群体时网络如何分裂。

几何定义的网络拓扑（Geometrically defined network topologies）

在机器学习任务中，数据常以矩阵形式给出

$$ X = ( x _ { 1 } , \ldots , x _ { n } ) \in \mathbb { R } ^ { m \times n } , $$

其中 $n$ 是数据点的个数，$m$ 是每个数据点的维数（即特征的个数）。为了借助网络进行数据分析，图的拓扑结构和权重必须从数据中构建。定义连接顶点 $i$ 与 $j$ 的边权重的一种常用方法是使用带阈值的高斯核

$$ w _ { i j } = \left\{ \begin{array} { l l } { \exp \left( - \dfrac { \| x _ { i } - x _ { j } \| ^ { 2 } } { \tau ^ { 2 } } \right) , } & { \text{若 } \| x _ { i } - x _ { j } \| ^ { 2 } \leq \kappa , } \\ { 0 , } & { \text{其他} , } \end{array} \right. $$

其中 $\tau$ 和 $\kappa$ 是可调参数，$\| \cdot \|$ 是数据点之间的距离。特别地，截断参数 $\kappa$ 可以避免网络过于稠密、带有大量小权重边。另一种常用方法是将每个顶点与其 $K$ 个最近邻相连。关于数据相似性网络构建的其他方法的描述，我们参考 (Grady and Polimeni, 2010, Chapter 4) 与 (Stankovic et al., 2020)。

MNIST 数据库（LeCun et al., 1998）是一个包含 70,000 个手写数字的数据库，常用作机器学习中的基准。图 1.7 展示了用数字 0、1、2 的 300 张图片、以高斯核作为权重函数构建的网络。更准确地说，我们首先计算一个 $K$ 近邻图（$K = 8$），其权重为

$$ w _ { i j } \ = \ \left\{ \begin{array} { l l } { \exp \left( - \dfrac { 4 \| x _ { i } - x _ { j } \| ^ { 2 } } { \tau _ { i } } \right) , } & { \text{若 } x _ { j } \text{ 是 } x _ { i } \text{ 的 } K \text{ 个最近邻之一} , } \\ { 0 , } & { \text{其他} , } \end{array} \right. $$

其中 $\tau _ { i }$ 表示 $x _ { i }$ 与其第 $K$ 个最近邻之间的距离。最后，通过将 $W$ 替换为 $\frac{1}{2} ( W + W ^ { T } )$ 对权重矩阵进行对称化。

由 MNIST 数字 0、1、2 的 300 张图片经 K 近邻图与高斯核权重构建的网络，节点按数字类别着色 — 图 1.7　由取自 MNIST 数据库的数字 0、1、2 的 300 张图片构建的网络。

1.2　复杂网络的共同性质（Unifying Properties of Complex Networks）

1.2.1　网络普遍共有的性质有哪些？（What are the Properties Commonly Shared by Networks?）

许多真实世界的复杂网络共有若干基本性质。

稀疏性（Sparsity）

节点 $i$ 的度（degree）记为 $d _ { i }$，是与该节点关联的边数，换句话说，是与节点 $i$ 相互作用的节点数。即使网络中的节点数 $n$ 可以很大，平均度 $\bar { d } = \frac { 1 } { n } \sum _ { i = 1 } ^ { n } d _ { i }$ 往往也很小。例如，从表 1.2 中可见，DBLP 合著网络有 13,326 个节点，而平均度 $\bar { d }$ 仅为 5.1。这一效应在 Facebook 等社交网络中更加明显：即使总用户数巨大且仍在增长，每个用户的好友数仍然很小（甚至可能是有界的）。如果平均度 $\bar { d }$ 比节点数 $n$ 低若干个数量级，我们称该网络是稀疏（sparse）的。

连通性（Connectivity）

二值无向图 $G = ( V , E )$ 的一个连通分量（connected component）是节点集 $U$，使得对任意两个节点 $i , j \in U$，都存在一条连接 $i$ 与 $j$ 的路径。由于两个连通分量必然不相交，节点集 $V$ 因此可以划分为有限个互不重叠的连通分量 $U _ { 1 } , \dots , U _ { p }$。若 $p = 1$，我们称图是连通的，否则称其为不连通的。尽管真实世界的网络可能不连通，但最大连通分量的相对规模通常非常大（例如包含约 90% 的节点），而其余分量则小得多（Newman, 2001a）。

小世界（Small world）

在一项著名的实验中，Milgram 要求参与者把一个文件夹（内含若干与本研究相关的文件）寄给自己的一位熟人，以期最终送达指定的目标人物（Milgram, 1967）。尽管在大多数情况下参与者未能成功（或因能力不足，或因缺乏意愿），但约有 20% 的参与者成功将文件送达了指定目标。⁴ 此外，起点与目标之间的中间人平均数目为 5.2。尽管 Milgram 的实验后来受到了批评（Kleinfeld, 2002），它们仍以“六度分隔”（six degrees of separation）现象之名融入了大众文化。^[校勘]事实上，这一现象此后已在许多网络中被经验地观察到（见 Watts, 2000；Newman, 2001b 及表 1.2）。

七个真实网络的基本特征表：节点数、边数、平均度、平均距离、聚类系数（含随机图基线对照）与度分布指数 — 表 1.2　若干所选网络的基本特征。各量为：节点数 $n$、边数 $| E |$、平均度（邻居节点的平均数目）$\bar { d }$、两节点间的平均距离 $\delta$、聚类系数 $\mathrm{cc}$（括号内为若图的边被随机抽取时的聚类系数）、度分布的指数 $\alpha$。

关系传递性与三元闭包（原文 Edge transitivity）

有句流行的俗语告诉我们：“朋友的朋友也是朋友”。因此，人们会期望网络中的相互作用具有关系传递性（transitivity），也就是三元闭包倾向。这意味着，如果 Alice 与 Bob 相互作用，且 Bob 与 Cecile 相互作用，那么 Alice 与 Cecile 也很可能相互作用。聚类系数（clustering coefficient）度量的正是这一现象。这里原文的 “Edge transitivity” 指社会网络中的关系传递与三元闭包，不是图论中“边传递图”的对称性概念。我们定义连通三元组（connected triple）为三个节点的集合，其中一个节点与另外两个节点相连；我们也定义三角形（triangle）为三个两两相连的节点的集合。由于每个三节点三角形贡献三个连通三元组（分别以三个节点中的每一个为中心），聚类系数 $\mathrm{cc}$ 由下式给出

$$ \mathrm { \; cc \; = \; { \frac { 3 \times \ 三角形数 } { \ 节点的连通三元组数 } } . } $$

考虑一个节点间相互作用纯随机的图（即两个节点之间以概率 $p$ 发生相互作用）。由于规模为三的节点集合共有 $\binom { n } { 3 }$ 个，三角形的期望数目即为 $\binom { n } { 3 } p ^ { 3 }$，而连通三元组的期望数目为 $\binom { n } { 3 } p ^ { 2 }$。因此，随机图的聚类系数等于 $3 p$。最后，由于共有 $\binom { n } { 2 }$ 个节点对，每个节点对以概率 $p$ 相互作用，$p$ 可以用比值 $| E | / \binom { n } { 2 }$ 来估计。因此，随机图的聚类系数可以用 $\frac { 6 | E | } { n ( n - 1 ) }$ 来估计。从表 1.2 中我们观察到，真实世界社交网络的聚类系数比同等规模随机图的聚类系数高出若干个数量级。

Tips：这段推导给出了随机图基线估计 $\mathrm{cc} \approx 6|E|/(n(n-1))$，正是表 1.2 括号中的数值；“与随机图比较”的思路在第 4 章模块度（modularity）概念中还会再次出现。

重尾度分布（Heavy-tailed degree distribution）

记 $p _ { k }$ 为均匀随机抽取的一个节点具有度 $k$ 的概率，并称 $\{ p _ { k } : k = 0 , 1 , 2 , \ldots \}$ 为度分布（degree distribution）。在一个随机网络中——即从 $\binom { n } { 2 }$ 个节点对中均匀随机地抽取 $| E |$ 条边——度分布是参数为 $n , p$ 的二项分布，其中 $\hat { p } = | E | / \binom { n } { 2 }$ 是连边概率的估计。然而，在大多数网络中，度分布高度右偏，换句话说，在远高于均值的取值处具有重尾（heavy tail）分布。这凸显了以下事实：少数节点具有非常大的度（例如社交网络中的“网红”），而绝大多数节点的度非常小。因此，用幂律（power law）为真实网络的度分布建模一般更为准确。

若随机变量 $X \in [ x _ { \mathrm { m i n } } , + \infty )$ 取自一个密度为 $f ( x ) = C x ^ { - \alpha }$ 的概率分布，则称它服从指数为 $\alpha$ 的连续幂律。虽然为使概率分布良定义需要 $\alpha > 1$（此时由正则化可得 $C = ( \alpha - 1 ) x _ { \mathrm { m i n } } ^ { \alpha - 1 }$），$\alpha$ 的典型取值常落在 $2 < \alpha < 3$ 的范围内。幂律的一条重要性质是标度自由（scale-free，或称标度不变），即对任意常数 $c$ 都有 $f ( c x ) \propto f ( x )$。由于度取整数值，我们将考虑幂律的离散变体，即 Zipf 分布（Zipfian distribution）：$\mathbb { P } ( X = k ) = C k ^ { - \alpha } \, \mathbf { 1 } ( k \geq x _ { \mathrm { m i n } } )$，其中 $C = \left( \sum _ { k = 0 } ^ { \infty } \left( k + x _ { \mathrm { m i n } } \right) ^ { - \alpha } \right) ^ { - 1 }$。

由于分布尾部会出现大幅涨落，拟合幂律是复杂的（Newman, 2005b；Clauset et al., 2009）；但方便的是注意到：当 $k \geq x _ { \mathrm { m i n } }$ 时 $\log \mathbb { P } ( X = k ) = - \alpha \log k + \log c$，因此在 log-log 尺度下概率分布是一条直线。为减弱上述尾部涨落的影响，拟合时最好使用互补累积分布函数（CCDF）而非密度函数。Hill 估计量也能准确估计幂律的指数，详见例如 (Clauset et al., 2009)。图 1.8 展示了 Citeseer 网络的幂律。

尽管幂律范式已被广泛接受、有时被称为一条“普适定律”，它也受到了激烈的批评。特别地，在相当常见的条件下，对 log-log 图做线性回归会产生显著的系统误差（见 Clauset et al., 2009, Appendix A）。此外，Lima-Mendez 和 van Helden（2009）表明，对生物网络而言，幂律度分布只是一个神话。类似地，Broido 和 Clauset（2019）通过对 1000 多个网络应用拟合优度检验，表明具有幂律度分布的网络实际上很少见。尽管如此，绝大多数真实世界的网络都具有重尾度分布。

Citeseer 网络节点度分布直方图：高度右偏，绝大多数节点度很小，少数节点度很大 — (a)　节点度直方图

Citeseer 网络度分布的 log-log 图，数据点近似落在一条直线上，并带有线性回归拟合线 — (a)　节点度直方图

1.2.2　这些性质如何产生？（How do these Properties Arise?）

为了解释上述性质如何在网络中产生，我们引入若干具有随机节点相互作用的随机图模型。这些随机图模型将在第 2 章详细研究。它们也将作为研究与网络相关的统计问题时的参照。

Erdős–Rényi 随机图（Erdős–Rényi random graphs）

最简单的随机图模型是 Erdős–Rényi 模型。该模型有 $n$ 个节点，每对节点以概率 $p$ 相连。

这是一个简单的模型，特别是因为它假设不同节点对之间的相互作用相互独立。因此，该模型不能产生上述关系传递性或三元闭包效应。此外，Erdős–Rényi 随机图的度分布是二项分布 $\mathrm { Bin } ( n , p )$，⁵ 它不是重尾的。

尽管如此，Erdős–Rényi 模型仍能以优美的方式阐释连通性与稀疏性。事实上，由于度分布是二项分布，可知节点的平均度 $\bar { d }$ 等于 $n p$。若 $p$ 为常数，则意味着 $\bar { d }$ 随节点数 $n$ 一同增长，因此在这一标度情形（scaling regime）下图不是稀疏的。于是常见的做法是让 $p$ 随 $n$ 变化，使得 $p = p _ { n } \ll 1$。例如，取 $p = \frac { a } { n }$（$a$ 为常数），则 $\bar { d } = a$，平均度在 $n$ 增大时保持不变。我们将在第 2 章看到，另一个有趣的选择是 $p _ { n } = a \frac { \log n } { n }$，此时平均度 $\bar { d } = a \log n$ 随 $n$ 对数增长。图 1.9 展示了 Erdős–Rényi 图的两个例子。我们观察到，当 (a) 中 $p _ { n } = \frac { 2 } { n }$ 时，图是不连通的，即有相当数量的节点汇聚在一个连通分量中，而一些节点仍然孤立。相反，当 (b) 中 $p _ { n } = \frac { 2 \log n } { n }$ 时，图看起来是连通的。我们将在第 2 章看到，严格的命题如何证实这些观察。

Tips：$p_n = a/n$ 与 $p_n = a\log n / n$ 这两种标度的对比，预告了第 2 章关于 Erdős–Rényi 图连通性阈值的严格定理（Theorem 2.1/2.2）。

n=100 的 Erdős–Rényi 图两例：(a) p_n=2/n 时图不连通、有孤立节点；(b) p_n=2 log n / n 时图连通 — 图 1.9　$n = 100$ 且连边概率 $p _ { n }$ 取不同值的 Erdős–Rényi 图。

随机几何图（Random geometric graphs）

可以通过引入几何来为这种关系传递性和三元闭包建模。让我们考虑 $n$ 个节点，并假设每个节点在欧氏平面上有一个随机位置。直观上，彼此靠近的节点比相距较远的节点有更多的机会相连。一种极端的选择是假设两个节点相连当且仅当它们的欧氏距离小于阈值 $r$。这给出了随机几何图（Random Geometric Graph，RGG）模型。从图 1.10 中我们观察到，该模型产生的图（与 Erdős–Rényi 图相比）含有大量三角形。此外，这些图在局部显得稠密，同时在整体上仍相当稀疏。

随机几何图示例：节点随机分布在单位正方形中，欧氏距离小于 0.1 的节点相连，取不同的 n，图中出现大量三角形和局部稠密结构 — 图 1.10　$\mathcal { S } = [ 0 , 1 ] ^ { 2 }$ 且 $r = 0 . 1$ 时 RGG 的示例，取不同的 $n$。

优先连接模型（Preferential attachment models）

Erdős–Rényi 模型解释了稀疏性与连通性，几何图解释了传递性，但这些模型都不呈现幂律度分布。为了对具有标度自由度分布的网络建模，Solla Price（1965，1976，分析引文网络）以及 Barabási 和 Albert（1999，分析 web 图）提出了优先连接（preferential attachment）模型。它是一个增长式网络模型，每个时间步都有一个新节点进入网络。新节点与已有节点 $i$ 相互作用的概率正比于节点 $i$ 的度 $d _ { i }$。因此，度大的节点倾向于吸引新边，从而进一步增大自己的度。我们在图 1.11 中画出了由优先连接模型生成的一个图的例子及其度分布。我们将在第 2 章给出该模型的严格定义，并证明该模型在极限下确实具有幂律度分布。

左：500 个节点的优先连接模型的一次实现，少数高度节点成为枢纽；右：10^4 节点优先连接图度分布的 log-log 图与橙色线性回归拟合线 — 图 1.11　左：$n = 500$ 个节点的优先连接模型的一次实现。右：$n = 10 ^ { 4 }$ 个节点的优先连接图在 log-log 尺度下的度分布。橙色曲线表示线性回归拟合。

1.3　与网络相关的统计问题有哪些？（What Are the Statistical Problems Related to Networks?）

1.3.1　如何对网络节点聚类？（How to Cluster Network Nodes?）

社区检测（community detection，又称社区恢复（community recovery）或图聚类（graph clustering））是网络分析中一个非常常见的问题。它要把节点划分为 $K$ 个社区（community，又称组、块或簇），使得同一社区内部的节点具有某些相似的性质。直观上，我们应假设同一社区中的节点比属于不同社区的节点更可能相互作用。⁶

同样直观地说，一个好的划分应当最小化不同簇之间的相互作用数目。因此，第一类图聚类方法——称为基于割的方法（cut-based methods）——旨在找到 $K$ 个簇，使得不同簇之间的相互作用数目最小。由此产生了若干谱方法（spectral methods），它们利用一个恰当选取的矩阵的特征向量中所含的信息来恢复社区。这把图论与线性代数优美地联系了起来。

另一些聚类方法通过某些准则评估给定划分的质量，并以优化这些准则为目标。这类方法的一个例子基于模块度（modularity）概念。本质上，模块度把一个带有簇的图与某个参照随机图模型进行比较。模块度的最大化通常通过贪心算法完成。这类方法的一个优点是不需要预先知道簇的个数。

不幸的是，我们将看到基于模块度的方法容易过拟合。特别地，我们将证明，在没有社区结构的随机图（如 Erdős–Rényi 随机图）上，也能找到具有高模块度的划分！我们将看到如何用贝叶斯方法来缓解这一问题。这类方法假设图数据由一个带有聚类结构的随机图模型生成，并通过马尔可夫链蒙特卡罗（Markov Chain Monte Carlo）算法寻找最优参数。

1.3.2　网络中哪些节点最重要？（Which Nodes are Most Important in a Network?）

在大型网络中，许多应用都要求按重要性对节点进行排序。实例包括：识别社交网络中最有影响力的节点、研究疾病的超级传播者，以及分析城市或技术网络（如电网）中的瓶颈节点（bottlenecks）。尽管这些问题都与寻找最重要、最关键的节点有关，但“重要性”这一概念的含义差异很大。事实上，社交网络中最有影响力的节点可能就是度最大的节点。例如，当在 Twitter 或 Instagram 上创建账号时，这些在线社交网络会建议新用户关注热门用户。相反，电网中的这类瓶颈位于度较小的节点上；若这些节点不存在，网络流就会发生很大变化。最后，还有一些应用（如 PageRank）基于网络节点上的随机游走来对节点排序，以模拟浏览或搜索行为。

1.3.3　如何推断网络中的重要信息？（How to Infer Important Information in a Network?）

分析一个非常大的网络，借助汇总统计量（summary statistics）往往更容易完成。一些例子是：估计社交网络用户的平均年龄、找出人群中吸毒者的比例、选举前的民意调查，等等。第一种可能是均匀抽取 $k$ 个节点，并对这一样本取平均。不幸的是，实践中往往难以均匀地抽样（sampling）节点。典型地，在 Facebook 或 Twitter 这样的巨型社交网络中无法高效地进行均匀抽样，因为 (a) 这些平台上所有账号的列表并不公开；(b) API 访问速率有严格限制。例如，一个普通 Twitter 账号每分钟最多只能发出一次请求。按这个速率，我们需要约 950 年才能爬完整个 Twitter 社交网络……

此外，抽样过程中的一个小偏差就可能导致估计量中非常大的偏差，许多涉及选举前民意调查的著名例子都可以作证。需要特别注意的是，节点抽样中的偏差无法通过简单地抽取更多节点来消除。一个臭名昭著的例子涉及《文学文摘》（The Literary Digest）：该刊在 1936 年调查了超过两百万人，却错误地预测 Landon 将明显战胜 Roosevelt。其抽样方式造成了偏差，因为这家报纸只调查了自己的读者，而这些读者比普通公民更富有。⁷

本书结构（Book Organisation）

本书的组织结构如下。我们首先在第 2 章介绍各种随机图模型。第 3 章聚焦于网络中的中心性（centrality）指标。社区检测问题在第 4 章提出并加以分析，第 5 章讨论网络上的半监督学习（semi-supervised learning），即已知部分关于社区结构信息的情形。第 6 章将社区检测问题推广到时序网络。最后，第 7 章介绍网络中的抽样与问卷调查技术。

本书的文献定位（Book Bibliographic Position）

让我们讨论本书相对于其他参考著作的定位。随机图模型在 Bollobás, 2001；Chung and Lu, 2006；Janson et al., 2011；Hofstad, 2016 中得到了透彻的分析。图形成过程（如优先连接过程）与图上的动力学（如流行病过程）在 Durrett, 2007；Draief and Massoulié, 2010；Barabási, 2016；Newman, 2018；Masuda and Lambiotte, 2021 中研究。随机图与复杂网络模型在社交网络中的具体应用在 Wasserman and Faust, 1994；Doreian et al., 2005；Carrington et al., 2005；Scott and Carrington, 2011；Prell, 2012；Yang et al., 2016；Borgatti et al., 2018；Knoke and Yang, 2019 中讨论。

随机图与复杂网络的拟合与可视化见 Ellson et al., 2004；Hagberg et al., 2008；Bastian et al., 2009；Kolaczyk et al., 2009；Goldenberg et al., 2010；Cherven, 2015；Mrvar and Batagelj, 2016；De Nooy et al., 2018；Kolaczyk and Csárdi, 2020。本书不详细覆盖上述主题。

本书的重点是复杂网络分析（亦称网络科学）的基础统计层面。图聚类与社区检测——特别是随机分块模型（stochastic block models）的聚类——在 Newman, 2018；Abbe, 2018 中研究。这仍是一个发展非常迅速的研究领域，许多有趣的新结果不断涌现。本书总结了社区检测问题的主要结果，综述了 2018 年以来的重要进展，并研究了时序网络中的聚类。半监督学习见 Chapelle et al., 2006。本书聚焦于基于图的半监督学习方法及其在时序网络中的应用。

据我们所知，目前尚没有关于网络中心性指标详细分析的教科书（尤其是关于它们的比较分析，以及它们在社交网络范围之外的各种应用）。与社区检测问题的情况一样，重要的新结果仍在不断涌现。我们尝试对这一领域做一个最前沿的综述。此外，我们也没有见过任何关于网络抽样现代方法的教科书。

因此，我们希望本书是对网络统计分析的第一部综合性教科书式论述。

资助（Funding）

本书的写作得到了 Inria–Nokia Bell Labs 项目“Distributed Learning and Control for Network Analysis”（面向网络分析的分布式学习与控制）和欧盟 COST 行动“European Cooperation for Statistics of Network Data Science”（网络数据科学统计欧洲合作）的部分资助。