在上一篇文章中，我们讨论了人肉计算领域的意图博弈 GWAPs，通过引入人与人之间游戏博弈的方式来解决计算机难以完成的任务，那么一个绕不开的话题就是应该如何将意图博弈的结果给聚合起来。这也就是本节我们要进一步讨论的内容。

社交网络

定义

社交网络（Social Network）是一个（有向或无向）图，满足：

• 一个顶点代表社会环境中的一个人或一个实体（如企业、市场）；
• 边（无向）或弧（有向）表示两个节点之间的互相影响的关系、交互或者协作。

进化社交网络（Evolving Social Network）是一个社交网络，满足：

• 每个边（或弧）上至少附加一个时间戳；
• 可以在边（或弧）上附加好几个时间戳。

实例

• 出版物网络：科学家们通过他们的出版物相互联系；
• 工作网络：
  • 员工通过从属关系相互联系；
  • 员工通过一起工作的项目相互联系
• 企业领导网络：在同一董事会任职时，业务主管相互联系。
• 关系网络：熟人朋友关系网
• 社会环境网络：在同一个社区的人们相互建立联系（可用于调查政治极端主义和恐怖主义）
• 消费者网络：人们在购买同一产品或服务时候可以建立联系
• 数字媒体网络：Facebook、Linkedin、Xing 等
• Trump 人脉关系网：https://graphcommons.com/graphs/ee4a43a2-3189-4f82-879c-960344332ea6

小世界

小世界网络（Small World Networks）是一种社交网络，其网络中任意两个节点之间的路径连接长度不超过 $n\in \mathbb{N}$。

人文上看，对于考虑活在同一时代的人来说，形成的是一个小世界网络：已经表明，对于每同一时代的一对人类而言，可以通过不超过 6 个熟人关系相互建立连接。

小世界网络是普遍存在的：从食物链到电力网到代谢加工网络到大脑神经元网络到社会影响网络再到具有导航菜单的网站链接网络都是一个小世界网络。

进一步阅读¹, ², ³l。

网络的聚类与偏好依附特性

在进化网络中，包括社交网络，通常呈现以下两个特性：

• 「聚类(Clustring)」两个未连接的顶点成为连接顶点的概率会随着临
• 「偏好依附(Preferential attachment)」：获得新邻居的顶点的概率随之前邻居数量的增加而增加（例如与过去的邻居数成正比）——一种「Matthew 效应」⁴。

在进化网络中，偏好依附由顶点的度分布表示⁵，即幂律分布（power-law distribution）。顶点的度：连接该顶点的边数（或者邻居数）。

Watts 和 Strogatz ：

• 将「聚类系数」定义为相同第三个顶点的两个邻居的两个顶点将成为彼此的邻居的概率；
• 并表明，在许多进化网，特别是社交网络的聚类系数远高于随机（进化）网络。

Watts 推测，社交网络中的聚类，是熟人互相介绍的结果⁶。

Newman 在物理和生物学之间的实证研究展示了「聚类」和「偏好依附」有⁷：

• 聚类：两位科学家在未来合作的概率随过去合作者数量的增加而增加；
• 偏好依附：科学家获得新合作者的可能性随着科学家过去的合作者数量的增加而增加。

并且，有研究表明，A 和 B 共同作者的概率与 A 和 B 的合作者数量的乘积有关⁸。

链路预测和节点接近度

问题的产生

推荐（Recommendations）通常可以表示为链路推荐（link recommendation）：

• 联系社交网络的推荐
• 在销售平台上推荐产品

「链路预测」（Link Prediction）指预测可由用户选择并因此推荐给用户的链路。

在进化网络中，「节点接近度」（node proximity） 是两个未连接节点在未来连接的概率估计。如果一个进化网络具有「聚类」和「偏好依附」的属性，则可以从当前网络节点计算未连接节点的近似值。这将产生两个问题：

• 如何定义有意义的节点接近度；
• 如何基于节点接近度估计链路预测的性能。

为了解决这两个问题，我们来看一些研究者给出的定义。

基于图距离的节点接近度

图距离（Graph distance）：$P(A, B)$ 是 A 和 B 两节点之间最短路径的（否定）长度。「否定」用来确保节点之间在未来连接的可能性越大。这点对于小世界网络是有意义的。

基于节点邻居的节点接近度

• $\text{nb}(A)$：节点 A 的邻居集合。
• 普通邻居数：$P(A, B) = | \text{nb}(A)\cap \text{nb}(B)|$
• Jaccard 系数：$P(A, B) = \frac{|\text{nb}(A)\cap \text{nb}(B)|}{|\text{nb}(A)\cup \text{nb}(B)|}$
• Adamic/Adar 系数⁹：$P(A, B) = \sum_{C\in\text{nb}(A)\cap\text{nb}(B)}\frac{1}{ln|\text{nb}(C)|}$
• 偏好依附：$P(A, B) = | \text{nb}(A) | \times | \text{nb}(B)|$
• Katz 系数：$P(A, B) = \sum_{l=1}^{\infty} \beta^{l}\times|\text{paths}(A, B, l)|$
  • 其中 $\text{paths}(A, B, l)$ 表示从 A 到 B 长度为 $l$ 的所有路径的集合，$0<\beta<1$
  • 通过长度的指数衰减，使得路径越来越多且越短。
  • 当 $\beta$ 很小时，其结果接近于普通邻居的值。

基于所有路径的节点接近度

设 $H(A, B)$ 表示从 A 开始到达 B 的随机游走步数的期望（我们之后再来讨论如何计算它）。则：

• 击中时间（Hitting Time）：$P(A, B) = H(A, B)$
• 通勤时间（Commute Time）：$P(A, B) = H(A, B) + H(B, A)$
• 如果某些 B 具有极高的平稳概率（Stationary probabilities）$sp(B)$，即随机游走期间 B 「卡住了」的概率，则 $H(A, B)$ 对于所有的 A 来说微不足道。
• 如果某些 B 具有极高的平稳概率$sp(B)$，那么下面这些节点接近度的度量可能有道理：
  • 归一击中时间（Normalized Hitting Time）：$P(A, B) = NH(A, B) = -H(A, B)\times sp(B)$
  • 归一通勤时间（Normalized Commute Time）：$P(A, B) = NH(A, B) = H(A, B)\times sp(B) + H(B, A)\times sp(A)$

SimRank 是以下这个递归定义所定义的不动点： $$ P(A, B) = \left{ \begin{array}{ll} 1 & if A=B \ \gamma \times \sum_{\gamma\in\text{nb}(A)}^{}{\sum_{Y\in\text{nb}(B)}\frac{P(X, Y)}{|\text{nb}(A)|\times|\text{nb}(B)|}} & if A \neq B \ \end{array} \right. $$ 其中 $0<\gamma<1$。直观含义是：两个节点相似相当于他们邻居的相似程度。下一篇文章我们再来继续讨论如何计算这个递归定义的不动点。

改进链路预测的方法

低秩逼近（Low-rank approximation）：

• 降低网络的邻接矩阵的主成分
• 考虑减少邻接矩阵对应的网络中的节点接近度

隐藏根据（Unseen bigrams）：$P(A, B)$ 作为 $\delta$ 个节点之间与 A 相似的 B 的邻居数（从某种意义上定义）。

聚类（Clustering）：

• 从网络中删除更多的「脆弱」（tenuous）边缘（从某种意义上定义）
• 考虑「清理过」（cleaned-up）的网络的节点接近度

参见 ¹⁰

基于节点接近度的链路预测的性能评估

在大部分社交网络中，由于网络本身没有反应的原因，会产生很多新的连接：

• 不是因为此前的友谊而产生的新友谊
• 不是因为此前的合作而产生的新合作
• 潜在的恐怖主义激进化不是由网络中的联系人造成的

因此，无论节点接近度是多少，伪阴性（false negative）的数量通常较高，预测性能也较低。

• 考虑一个进化无向社交网络 N：
  • $N$ 在 时间 $t_0$ 时的实例 $N_{t_0}$
  • $N$ 在时间 $t_1>t_0$ 时的实例 $N_{t_1}$
• 选择节点接近度 $P(.,.)$
• 对未连接的 $N_{t_0}$ 的集合 $U$ 计算 $P(A, B)$ 的值。
• 考虑 U 中节点 A 的集合 CP 使得：
  • 均连接到 $N_{t_1}$
  • 使得 $P(A, B) > 0$ 对于 $B\in U$

正确预测：$CP$ 中连接到 $N_{t_1}$ 的点

伪阳性：集合 $CP$ 中没有连接到 $N_{t_1}$ 的点

伪阴性：集合 $U - CP$ 中连接到 $N_{t_1}$ 的点

注意，这种模型只考虑了无向网络，但适应有向网络的方法很容易。添加到 $N$ 中，且在 $N_{t_1}$ 中而不在 $N_{t_0}$ 中的节点应该被忽略。

进一步阅读的参考文献

---

1. S. Milgram: “The Small World Problem”, Psychology Today. 1 (1):60–67, 1967 ↩︎

2. D. J. Watts: “Small Worlds”, Princeton University Press, Princeton, 1999 ↩︎

3. M. Buchanan: “Nexus: Small Worlds and the Groundbreaking Theory of Networks”, Norton, W. W. & Company, Inc. ISBN 0-393-32442-7, 2003 ↩︎

4. 「因为有一个必有的，必有丰盛，而且从他身上，不可以拿他所有的。」马太福音25:29，国王詹姆斯圣经 ↩︎

5. S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin: “Structure of growing networks with preferential linking”, Physical Review Letters, Nb. 85, pages 4633–4636, 2000 ↩︎

6. D. J. Watts and S. H. Strogatz,: “Collective Dynamics of ‘Small-World’ Networks”, Nature 393, 440–442, 1998 ↩︎

7. M. E. J. Newman: “Clustering and Preferential Attachment in Growing Networks”, Physical Review Letters E, 2001 http://arxiv.org/pdf/cond-mat/0104209v1.pdf ↩︎

8. AL . Barabasi, H. Jeong, Z. Neda, E. Ravasz, A. Schubert, and T. Vicsek: ”Evolution of the Social Network of Scientific Collaboration”, Physica A, 311 3-4, pages 590–614, 2002 ↩︎

9. Lada A. Adamic and Eytan Adar. Friends and Neighbors on the Web, Social Networks, 25(3), pages 211-230, 2003 ↩︎

10. D. Liben-Nowell and J. Kleinberg: “The Link Prediction Problem for Social Networks”, Journal of the American Society for Information Science and Technology, 58(7), pages 1019-1031, 2003 ↩︎