第 07 章精校翻译：网络中的抽样
第 7 章 网络中的抽样（Sampling in Networks）
许多网络（包括线上和线下社交网络）都无法获得完整的网络图景。因此，研究者需要发展抽样技术，以刻画和研究大型网络。
网络抽样的一般问题可以形式化如下。设 $G=(V,E)$ 是一个无向网络，其中有 $n=|V|$ 个节点、$m=|E|$ 条边。我们的目标是为网络函数的平均值设计一个高效的估计量：
$$ \bar f=\frac{1}{n}\sum_{v\in V}f(v).\tag{7.1} $$
尽管问题的表述很简单，它却可以描述许多现实世界中的统计问题。这里只给出几个例子。
- 社交网络有多年轻？取 $f(v)$ 为节点 $v$ 的年龄；
- 一个社交网络成员平均有多少位朋友？取 $f(v)$ 为节点 $v$ 的度（朋友数量）；
- 网络中某一特定子群体的比例是多少？取 $f(v)=1$（若 $v$ 属于该子群体），否则取 $f(v)=0$。
7.1 抽样方法概览（Overview of Sampling Methods）
7.1.1 独立均匀抽样（Independent Uniform Sampling）
显然，最简单的无偏估计量是独立均匀抽样估计量。也就是说，获得一组样本 $v_{i_1},\ldots,v_{i_k}$，其中每个节点都以某个概率 $p$ 独立抽取。于是，
$$ \widehat f^{(k)}=\frac{1}{k}\sum_{s=1}^{k}f(v_{i_s}).\tag{7.2} $$
严格地说，这里考虑的是有放回抽样。然而，在大型网络中，两次抽到同一节点的概率很小。实践中经常尝试这种方法，但它至少有以下两个缺点：(i) 在多数情况下，实现均匀抽样并不容易。例如，进行电话问卷时，如果主要使用固定电话的号码，就可能造成基于年龄的偏差；(ii) 如果研究对象是一个非常小的子群体，就可能极难从该子群体中收集到足够样本。后一个问题促成了许多基于链式推荐（chain-referral）的方法，参见例如 Goodman（1961）。
7.1.2 滚雪球抽样（Snowball Sampling）
滚雪球抽样是第一种“朴素的”链式推荐方法。在链式推荐过程中，抽样从一名初始受访者（节点）开始；该受访者提供一名或多名朋友（邻居）的联系方式。随后，研究者联系每一名新的受访者进行问卷调查；问卷完成后，再请他或她提供自己的联系人列表。这个过程持续进行，直到收集到足够数量的样本。朴素滚雪球估计量在形式上与估计量 (7.2) 非常相似，即
$$ \widehat f^{(k)}=\frac{1}{k}\sum_{s=1}^{k}f(v_{i_s}),\tag{7.3} $$
其中，$v_{i_1},\ldots,v_{i_k}$ 是接受联系并给出回答的受访者。
注意，如果在每一个阶段只从联系人列表中询问一名邻居，这一过程就对应于社交网络上的随机游走。
朴素滚雪球抽样的一个重要问题是，邻居较多的节点会被过度抽样（Erickson，1979），因为随机游走更有可能到达这些节点。
7.1.3 Metropolis–Hastings 抽样（Metropolis-Hastings Sampling）
减轻大度节点过度抽样的一种自然方法，是使用 Metropolis et al.（1953）与 Hastings（1970b）提出的经典马尔可夫链技术。
为了避免相对于节点度的偏差，我们希望随机游走的目标分布是均匀的，即 $\pi(v)=1/n$。于是，按照 Metropolis–Hastings（MH）方法，我们应将选择邻居节点的概率改为
$$ \widetilde p_{vu} =\frac{1}{d(v)}\min\left\{1,\frac{\pi(u)p_{uv}}{\pi(v)p_{vu}}\right\} =\frac{1}{d(v)}\min\left\{1,\frac{d(v)}{d(u)}\right\} =\frac{1}{\max\{d(v),d(u)\}}, $$
若 $(v,u)\in E$ 且 $v\ne u$；若 $(v,u)\notin E$ 且 $v\ne u$，则 $\widetilde p_{vu}=0$；最后，当 $u=v$ 时，
$$ \widetilde p_{vv}=1-\sum_{s\ne v}\frac{1}{\max\{d(v),d(s)\}}. $$
综上，
$$ \widetilde p_{vu}=\left\{ \begin{array}{ll} 0, & \text{若 }(u,v)\notin E,\\ \displaystyle\frac{1}{\max\{d(v),d(u)\}}, & \text{若 }(u,v)\in E\text{ 且 }v\ne u,\\ \displaystyle 1-\sum_{s\ne v}\frac{1}{\max\{d(v),d(s)\}}, & \text{若 }u=v. \end{array} \right.\tag{7.4} $$
使用马尔可夫链的中心极限定理（例如 Brémaud，1999），Avrachenkov et al.（2018b）为按 (7.4) 生成样本 $v_{i_1},\ldots,v_{i_k}$ 的估计量 (7.3) 建立了渐近一致性。具体地，可以陈述如下定理。
对于 MH 估计量，有
$$ \sqrt{k}\left(\widehat f^{(k)}-\bar f\right)\xrightarrow{D}\mathcal N\left(0,\sigma_{\mathrm{MH}}^2\right),\qquad k\to\infty, $$其中
$$ \sigma_{\mathrm{MH}}^2=\frac{2}{n}f^T Zf-\frac{1}{n}f^Tf-\left(\frac{1}{n}f^T\mathbf 1\right)^2, \qquad f^T=(f(1),\ldots,f(n)), $$并且
$$ Z=\left[I-\widetilde P+\frac{1}{n}\mathbf 1\mathbf 1^T\right]^{-1} $$是基本矩阵（fundamental matrix）。
查看学习笔记中的外引依赖说明（书内未证明）在在线社交网络的语境中，MH 估计量的使用最早由 Gjoka et al.（2010）提出。
7.1.4 被访者驱动抽样（Respondent-driven Sampling）
MH 估计量的一个重要问题是它会重复抽取许多节点，因而效率不高。被访者驱动抽样（Respondent-Driven Sampling，RDS；中文文献中亦见“受访者推动抽样”“同伴推动抽样”）可以修正这个问题；RDS 由 Heckathorn（1997）、Salganik and Heckathorn（2004）以及 Volz and Heckathorn（2008）的一系列工作提出。在 RDS 中，底层抽样过程采用标准随机游走，但估计量改为
$$ \widehat f^{(k)}=\frac{2m}{nk}\sum_{s=1}^{k}\frac{f(v_{i_s})}{d(v_{i_s})}.\tag{7.5} $$
其中，$d(v_{i_s})$ 是节点 $v_{i_s}$ 的度（邻居数量），$m$ 是网络中的边数。当然，$m$ 的值可能不可得，或者难以估计。下面的 RDS 估计量变体可以缓解这一问题：
$$ \widehat f^{(k)}= \frac{\displaystyle\sum_{s=1}^{k}f(v_{i_s})/d(v_{i_s})} {\displaystyle\sum_{s=1}^{k}1/d(v_{i_s})}.\tag{7.6} $$
RDS 估计量 (7.5) 和 (7.6) 是渐近一致的；相应的中心极限定理见 Avrachenkov et al.（2018b）。
7.1.5 带均匀跳跃的被访者驱动抽样（Respondent-driven Sampling with Uniform Jumps）
RDS 估计量仍有一个问题：随机游走可能被困在与网络其他部分连接很少的子网络中。为了克服这一问题，Avrachenkov et al.（2010）建议把随机游走与均匀跳跃结合起来。具体地，我们按如下方式修改网络邻接矩阵 $A$：
$$ \widetilde A=A+\frac{\alpha}{n}\mathbf 1\mathbf 1^T. $$
也就是说，我们在任意两个节点之间添加一条权重为 $\alpha$ 的人工边。这一修改的一种解释是：把基于随机游走的抽样与均匀抽样结合起来。
通常，权重 $\alpha$ 很小，因为一次均匀抽样比一次基于随机游走的抽样代价更高。例如，在在线社交网络中，用户与唯一的数字 ID 关联，均匀节点抽样可以通过查询随机生成的 ID 来完成。然而，实践中这种抽样在资源方面代价很高，因为 OSN（例如 Facebook 和 Myspace）的 ID 空间很大且很稀疏。例如，在 Myspace 中只有 10% 的 ID 属于有效用户（Gauvin et al.，2010），也就是说，平均每十次查询中只有一次能成功找到有效的 Myspace 账户。在这个例子中，参数 $\alpha$ 的一个自然选择是 $1/10$。
注意，由 $\widetilde A$ 定义的加权图上的随机游走仍然是无向图上的随机游走，因此其平稳分布与加权度成正比，即
$$ \widetilde\pi(v)=\frac{d(v)+\alpha}{2m+\alpha n} =\frac{1}{n}\frac{d(v)+\alpha}{\bar d+\alpha}, $$
其中，$\bar d$ 是网络的平均度。因此，我们可以把 RDS 估计量修改为
$$ \widehat f^{(k)} =\frac{1}{nk}\sum_{s=1}^{k}\frac{f(v_{i_s})}{\widetilde\pi(v_{i_s})} =\frac{\bar d+\alpha}{k}\sum_{s=1}^{k}\frac{f(v_{i_s})}{d(v_{i_s})+\alpha}.\tag{7.7} $$
如果平均度和节点总数未知，可以使用类似于 (7.6) 的变体，即
$$ \widehat f^{(k)}= \frac{\displaystyle\sum_{s=1}^{k}f(v_{i_s})/(d(v_{i_s})+\alpha)} {\displaystyle\sum_{s=1}^{k}1/(d(v_{i_s})+\alpha)}.\tag{7.8} $$
把随机游走与均匀重启结合起来的另一个自然候选方法，是 PageRank 风格的修改。也就是说，可以如下改变随机游走的转移概率矩阵：
$$ \widetilde P=(1-\varepsilon)P+\varepsilon\frac{1}{n}\mathbf 1\mathbf 1^T.\tag{7.9} $$
这种方法的一个主要缺点是，即使图是无向的，$\widetilde P$ 的平稳分布（PageRank）也没有可以代入 (7.7) 的显式表达式。当然，也可以对转移概率使用 Metropolis–Hastings 修正。然而，正如前面所述，这种修正会导致频繁的重复抽样。
有趣的是，由修改后的邻接矩阵 $\widetilde A$ 定义的带均匀跳跃随机游走，可以看作具有节点相关重启概率的 PageRank。为此，我们可以把带跳跃随机游走的转移概率矩阵变换为
$$ \begin{aligned} \widetilde P &=(D+\alpha I)^{-1}\left(A+\frac{\alpha}{n}\mathbf 1\mathbf 1^T\right)\\ &=(D+\alpha I)^{-1}DD^{-1}A +(D+\alpha I)^{-1}\alpha I\frac{1}{n}\mathbf 1\mathbf 1^T. \end{aligned} $$
这就是式 (3.8) 的形式，其中重启概率矩阵为
$$ C=(D+\alpha I)^{-1}D =\operatorname{diag}\left(\frac{d(i)}{d(i)+\alpha}\right). $$
个性化分布为 $\nu=\frac{1}{n}\mathbf 1^T$。因此，$\widetilde\pi(v)$ 就是式 (3.9) 中定义的节点 $i$ 的占用时间个性化 PageRank（Occupation-Time Personalized PageRank，OT-PPR）。特别地，矩阵 $C$ 的表达式意味着：节点度较大时，随机游走从该节点重新启动的概率更高。
最后，式 (3.14) 和 (3.15) 给出了连续两次重启之间期望时间的一个有用公式：
$$ \begin{aligned} \mathbb E[\text{连续两次重启之间的时间}] &=\left(\sum_{i\in V}\left(1-\frac{d(i)}{d(i)+\alpha}\right)\frac{d(i)+\alpha}{2m+\alpha n}\right)^{-1}\\ &=\frac{2m+\alpha n}{n\alpha}\\ &=\frac{\bar d+\alpha}{\alpha}. \end{aligned} $$
通过改变参数 $\alpha$，可以用这个公式调节跳跃的频率。
7.1.6 Ratio with Tours 估计量（基于往返游程的比率估计量）
即使偶尔进行一次均匀抽样也可能很困难。因此，我们不在所有节点之间创建人工边，而只在部分节点之间创建人工边。直观地说，最好在网络中相距很远的不同部分的节点之间创建人工边。这应该会显著增加随机游走的混合时间。我们也可以把这些人工连接的节点视为一个超节点（super-node）。用 $S$ 表示这组节点。图 7.1 阐释了超节点的思想。注意，此时图中可以有多重边，随机游走的转移概率需要按多重边的数量作相应修改。
创建超节点后，我们可以在从超节点出发并首次返回超节点的往返游程（tour）中运行随机游走，并使用如下 Ratio with Tours 估计量（基于往返游程的比率估计量，简称 RT 估计量）：
$$ \widehat f^{(k)}= \frac{\displaystyle\sum_{k=1}^{m(B)}\sum_{t=1}^{\xi_k-1}\frac{f(v_{i_t})}{d(v_{i_t})} +\frac{1}{d_S}\sum_{v\in S}f(v)} {\displaystyle\sum_{k=1}^{m(B)}\sum_{t=1}^{\xi_k-1}\frac{1}{d(v_{i_t})}+\frac{n}{d_S}}.\tag{7.10} $$
其中，$\xi_k$ 是第 $k$ 次往返游程（tour）的长度，$B$ 是抽样预算，$m(B)$ 是预算耗尽前完成的往返游程数，即
$$ m(B)=\max\left\{k:\sum_{j=1}^{k}\xi_j\le B\right\}.\tag{7.11} $$
$d_S$ 是超节点的度，并且
$$ \widetilde f(v)=\left\{ \begin{array}{ll} f(v), & \text{若 }v\notin S,\\ 0, & \text{若 }v\in S. \end{array} \right. $$
7.2 基于往返游程的网络模体计数估计量（Tour-based Estimators for Motif Counting）
网络模体（network motif）计数是网络分析中的一项重要任务。例如，我们需要计数三角形和楔形，以计算（全局）聚类系数。
Cooper et al.（2016）提出了基于往返游程的估计量，用于高效估计网络模体。我们注意到，他们的方法可以与超节点思想结合。为使解释透明，考虑从单个节点（记为 $s$）出发并首次返回该节点的一次随机游走往返游程。像前面一样，令 $\xi_j$ 表示第 $j$ 次往返游程的长度。令 $\pi_s$ 表示随机游走处于节点 $s$ 的平稳概率。于是，我们知道
$$ \mathbb E_s[\xi_j]=\frac{1}{\pi_s}=\frac{2m}{d_s}. $$
因此，可以使用下面的估计量估计边数：
$$ \widehat m=\frac{d_s}{2}\frac{1}{m(B)}\sum_{k=1}^{m(B)}\xi_k.\tag{7.12} $$
其中，$m(B)$ 由 (7.11) 定义。
接下来，如果要估计三角形数，我们考虑加权网络上的随机游走：对每条边 $\{v,u\}$ 赋予权重 $1+t(\{v,u\})$，其中 $t(\{v,u\})$ 是包含边 $\{v,u\}$ 的三角形数量。
这种加权网络上的随机游走的平稳分布为
$$ \pi_v=\frac{d(v)+\displaystyle\sum_{u\in N(v)}t(\{v,u\})}{2m+6t(G)}, $$
其中，$t(G)$ 是网络中的三角形数。
因此，可以使用以下估计量估计三角形数：
$$ \widehat t=\max\left\{0, \frac{\left(d(s)+\displaystyle\sum_{u\in N(s)}t(\{s,u\})\right)\displaystyle\sum_{k=1}^{m(B)}\xi_k}{6m(B)}-\frac{\widehat m}{3}\right\}. $$
其中，$\widehat m$ 是边数的一个估计量，例如可以由 (7.12) 给出。
把这一方法用于计数任意网络模体是直接的。
7.3 抽样方法的数值比较（Numerical Comparison of Sampling Methods）
7.3.1 合成网络（Synthetic Networks）
我们首先考虑一个含 $n=20000$ 个节点的 SBM。节点被聚成两个社区，社区大小分别为 200 和 19800。令 $p_{11}=0.3$，而 $p_{12}=p_{22}=0.001$。这模拟了大型社交网络中的一个小型子群体。作为待求平均的函数，我们先取：若节点 $v$ 位于最小社区，则 $f(v)=1$，否则 $f(v)=0$。结果见图 7.2。我们观察到，即使只使用 $k=500$ 个随机选取的节点，均匀抽样也能给出很好的结果；而“朴素”滚雪球抽样则产生高估。这是意料之中的，因为标准随机游走偏向大度节点，而在这个情形下，大度节点位于较小的社区中。另一方面，Metropolis–Hastings 抽样和 RDS 成功地校正了这一偏差。
为了说明均匀抽样未必总是表现最好，我们提出如下情形。与前面一样，取一个由大社区和小社区组成的 SBM，两者大小分别为 49,500 和 500。我们把小社区的节点分成两个大小相等的组，称为 Group-A 和 Group-B。大社区中的节点全部归入另一个组 Group-C。目标是恢复小社区中 Group-A 节点所占的比例。一个实际动机是：小社区可能代表一个难以触达的子群体，例如吸毒者。在这个例子中，小社区进一步分为重度使用者和轻度使用者；研究者可能关心吸毒者中重度使用者的比例。假设我们知道 10 个属于 Group-A 的节点。我们把这 10 个节点合并成一个超节点，并在修改后的图上进行 RDS，再将其与均匀抽样比较。结果见图 7.3。我们观察到，带超节点的 RDS 估计方差要小得多。
7.3.2 现实网络：DBLP（Real-world Network: DBLP）
现在，我们在 DBLP 数据集上比较不同的抽样方法（$n=317{,}080$ 个节点、$m=1{,}049{,}866$ 条边）。在图 7.4 中，我们估计平均度，即取 $f(v)=d(v)$。在图 7.5 中，我们还通过取 $f(v)=\mathbf 1\{d(v)\ge 50\}$ 来估计度大于 50 的节点比例。在这两种情形下，我们都观察到，Metropolis–Hastings 抽样的方差大于 RDS 或均匀抽样。
进一步阅读（Further Notes）
Dasgupta et al.（2012）提出了一种有趣的方法，称为社交抽样（social sampling）。它可以被看作均匀节点抽样与基于随机游走的抽样之间的中间方法。在这种方法中，一旦一个节点被抽样，与其邻居有关的信息也随之可得。显然，如果这种方法可行，它所需的样本数少于均匀节点抽样，并且避免了基于随机游走的方法所产生的依赖。
使用多条并行运行的随机游走来抽样网络可能是有益的，参见 Ribeiro and Towsley（2010）。为了提高效率，多条随机游走要么以一种特殊方式相互依赖，要么彼此独立但作为连续时间随机游走运行，其转移率与节点度成正比。
正如 Avrachenkov et al.（2016b）所讨论的，在某些情况下，链式推荐方法跳过一部分样本可能是有益的。直观地说，跳过一些样本可以降低基于随机游走的方法中的相关性。
网络函数不一定要定义在节点上，也可以定义在边或三角形之类的其他网络模体上。关于这一点的细节，参见 Avrachenkov et al.（2016c）。