论文部分内容阅读
人和人之间的关系，可以看成是一个网络，可以用图或有向图来描述，或者说用它们来建模。在本栏目第2期讨论一笔画问题时我们接触过图，在第4期谈连通问题时针对的也是图，而在第13期讨论网络最大流问题时采用的模型则是有向图。第21期谈选举，也用到了有向图。图和有向图是用算法求解问题中十分常见的一类模型。
取决于所考虑的人群范围和关系的定义，社会网络，有时也称社交网络，可以多种多样。最熟悉的，是现实生活中的“熟人”关系，见面相互都能叫得上名字，用图来描述就很合适，如图1（a）所示。而微博博主之间的“粉丝关系”，不一定是互相的，用图来表示就不合适了，需要用有向图，如图1（b）所示。箭头方向就表达了粉丝关系的单向性。如果两个人互粉，如节点2和节点5，那么他们之间就有两条不同方向的边。
社会网络分析有许多现实的意义。例如，在新冠肺炎疫情期间，发现一个病例，要确定他有哪些“密接者”，就涉及社会网络分析。那种社会网络，其中的边具有时间特性（只是在某个时间段存在），也称作“接触网络”。现在一些城市要求市民在一些场所通过扫描特定的二维码“打卡”，其意义之一就是为了在发现病例的时候，能够迅速构建与他相关的接触网络。
本文介绍社会网络分析中的两个基础算法，让读者从中了解社会网络分析的一种主要计算模式——矩阵运算①。这类算法，从算法逻辑的角度来说，会显得比本专栏前面介绍过的那些算法简单许多，它们的引人入胜之处在于其结果体现了某些社会现实意义。在讨论中，我们总假定网络结构是已经给定的有向图，而且采用的是邻接矩阵表示。在本栏目第4期讨论图的连通问题时，我们用过图的邻接矩阵表示。不过那里仅涉及无向图，邻接矩阵是对称的;本文则主要关注有向图，邻接矩阵一般不对称。例如，图2（a）就是前面图1（b）中有向图的邻接矩阵表示，其中行和列的编号对应图中的节点，即第i行第j列的值aij=1，当且仅当有一条从节点i指向节点j的边。有时候，如果需要表示一个节点指向自己的情形，就会有aii=1。
对矩阵概念陌生但对编程比较熟悉的读者，不妨就想像程序语言中的“二维数组”。在Python中可用二维列表或者numpy中的数组直接体现，如图2（a）中的矩阵用二维列表给出就是：
A=[[0，0，1，0，0，0]，
[1，0，1，1，1，0]，
[0，0，0，0，0，0]，
[1，0，0，0，1，0]，
[0，1，1，0，0，1]，
[0，0，1，0，0，0]]
用A[i][j]訪问它的第i行第j列元素。有时候，为方便起见，也用矩阵（数组）的第i个行向量和第j个列向量来分别指代A[i][j]，j=1，2，…，n和A[i][j]，i=1，2，…，n。注意，它们分别都包含n个元素，视觉形象上对应数组的行和列。
我们要讨论的两个算法，其社会现实意义分别与社会网络中人们的“发言权”和“影响力”有关。为了体会这些说法的现实含义，不妨考虑下面这样一种情境。
设想在某中学的一个班里，学生们相处久了相互已经比较熟悉。现在要讨论某个话题，如生物多样性，或者校门口那一棵大槐树的高度。教师让每个学生分别填写表1，写出自己的姓名和2～5个认为对该话题比较有发言权的同学的姓名。
教师收上来这些纸条，你马上能意识到，她有了一个社会网络的数据，而且其中表达的关系是有方向性的：每个学生是其中一个节点，如果学生i在他的表中提到了学生j的名字，那么网络中就有一条从i指向j的边。例如，图3就是一次实际填报数据给出的结果。我们看到每个节点发出有若干指向其他节点的边（称为出向边），同时作为结果，每个节点也“收到了”若干来自其他节点的边。此处重点是，这种“入向边的条数（称为“入度”），不同节点很可能是不同的，反映了一个学生被其他学生“认可”的情况。
一般来说，针对一个话题，每个学生都会有自己的观点，有的坚实，有的飘忽，姑且称其为不同程度的“发言权”。而这种程度是被其他同学看在眼里，表达在上述表格中的。显然，这种发言权意味着某种价值，有高低。我们来介绍一种评估这种价值的计算方法。
按照填表时给学生的背景意义，我们可以理解，如果节点i的入度大于节点j的入度，大致可以说明更多的人认为i比j对当下话题更有发言权。也就是说，节点的入度可以是发言权高低的一种指示器。不过我们还想更进一步，认为一个人的发言权不光取决于有多少人认为他有发言权，还取决于认为他有发言权的人有多大的发言权。同时，若某人认可的人较多，他的分量体现在一个人身上应该较少。直觉上，这是有道理的。利用一些合理的直觉（尽管不一定能证明总是对的），形成启发式来指导计算，是利用计算机求解问题的一种基本策略。在本栏目前面的文章中我们已经看到过不少例子。在这种思想下，接着就要考虑两点，一是将启发式变成算法，二是在应用实践中检验。
下面就是解决这个问题的著名的PageRank算法，它通过迭代同时更新每个节点的值，直到收敛误差满足要求或达到某个预设的迭代次数。算法要点是：在迭代的每一轮，让每个节点将自己的当前值均分给出向邻居节点，同时将从入向邻居节点收到的当前值加和作为自己下一轮的当前值。图4给出一个示意。关注左边图中的节点v，它有3个入向邻居，每个有不同的出度。右边则是按照上述算法思想对v进行更新的公式。
不难想到，基于有向图中的连接关系，对每一个节点都可以写出一个类似但不同的公式来。假设有n个节点，通常令每个节点的初值为1/n，按照公式进行迭代，就是PageRank计算的过程。在我们前面设置的背景问题下，这也就是学生们对某一个问题的“发言权”的计算过程了。
不过，上面只是阐述了“算法思想”。落实到明晰的算法描述还需要做些整理。关键在于“按不同的公式同时更新每个节点的值”具体怎么实施。这里首先要解决的是不同公式的统一表达问题。
取决于所考虑的人群范围和关系的定义，社会网络，有时也称社交网络，可以多种多样。最熟悉的，是现实生活中的“熟人”关系，见面相互都能叫得上名字，用图来描述就很合适，如图1（a）所示。而微博博主之间的“粉丝关系”，不一定是互相的，用图来表示就不合适了，需要用有向图，如图1（b）所示。箭头方向就表达了粉丝关系的单向性。如果两个人互粉，如节点2和节点5，那么他们之间就有两条不同方向的边。
社会网络分析有许多现实的意义。例如，在新冠肺炎疫情期间，发现一个病例，要确定他有哪些“密接者”，就涉及社会网络分析。那种社会网络，其中的边具有时间特性（只是在某个时间段存在），也称作“接触网络”。现在一些城市要求市民在一些场所通过扫描特定的二维码“打卡”，其意义之一就是为了在发现病例的时候，能够迅速构建与他相关的接触网络。
本文介绍社会网络分析中的两个基础算法，让读者从中了解社会网络分析的一种主要计算模式——矩阵运算①。这类算法，从算法逻辑的角度来说，会显得比本专栏前面介绍过的那些算法简单许多，它们的引人入胜之处在于其结果体现了某些社会现实意义。在讨论中，我们总假定网络结构是已经给定的有向图，而且采用的是邻接矩阵表示。在本栏目第4期讨论图的连通问题时，我们用过图的邻接矩阵表示。不过那里仅涉及无向图，邻接矩阵是对称的;本文则主要关注有向图，邻接矩阵一般不对称。例如，图2（a）就是前面图1（b）中有向图的邻接矩阵表示，其中行和列的编号对应图中的节点，即第i行第j列的值aij=1，当且仅当有一条从节点i指向节点j的边。有时候，如果需要表示一个节点指向自己的情形，就会有aii=1。
对矩阵概念陌生但对编程比较熟悉的读者，不妨就想像程序语言中的“二维数组”。在Python中可用二维列表或者numpy中的数组直接体现，如图2（a）中的矩阵用二维列表给出就是：
A=[[0，0，1，0，0，0]，
[1，0，1，1，1，0]，
[0，0，0，0，0，0]，
[1，0，0，0，1，0]，
[0，1，1，0，0，1]，
[0，0，1，0，0，0]]
用A[i][j]訪问它的第i行第j列元素。有时候，为方便起见，也用矩阵（数组）的第i个行向量和第j个列向量来分别指代A[i][j]，j=1，2，…，n和A[i][j]，i=1，2，…，n。注意，它们分别都包含n个元素，视觉形象上对应数组的行和列。
我们要讨论的两个算法，其社会现实意义分别与社会网络中人们的“发言权”和“影响力”有关。为了体会这些说法的现实含义，不妨考虑下面这样一种情境。
设想在某中学的一个班里，学生们相处久了相互已经比较熟悉。现在要讨论某个话题，如生物多样性，或者校门口那一棵大槐树的高度。教师让每个学生分别填写表1，写出自己的姓名和2～5个认为对该话题比较有发言权的同学的姓名。
教师收上来这些纸条，你马上能意识到，她有了一个社会网络的数据，而且其中表达的关系是有方向性的：每个学生是其中一个节点，如果学生i在他的表中提到了学生j的名字，那么网络中就有一条从i指向j的边。例如，图3就是一次实际填报数据给出的结果。我们看到每个节点发出有若干指向其他节点的边（称为出向边），同时作为结果，每个节点也“收到了”若干来自其他节点的边。此处重点是，这种“入向边的条数（称为“入度”），不同节点很可能是不同的，反映了一个学生被其他学生“认可”的情况。
一般来说，针对一个话题，每个学生都会有自己的观点，有的坚实，有的飘忽，姑且称其为不同程度的“发言权”。而这种程度是被其他同学看在眼里，表达在上述表格中的。显然，这种发言权意味着某种价值，有高低。我们来介绍一种评估这种价值的计算方法。
按照填表时给学生的背景意义，我们可以理解，如果节点i的入度大于节点j的入度，大致可以说明更多的人认为i比j对当下话题更有发言权。也就是说，节点的入度可以是发言权高低的一种指示器。不过我们还想更进一步，认为一个人的发言权不光取决于有多少人认为他有发言权，还取决于认为他有发言权的人有多大的发言权。同时，若某人认可的人较多，他的分量体现在一个人身上应该较少。直觉上，这是有道理的。利用一些合理的直觉（尽管不一定能证明总是对的），形成启发式来指导计算，是利用计算机求解问题的一种基本策略。在本栏目前面的文章中我们已经看到过不少例子。在这种思想下，接着就要考虑两点，一是将启发式变成算法，二是在应用实践中检验。
下面就是解决这个问题的著名的PageRank算法，它通过迭代同时更新每个节点的值，直到收敛误差满足要求或达到某个预设的迭代次数。算法要点是：在迭代的每一轮，让每个节点将自己的当前值均分给出向邻居节点，同时将从入向邻居节点收到的当前值加和作为自己下一轮的当前值。图4给出一个示意。关注左边图中的节点v，它有3个入向邻居，每个有不同的出度。右边则是按照上述算法思想对v进行更新的公式。
不难想到，基于有向图中的连接关系，对每一个节点都可以写出一个类似但不同的公式来。假设有n个节点，通常令每个节点的初值为1/n，按照公式进行迭代，就是PageRank计算的过程。在我们前面设置的背景问题下，这也就是学生们对某一个问题的“发言权”的计算过程了。
不过，上面只是阐述了“算法思想”。落实到明晰的算法描述还需要做些整理。关键在于“按不同的公式同时更新每个节点的值”具体怎么实施。这里首先要解决的是不同公式的统一表达问题。