李晓明

人和人之间的关系，可以看成是一个网络，可以用图或有向图来描述，或者说用它们来建模。在本栏目第2期讨论一笔画问题时我们接触过图，在第4期谈连通问题时针对的也是图，而在第13期讨论网络最大流问题时采用的模型则是有向图。第21期谈选举，也用到了有向图。图和有向图是用算法求解问题中十分常见的一类模型。

取决于所考虑的人群范围和关系的定义，社会网络，有时也称社交网络，可以多种多样。最熟悉的，是现实生活中的“熟人”关系，见面相互都能叫得上名字，用图来描述就很合适，如图1（a）所示。而微博博主之间的“粉丝关系”，不一定是互相的，用图来表示就不合适了，需要用有向图，如图1（b）所示。箭头方向就表达了粉丝关系的单向性。如果两个人互粉，如节点2和节点5，那么他们之间就有两条不同方向的边。

社会网络分析有许多现实的意义。例如，在新冠肺炎疫情期间，发现一个病例，要确定他有哪些“密接者”，就涉及社会网络分析。那种社会网络，其中的边具有时间特性（只是在某个时间段存在），也称作“接触网络”。现在一些城市要求市民在一些场所通过扫描特定的二维码“打卡”，其意义之一就是为了在发现病例的时候，能够迅速构建与他相关的接触网络。

本文介绍社会网络分析中的两个基础算法，让读者从中了解社会网络分析的一种主要计算模式——矩阵运算①。这类算法，从算法逻辑的角度来说，会显得比本专栏前面介绍过的那些算法简单许多，它们的引人入胜之处在于其结果体现了某些社会现实意义。……