众智-社会网络

社会网络

三元闭包

在一个社交圈内，若两个人有一个共同的朋友，则这两人在未来成为朋友的可能性就会提高。我们将上述原则称为三元闭包

原理的拓展

量：两个人的共同朋友越多，则他们成为朋友的可能性越高

质：两个人与共同朋友的关系越密切，则他们成为朋友的可能性越高

如何定义考察三元闭包现象的测度

当前共同朋友数与后来成为朋友的概率关系

数据验证

统计相同数量的共同朋友下，出现新边（成为朋友）的概率

如何计算共同朋友数

邻接矩阵相乘

节点聚集系数

刻画三元闭包现象的一个常用参数，描述某个节点对朋友的聚集能力

节点A的聚集系数 = A的任意两个朋友之间也是朋友的概率（即邻居间朋友对的个数除以总对数）

社会网络结构的统计特征

度分布（包括图的入度和出度）

• 度分布函数。P(k）表示网络中度为k的节点在整个网络中所占的比例。

• 累积度分布函数（CumulativeDegree Distribution Function）。$P_k$表示度不小于k的节点的概率分布，其分布关系为$P_k=\sum_{x=k}^{\infty}{P(x)}$

平均路径长度

$L=\dfrac{2}{N(N-1)}\sum_{i=1}^{N}\sum_{j=i+1}^{N}d_{ij}$

• 任意两个节点间最短路径的平均长度，也叫做网络的平均距离或网络的特征路径长度。

• 它刻画了网络节点之间进行信息传递的代价大小， 在线社交网络中常用其衡量用户之间关系的紧密程度

网络密度

$d(G)=\dfrac{2L}{N(N-1)}$

• 网络中实际存在边数与可容纳的边数上限的比值

• 可用于刻画网络中节点间相互连边的密集程度

• 在线社交网络中常用来测量社交关系的密集程度以及演化趋势

介数(重点)

• 用来描述网络中节点承载最短路径数的能力

• 节点（或边）的介数等于网络中所有最短路径中经过该节点（或边）的概率之和

• 描述了节点在网络中的影响力与中心性程度

介数计算的一种算法

• 从一个节点开始，做广度优先搜索，将节点分层（以便于下面的步骤）

• 确定从起始节点到其他每个节点的最短路径的条数

• 确定当从起始节点沿最短路径向其他所有节点发送1个单位流量时，经过每条边的流量。

• 对每一个节点，重复上述过程，累计，除以2，即得每条边的介数。

样例

以A为起始节点，分层

统计从A到其他节点最短路径的条数

计算每条边的介数（这里以从K到A为例）

• 从底部的节点K开始。一个单位的信息流到达节点K，并且从节点A到K通过节点I和J的最短路径数量相等，这个单位的信息流被等量划分在两条边上（也就是说信息流是按最短路径数量的比例分配的）。 因此可将半个单位的信息流分别放在这两条边上。
• 现在开始向上移动，到达节点I的信息流总量，应该是终结在自己的一个单位加上流给K的1/2单位，即总量为3/2。 这3/2信息流的总量如何从上层节点(F和G)流下来的，即如何在F-I边和G-I边上划分？从步骤(2)得出，从节点A到节点F的 最短路径数是到G的最短路径的两倍，于是从F应该流出两倍的信息流。因此，从F有一个单位的信息流出，从G有半个单位的信息流出。
• 继续用这种方法处理其他每个节点，通过先宽搜索（BFS）逐层次向上移动。

强弱联系

桥和捷径

​ 一个图中，已知A和B相连，若去掉连接A和B的边会导致A和B分属不同连通分量，则该边称为桥(bridge)。

​ 若边A-B的端点A和B没有共同的朋友，则称边A-B为捷径(local bridge)。换句话说，删除该边将把A和B的距离增加至2以上（不含2)，则称该边为捷径。我们定义捷径的跨度为该边两端点在没有该边情况下的实际距离。桥一定是捷径，但捷径不一定是桥，捷径中可能还有一条多节点通路连接A和B使得两者没有共同朋友但其实是连通的。

​ 捷径，特别是其中跨度较大的捷径，其作用和桥无明显差异，只是不那么极端：其两个端点直接触及社交网的两个不同部分并可通过该方式获取原本离自己很遥远的信息。

强三元闭包性质

​ 一般来说，关系的强度可以是一定范围内的任意值，然而，为了简化概念，并与我们的朋友／熟人二分原则相匹配，将社交网中的所有关系归为两大类：强联系（较强的关系，相对应朋友关系）和弱联系（较弱的关系，相对应熟人关系）。一旦决定了按强联系和弱联系将关系分类，就可以来标注社交网络中的每一条边（强或弱）

强三元闭包原理（假设）

• 如果A-B和A-C之间的关系为强关系；则B-C 之间形成边的可能性应该很高；

定义：若A有两个强关系邻居B和C，但B-C之间没有任何关系（强或弱），则称节点A违背了强三元闭包原理；

如果节点A没有违背强三元闭包原理，则称节点A符合强三元闭包原理。

注意：一个节点是否符合强三元闭包是严格定义的，即在标注边的强弱网络中，每个节点要么符合要么违背。

捷径和弱联系

断言：社交网络中，若节点A满足强三元闭包性质，并有至少两个强联系边与之相连， 则与其相连的任何捷径均为弱联系。（反证法证明）。

• 这个结论将一个社交概念（关系的强弱）和一个结构概念（捷径）连接了起来。

统计推论：共同朋友越多，关系强度越高

• 准确些，可以说共同朋友数在总朋友数中的占比（引入邻里重叠度进行衡量）

邻里重叠度

定义一条边(A-B)的邻里重叠度(neighborhood overlap)如下式：

$\dfrac{与A、B均为邻居的节点数}{与A、B中至少一个为邻居的节点数}=\dfrac{共同朋友数}{总朋友数}$

该定义的一个关键特性是，当分子为0时，这个比率为0，对应的边是捷径。 捷径的概念 包含在该定义中，即捷径是邻里重叠度为0的边，因此我们可以把邻里重叠度很低的边粗略视为捷径。

测量描绘了关系强度和局部网络结构（节点的邻居）的一种联系。 考虑如何用这种数据来评估理论预测的全局性结果也是很有意思的。 所谓全局性结果指的是 弱联系起到将包含大量强联系的紧密社区连接起来的作用。 此处，欧尼拉 (Onnela) 等人给出了一种间接的分析，如下所述。 首先，从强度最强的关系开始，按序逐一从网络中进行边删除。 由于节点间连接的删除，超大强连通分量会随之逐渐变小。 然后，他们做同样的操作，但是从强度最弱的关系开始，按强度的升序进行边的删除。 在这种情形下，他们发现超大连通分量缩小得更加迅速；而且，一旦一个临界数量的弱联系被删除，其残余部分会突然分裂。 这个结果是与理论预测是一致的，即弱关系在不同社区之间提供了更加关键的连接结构，将分散的社区连接起来，保持了超大连通分量全局结构的完整。

闭包、结构洞和社会资本

以下图的网络为例，特别关心节点A和B的体验，前者在一个关系紧密群体的中心，后者在多个群体交界处。

嵌入性

节点A 所属网络邻里有很强的三元闭包特征，它有很高的聚集系数。

为了分析节点A周围的结构，下面这个附加定义是有用的。 我们定义网络中一条边的“嵌入性”为其两个端点共同的邻居的数量。 例如，A-B边的嵌入性为2，因为节点A和B有共同的两个邻居节点E和F。 该定义与前面的两个概念相关。 首先，一条边的嵌入性，等于邻里重叠度的分子。 其次，捷径就是那些嵌入性为 0 的边，因为按照定义，捷径是两个端点没有共同邻居的边。

结构洞

​ 节点B用与她有关的多条捷径跨越了组织里的一个结构洞(structural hole)。 结构洞看起来就是存在于网络中两个没有紧密联系的节点集合之间的“空地”。（与有严格数学定义的＂捷径 "不同，这里的 “结构洞” 是非形式化的。）下面要说明的是节点B所处的位置在多个方面要比节点A的位置优越。 根据前几节的观察，第一种优势在于信息方面：节点B可以更早地获得来自网络中多个互不交叉部分的信息。 每个人投入在维护组织中联系的精力有限， 节点B通过积极联系多个不同的群体（而不是仅限于某个群体）更有效地投入自己的精力。
​ 第二种优势在于，处在捷径的一端对其创造性有放大功能 。许多领域的经验表明， 创新常常源自多个观点的意外合成，这里的每个观点本身或许是人们熟知的，但只是在不同且不相关的专业领域内部所熟知。 因此，位于三个无交互群体交界处的节点B，不仅可以得到这些群体的所有信息，还有机会整合来自不同群体的信息。
​ 最后，网络中节点B的位置意味着某种社交“把关”的机会，该节点不仅可以控制节点C和D访问她所属的群体，还可以控制她所属的群体从节点C和D的群体获取信息。 这样，这个位置给予B一种权力资源。 可以想象，在这种情况下，某些人会试图阻止围绕他们所在的捷径形成三角形，例如从节点C或D产生一条到达B所在群体另一节点的边，很有可能会削弱B的社交“把关者”的地位。

社会网络的划分

如何刻画社会网络中“相互紧密连接的节点群”？能否有一种精确的方法将它们找出来？

• 分割法

  • 逐步去掉“跨接边”

• 聚集法

  • “滚雪球”

• 近似

  • 准确与效率的平衡

Girvan-Newman方法（一种分割法）：逐步删除高介数边

同质性与社会网络结构相互影响

同质性

影响社交网络结构最基本的概念之一是同质性，即我们和自己的朋友间往往会有相同的特点。

• 每个人的特质可分为两种：

  • 固有特质：性别、种族、母语等，自然属性
  • 可变特质：居住区、专长、偏好等，建构属性

• 同质性是社会网络结构形成的基本外部原因

社会学的一个基本问题：人们是因为相似，才成为朋友 （selection）；还是因为成为朋友后变得相似（social influence）我们会在后面讨论这个问题。

社会网络中同质性判别的一个测度

假设人们按照两种属性区分（例如性别），我们来看如何判断社会网络中同质性体现的程度？直观上我们可以观察相同颜色节点的聚集程度。但如何定量把握？

基本思想：如果端点颜色相同的边较多，则同质性显现较强

• 给定一个二色图G，让p为一种颜色节点占比，q=1-p对应另一种颜色节点占比

• 考虑 “假若按照该占比随机着色”，于是两端颜色不同的边出现的概率为**2pq**

• 比较G中的情况：端点异色边数／总边数

• 若明显小于2pq，则可认为同质性明显

归属与归属网络

​ 一个公司、组织、社区成员，或者常到某个固定地点，追求特定的兴趣爱好，都是活动，如果在两个人之间分享，那么他们将有很高的几率交往并建立社会网络的连接。我们称此活动为社团 (foci) ，即社会交往的焦点，包含“社会的、心理的、法律的或物理的实体，围绕它们组织有各种社会活动。

​ 归属网络(affiliation network)表明个体关联某个族群或参与某个个体对社团的归属关系。更一般地，归属网络是二分图。

社会网络与归属网络的协同演化

​ 社会网络与归属网络都随着时间在演变发展：新的朋友关系在建立，个体也和新的社团建立关系。 并且，这些改变表示了一种协同演化 (coevolution)，反映选择倾向及社会影响之间的相互作用：如果两个人参与同一个活动，那么这为他们成为朋友提供了机会；而如果两人是朋友，那么他们之间会影响对方参与新的社团。（两种闭包，下文讲）。

​ 我们现在加入两类不同的关系连接。 第一类关系连接是在社会网络中：连接两个个体，表明两者之间的友谊关系（或者其他的社会连接关系，如在职场上的合作）。第二类关系连接是在归属网络中：连接个体和社团活动，表明这个个体参与其中。 我们称此网络为社会归属网络(social-affiliation network) ，反映它同时包含一个个体之间的社会网络及个体与社团之间的归属网络。

同质现象背后的机制：选择与社会影响

​ 在固定不变的一些特质中，如种族或族群，人们倾向于在和他们相似的人之间形成友谊，这通常被称为选择（selection），即人们根据相似的特征选择朋友。

​ 如果特征是具有可变性的，如行为、活动、兴趣、信仰和观念，那么个体之间特征的反馈效应及其在社交网络中的连接会变得很复杂。 选择过程仍然存在，个体的特征影响社交网络中连接的形成。但另外一个过程也在发生作用：人们会因为需要和朋友们保待一致而改变自己的行为。这个过程被描述为社会化(socialization) 和社会影响(social influence)

因此，我们在三元闭包之外，引入另外两个闭包：

• 选择 -> 社团闭包（强调社团对成员关系的影响）
• 社会影响 -> 会员闭包（强调社团会员对其朋友加入社团的影响）

三种闭包的形成样例如下：

也就是说：

• 如果两个不相识的人有了3个或更多共同朋友，则他们下一时点前会成为朋友（三元闭包）

• 如果某人有2个或更多朋友参加了某个俱乐部，则他在下一时点前参加该俱乐部（会员闭包）

• 如果两个不相识的人参加了2个或更多相同的俱乐部，则他们在下一时点前会成为朋友（社团闭包）

更加形象地，我们可以这样表示：

基于三元闭包与同质性原理考察社会（归属）网络结构的变化

基于三个闭包的自动化模拟

对于以下的社会归属网络：

邻接矩阵与归属矩阵可以如下表示：

其中：

• $n$: 人物节点个数

• $m$: 社交聚点个数

• $A(i,j)$ : $i$ 与 $j$ 的连接关系

• $B(i,j)$ : $i$ 是否加入 $j$

• $A(i,*)$ : $A$ 的第 $i$ 行向量

• $B(*,j)$ : $B$ 的第 $j$ 列向量

那么：

• 邻接矩阵的两个行向量内积：两人的共同朋友数
• 归属矩阵的两个行向量内积：两人共同社团数
• 邻接矩阵的一行与归属矩阵一列内积：某人参与的某社团中的朋友数

于是我们可以：

• 根据初始给定情况，将矩阵初始化

• 看“三元闭包”：若$A(i,j)=0$，且$A(i,*)×A(j,*)≥3$，则$A(i,j)$将＝1

• 看“社团闭包”：若$A(i,j)=0$，且$B(i,*)×B(j,*)≥2$，则$A(i,j)$将＝1

• 看“会员闭包”：若$B(i,j)=0$，且$A(i,*)×B(*,j)≥2$，则$B(i,j)$将＝1

• 同时完成上述需要的更新，重新“三看”，直到没有进一步更新的可能

基于大数据的验证

对三种闭包的验证

• 选取2次不同时间的网络快照。

对于三元闭包：

• 对于每个k，在第1次快照中找出恰好有K个共同朋友的节点对，且它们之间没有边。
• 定义T(k)为这些对节点在第2次快照中形成了边的比例。这就是在两个有K个共同朋友的人之间建立连接的几率。

对于社团闭包：

• 对于每个k，在第1次快照中找出恰好有K个共同社团的节点对，且它们之间没有边。
• 定义T(k)为这些对节点在第2次快照中形成了边的比例。 这就是在两个有K个共同朋友的人之间建立连接的几率。

对于会员闭包：

• 对于每个k，在第1次快照中找出恰好有K个朋友的社团，且k不在此社团。

• 定义T(k)为这个节点在第2次快照中形成了边的比例。 这就是k加入了此社团的几率。

最后：

• 画出T(k)作为K的一个函数。

两种力量（selection, influence）的分别作用

参考书上的样例即可。

隔离（segregation）

同质性影响与结果（固有特质相同 -> 可变特质趋同）。

如不同群体的聚居会随着时间的变化而逐渐加强，强调这是一个动态的过程。

谢林模型

我们假设有一群个体，成为代理（agent），每个代理属于X型或0型。 我们将这两种类型看成是不可变的特质，作为研究同质性的基础。代理”居住“在一个网格的单元内，表示一个城市的二维地理空间。 如图4. 15(a)所示，我们假设一些单元内居住着代理，而另一些单元则没有。 一个单元的邻居是与之紧挨着的单元，包括顶角接触的，因此一个不在边缘的单元有8个邻居。 我们可以等价地将这种邻居关系定义为一个图：单元是节点，我们将单元上的邻居连在一起。这样，如图4. 15(b)所示，占据图中单元的代理被安排成图的节点。 为了视觉上的直观性，我们将会继续采用网格进行分析。

该模型的基本制约因素是，每一个代理要和一定量的同类代理成为邻居。 我们假设门槛值 t 适用于所有的代理：如果一个代理发现自己拥有比 t 少的邻居，他就有兴趣挪到其他的单元，我们称这样的代理不满意现状。

代理们按照轮次移动：在每一轮，我们按照一定的顺序考虑不满意的代理，轮流到每个代理，我们将其挪到一个空着且会让他们满意的单元中。 在此之后，一轮移动停止，表示不满意现状的代理经过一段时间，都已更换了他们原本所在的地方。但新的状况可能引起其他代理的不满，于是将引起新一轮的移动。

在关于这个模型的文献中，当代理移动的时候，存在不同的细节处理方式。研究者发现，无论如何处理这些细节，此模型的定性结果非常相似。

对该模型的一些认识

最基本的认识是，即使没有任何代理主动寻求隔离，空间的分隔依然发生。在门槛值之下的代理要在网格中寻求同类更多的位置，也会引起先前已经满足的代理变得不满足。 谢林称这种效果为规整区域的逐步＂拆开“。时间一长，这个过程趋向于使隔离的区域变大，而比较规整的区域受损。 整体效果就是代理们自己的局部偏好产生了一种谁也没刻意追求的全局模式。 隔离的基础已经在此系统中显明，即人们只是想避免在各自所在的局部地区成为极端少数。

正负关系

边的正负性

社会网络中，两个节点之间的关系（边）可能携带着各种各样的社会性含义。除了强弱以外，还有支持（＋）与反对（－），朋友（＋）与敌人（－）等利害关系 。

在一个图中，我们如何判断两点之间形成稳定关系时边的正负？

例如，如何判断0与4的关系？

我们可以依次建立0与1，0与2，0与3，0与4的关系，即可。

或者，更一般的，图的一个环中只能有偶数个负向边，那么这个环是稳定的。

网络结构平衡的定义

我们将上面的三节点图推广到任意节点数的完全图：

结构平衡性质：对于每三个节点组，与它们相关联的三条边，要么都标识为 “+” ，或者 恰有一条边标识为 “+"。

也就是说，（完全）图的结构是平衡的，若其中所有三角关系都是平衡的。

但按照这个定义来判断一个网络是否平衡显然太麻烦了，由此引出以下内容。

平衡定理

如果一个标记（＋／－）的完全图是平衡的，则：

• 要么它的所有节点两两都是朋友
• 要么它的节点可以被分为两组，X 和 Y，其中X组内的节点两两都是 ‘＋’ 关系，Y组内的节点两两也都是 ‘＋’ 关系，而X组中的每个节点与Y组中每个节点之间都是 ‘－’ 关系

也就是说，要么没有敌人，要么敌人关系的双方可以划分成二分图（即完全图可以划分成两个集合，每个集合内任意两个人均互为朋友，属于不同集合的任意两个人均互为敌人）。

平衡定理的证明

取网络中的任意一个节点，称为A，从A的角度来考虑问题。其他节点要么是A的朋友，要么是A的敌人。于是，一种自然地确定 X 和 Y 的方式是让 X 包含 A 以及他的所有朋友，让 Y 包含 A 的所有敌人。 这的确把图中所有节点分成了两组，因为每个节点要么是 A 的朋友，要么就是其敌人。

那么集合 X 和集合 Y 的节点应该以下要求：

• X 中的每两个节点都是朋友。
• Y 中的每两个节点都是朋友。
• X 中的每个节点与 Y 中的每个节点都是敌人

根据我们开头的三节点稳定性，显然。

这个定理带给我们的一个启示：事物的微观性质，有可能导致人们对它的一种宏观认识，这正是人们研究复杂系统时的一种基本追求。

但其实这种方法还是太复杂，我们想进一步简化问题，就必须放松对条件的限制。

平衡定理的推广

• 弱平衡

  • 只是不允许（＋＋－）

• 近似平衡

  • 图中部分三角形是平衡的

• 非完全网络中的平衡

  • 允许一些边的缺失，即考虑非完全图情形

我们希望找到一种局部特征与全局形态之间的简单关系。

弱平衡网络

注意到在平衡网络中排除的两种三角关系在社会关系的含义（分量）上是有区别的：

• 改变（－、－、－）的动力较弱

• 改变（＋、＋、－）的动力较强

弱平衡网络：不存在（＋、＋、－）三角关系的完全图。

弱平衡网络的特性：节点可分成若干组，组内均为朋友（＋），组间均为敌人（－）

弱结构平衡性质：任意三个节点，均不存在两个正关系边和一个负关系边的连接模式。

证明

我们的思路是：

从一个节点开始，一个个“剥离”满足要求的节点组。

图中考虑任意节点A，将它的朋友和敌人分开，考察朋友组内与跨组的边的性质，暂时不管敌人组内的边的性质。

首先，设包含A及其所有朋友的集合为 X 。 我们将 X 设为第一组。为使下面的证明顺利进行，我们同样设定两个条件：

• A 的所有朋友均互为朋友关系。（这样可以产生互为朋友关系的节点组。）
• A 及其朋友和图中除他们以外的所有人均互为敌人。（基于这个条件，无论剩下的人怎样分组，都可以保证集合 X 中的人与其他组的所有人均互为敌人。）

这两个条件也是很容易证明的。

接下来可以在图中除去包含 A 所有朋友的集合 X ，定义其为第一组。 剩下的节点便形成一个相对更小的具有弱平衡性的完全图。 在该图中找到第二组，再用相同的方法将其从原图中去除，以此类推，直到所有节点都被分到各自的组中为止。

近似平衡的网络

允许网络中有少量三角形不平衡（即可以出现少量“－－－”或“－＋＋”）。在存在少量不平衡三角形的情况下，能否给出网络结构平衡性的一个宏观特性描述？

考虑一个N节点的完全标注网络，断言：

设$0≤ε≤1/8$。若在网络中有$≥1-ε$占比的三角子图是平衡的，则（令$δ=\sqrt[3]{\varepsilon}≤1/2$）：

①至少存在$1-\varepsilon$占比的节点，其中至少有 $1-\varepsilon$占比的节点对互为朋友（+ 边）；或

②可将网络节点划分为两个集合 X 和 Y，满足

• X 中至少有$1-\varepsilon$占比的节点对互为朋友（+ 边）

• Y 中至少有$1-\varepsilon$占比的节点对互为朋友（+ 边）

• X 和 Y 之间的所有节点对中至少有$1-\varepsilon$占比的节点对互为敌人（ - 边）

假设最多有 $ε$ 占比的三角形是不平衡的，则不平衡三角形总数不超过：$\dfrac{εN(N-1)(N-2)}6$

设想每一个节点有一个权重，为它涉及的不平衡三角形个数。于是所有节点（N）的总权重不超过：

$ \dfrac{3εN(N-1)(N-2)}6= \dfrac{εN(N-1)(N-2)}2$

那么一个节点的平均权重最多就是 $\dfrac{ε(N-1)(N-2)}2$

于是，存在一个节点 A ，所涉及不平衡三角形个数$≤\dfrac{ε(N-1)(N-2)}2$，为推导简单起见，放大为$\dfrac{εN^2}2$。

据此我们可以分别证明断言。

非完全图网络平衡性

在这里，我们将平衡定义为没有求改变的动机，也就是说，不会因为增加一条边（关系），出现不可避免的三角不平衡。

要点：允许有些边的缺失

• 表示相应两个节点之间关系不存在或不清楚

此时结构平衡的定义：

• 可以通过补充缺失的边（带符号），成一个平衡网络

  • 这和完全图的平衡定义一致

• 节点可以分成两组（组内边为＋，跨组为－）

  • 这和平衡定理中给出的宏观结论一致（两个阵营）

但这两种判别法都较为复杂。我们期望找到一种更简单的方法。

我们发现，如果存在一个含有奇数个“－”的圈，就没有可能将其节点安排到两个敌对阵营。但对于一个图来说，也不容易。

但注意到，如果一个图的节点能被分成两个阵营，则其中由“＋”互联的连通子图必定完整地属于同一个阵营，我们可以将那样的子图作为一个整体考虑。

那么，原图中存在有奇数个“－”的圈，当且仅当这个简单图中存在长度为奇数的圈。

而，图中存在奇数长度圈，当且仅当广度优先搜索结果中存在同层的边。

小世界

案例：Milgram实验（1967）的计算思维

几百名初始者，要求每人通过转发，争取让一个指定的人收到一封信；

1.向每个初始者提供了目标收信人的姓名、地址、职业等个人信息；

2.规定：参与者只能将信件直接发给相当熟的人，并请他继续转发。因此，如果一个参与者不认识目标收信人，则他不能直接将信寄给他；

结果，约三分之一的信件经过平均六次转发到达了目标。

小世界的含义与短视搜索

• 人类社会网络中，任何两个人之间最短路径长度都不超过“6”（即“六度分隔”）

• 社会网络中，任何两人之间存在短路径的概率很高，而且短视搜索经过短路径的概率也很高

短视搜索（myopic search）

一种有目标的、基于局部信息的网络搜索过程。具有如下特点：

• 每个节点有一个特征（根据需求可有不同定义），任何两个节点之间的特征可以谈差别（特征距离，不同于网络距离）。

• 每个节点仅知道自己和自己网络邻居节点的特征；特别是（因短视），不知道邻居有哪些邻居。

• 搜索过程可看成是信息传递的过程，节点将信息（目标节点的特征）传给离目标节点距离较近（差别较小）的网络邻居节点。

  • 这一思想其实类似于贪心算法，就是尽可能快的到达终点

不过我们看到，“短视搜索”没能走“最短路径”，这其实也是贪心算法的一个广泛存在的问题。

对该现象的研究

形成社会网络的两种基本力量

• 同质性
  • –对应社会网络中的大量的“三角形”（圈子）
• 弱联系
  • –偶然的原因，认识的“远程”朋友。或者说联系并不紧密的社交关系。

从现象到问题

现象：

社会网络中两节点间包含丰富的短路径！

分散搜索能够有效地找到这些短路径！

问题：

• 这具有普遍（规律性）意义吗？

• 为什么社会网络具有这样的性质？它们源于社会网络的哪些基本原理？

  • 可以证明，完全随机的网络没有这样的性质

能否依据社会网络的某些基本原理，说明这种性质的必然性？

那么我们需要一种形式化网络，既体现这两种力量的作用，也便于我们分析其中是否有小世界现象。

Watts-Strogatz模型（r,k）

有许多 “三角形” 和少数随机的 “远程边”。

通过这个网络可以证明：任何两个节点之间存在短路径的概率很高。但同时也存在一些问题，它解释不了Milgram实验的另一个重要现象：短路径不仅存在，而且通过短视搜索能发现。

回顾那个寄信（搜索）过程

每个人被告知：如果不认识目标人，就不能直接寄给他，但要有意识地转发，希望信件的下一站能离目标人近一些。

• 大量实验结果证明这样做是有效的：信件实际走了短路径，说明现实社会网络结构支持这种做法。

• 理论分析在W-S社会网络模型上这样做效果不好：信件走的路径很长，说明该网络模型不支持这种做法。

注意一个很大的问题就是，上面提到的是 “走”，而W-S模型只说了 “存在”

因此需要一种社会网络模型，既反映任意节点对之间短路径的存在性，也支持在这种转发方式下短路径的可实现性。也就是说，网络要有以下特征：

• 两个节点无论相距多远，都要有机会很快接近；

• 两个节点的距离越近，存在直接连接的机会越大

Watts-Strogatz-Kleinberg模型

在Watts-Strogatz模型基础上，让两个节点之间存在随机边的概率与距离的某个幂次（q）成反比 。

• q：控制远程连接的概率随距离递减的强度。

不同q值对随机连接长度的影响

模型的最佳工作参数(q)

理论结果：当q=2时，分散搜索达到最佳效果

仿真实验**：**由几亿个节点组成的网络中，考察不同的q值在分散搜索中的效果

• 对于这种规模的网络，在指数q介于1.5和2.0 之间时搜索效果最佳

• 随着网络规模的扩大，最佳的性能指数q越来越接近2

图中，横轴为参数q，纵轴为从一个节点到达另一个节点所需的平均时间（跳步）。

研究的进展（WSK）带来新问题

模型中的距离，对应现实中的什么？关系的密切性，交往的频繁性，机会的多少？

最好能有真实网络数据验证这样的认识。

利用在线社会网络进行验证

我们只要能验证两人成为朋友的概率与其空间距离的平方成反比即可。

但社会网络中往往由于各种因素人员分布并不平均，所以引入了结合地理距离的节点相对排名。可以看成是节点在地理上均匀分布时区域范围概念的一种推广，“排名”与“距离”有对应关系。这就使我们能一般性地处理节点在地理上分布不均匀的问题了。

于是，给定每个节点的空间位置，就可以算出每个节点对每个节点的相对rank，利用社会网络给出的节点之间的关系数据，计算得出人们有关系的概率随rank递减，那么，我们要验证的是，在均匀地理分布情形，一个节点在任一距离上的朋友数量在同等距离节点总数中的占比随距离平方递减（$\dfrac{1}{d^2}$）。此时等价于要验证，一个节点在任一排名上的朋友（即有连接）数量在同等排名节点总数中的占比随排名递减（$\dfrac{1}{r}$）。

这意味着，大量微观社交关系的建立总体上呈现一种最优化特征，或者说大量人群的随机社会活动相当于一台计算机，完成了一种优化计算（实现了最优参数）。这可以看成是社会计算的一个实例，也是体现社会系统中微观与宏观关系的实例。

人们之间的社会距离：进一步的概念

Watts-Strogatz-Kleinbeig（WSK）网络模型试图反映的社会网络特征

• 由某种“亲近”（相似性）形成的近距离边

• 随机的远距离弱联系边

• 远程相邻节点数量在同距离节点总数中的占比随距离的平方减少

距离，是其中一个关键概念

• 地理空间位置的关系体现最直接的距离概念

• 节点的相对排名也体现了一种距离概念，克服了处理节点在地理空间上分布不均匀情形的困难

社会网络：社团（社交聚点）与距离

一个人可能参加多种社团，社团是两人建立关系的一个基础（社团闭包）

可以想象，两人的亲近程度（ “距离” ）与共处社团的规模有关，越小越近。可以定义 “社会距离”：两人同属最小社团的规模。如同在非均匀分布空间上的处理（建立以人数为基础的排名），也可以直接用这种社会距离作为排名

搜索引擎

有效利用链接关系蕴含的信息，是搜索引擎超越传统信息检索系统、技术进步的最重要标志。

原理

假设查询词 “newspaper” ，左边是与 “newspaper” 字面上相关的网页。右边是它们所指向的网页，得到的 “票数” 表示一定的认可度，如何确定网页的排名。

我们通过 “被指向” 的关系给目标网址进行投票，但也可以通过投票结果反过来评估 “推荐者” 的分量。然后可以在考虑推荐者分量的情况下重新评估网站相对于 “newspaper” 的重要性（相当于加权评分）。这其实形成了一个不断迭代的过程。

网页的“中枢”与“权威”性

万维网中一篇网页具有两方面的属性。 观念：

• 被很多网页指向：权威性高，认可度高

• 指向很多网页：中枢性强

HITS算法：计算网页的权威值（auth）和中枢值（hub）(Hyperlink-Induced Topic Search)

auth(p) 和 hub(p) 的计算方法

• 输入：一个有向图

• 初始化：对于每一个节点p，auth(p)=1，hub(p)=1

步骤：

• 利用中枢值更新权威值

  • 对于每一个节点p，让auth(p)等于指向p的所有节点q的hub(q)之和

• 利用权威值更新中枢值

  • 对于每一个节点p，让hub(p)等于p指向的所有节点q的auth(q)之和

• 重复上述两步若干（k）次

在搜索引擎领域，auth值或hub值高的网页，有时分别称为“权威网页”和“中枢网页”。一篇网页可以兼具二者

注意

• Auth和hub值的意义在于相对大小

• 在每一轮结束后做归一化：值／总和

• 归一化结果随迭代次数趋向于一个极限

  • 即：相继两次迭代的值不变

• 极限与初值无关，即存在 “均衡”

PageRank基本算法

输入：一个有n个节点的网络（有向图），设所有节点的PageRank初始值为1/ n。

• 选择操作的步骤数k

• 对PageRank做k次更新操作，每次使用以下规则：

  • 每个节点将自己当前的PageRank值通过出向链接均分传递给所指向的节点
  • 若没有出向链接，则认为传递给自己（或者说保留）
  • 每个节点以从入向链接获得的（包括可能自传的）所有值之和更新它的PageRank

（这个结果是收敛的，所以不需要k，但如果不收敛，就需要规定迭代次数）

存在问题与解决

PageRank基本算法在某些结构上表现很不好，它不像HITS算法那样需要归一化，但有新问题。

F和G两个节点显得很 “自私”：吸收别人的价值，但不向外传。导致它们最后各自1/2，其他人都0，也就是说这两个节点会吸走整个网络的所有权重。这也显示了共谋（colluding）制造垃圾网页的一个原理

PageRank的同比缩减与统一补偿规则

• 同比缩减

  • 在每次运行基本PageRank更新规则后，将每一节点的PageRank值都乘以一个小于1的比例因子s，0<s<1，经验值在0.8-0.9之间。

• 统一补偿

  • 在每一节点的PageRank值上统一加上$\dfrac{1-s}{n}$。

这样，既维持了“ΣPR=1”的性质，也防止了PR值不恰当地集中到个别节点。但其实仅仅能够缓解。

随机游走：PageRank的另一种等价理解

想象一个人从一篇随机选择的网页开始，随机选择其中的链接浏览到下一篇网页，并不断如此进行，称为“随机游走”。考虑一篇网页X，问：经过k步随机游走到达X的概率是多少？

可以证明：到达X的概率等于运行PageRank基本算法k步得到的值。

随机游走概念稍加修改也可以和同比缩减统一补偿的PageRank等价。