社会计算（一）

第一部分图论与社会网络

一、图论概述

基本概念

概念名称	概念解释
距离	两个节点间最短路径的长度
连通分量	无向图的极大连通子图
强连通分量	有向图的极大连通子图
桥	具有特别性质的边，删除它后其两个端点之间就不再有路
捷径	也是一种边，删除它后两个端点之间的距离至少为3
二部图	节点可分为两组，且组内没有边

二、三元闭包

1.三元闭包的解释

（1）解释

如果两人在社会网络中有一个共同的朋友，则他们俩将来成为朋友的可能性提高。

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

（2）成因

三元闭包是社会网络中由于网络结构自身的特性促成新边形成的基本力量，它背后有机会、信任和动机三个方面的原因。

（3）三元闭包的衡量标准——节点的聚集系数

$节点的聚集系数与相邻的节点之间边的实际数与相邻节点对的个数$

$与相邻节点对的个数的邻接节点数$

2.强三元闭包理论

（1）强三元闭包性质

若A有两个强关系邻居B和C，但B-C之间没有任何关系（S或W），则称节点A违背了强三元闭包原理。如果节点A没有违背强三元闭包原理，则称节点A符合强三元闭包原理。

一个节点是否符合强三元闭包也是严格定义的，即每个节点要么“符合”，要么“违背。

（2）捷径和弱关系

推论：若节点A符合强三元闭包，且至少有两个强关系邻居，则与A相连的任何捷径必定意味着是弱关系。

证明：如果是强关系，那根据强三元闭包原理。这两个之间必然有边相连，不符合捷径的定义。（反证法）

（3）邻里重叠度

$的邻里重叠度与、均为邻居的节点数与、中至少一个为邻居的节点数$

捷径即为邻里重叠度为0的边。（原因：若有同时与(A,B)相邻的节点，则删除(A,B)边后距离只增加1，不符合捷径的定义）

3.闭包、结构洞

（1）弱关系的强度

为什么对找工作提供有效帮助的人更多只是一般熟人，而不是亲密朋友？

对于亲密的朋友，你们所在的闭包往往相似，所以覆盖面比较小。

对于一般熟人，其所在的闭包和你所在的闭包的重合度较小。

（2）嵌入性与结构洞

社会网络的基本意象为：用桥（或者捷径，或者邻里重叠度很低的边，弱关系）连接起来的相对比较密集互连的节点群。

边的嵌入性：两个端点共同邻居的数量

结构洞：存在网络中两个或多个没有紧密联系的节点集合之间的“空地”。

4.图划分算法

三、同质性

1.同质现象

假设有一个社会网络，其中有占比是男性，有占比是女性。一条跨性别节点的边（一个端点为男性，一个端点为女性）概率为。

如果跨性别边所占比显著低于，则就有同质性现象。

2.社会归属网络

社会归属网络是一种二部图。

会员闭包：人和社团因与同一个人联系而产生联系。(c)
社团闭包：人和人因参加同一个社团而产生联系。(b)

写出社会归属网络中的社团闭包，转换成边，可画出到社会归属网络的投影图。
（该投影图是一种社会网络，只展现人与人间的关系）

3.隔离——谢林模型

四、社会网络中关系的正负及其平衡

1.平衡网络

一个平衡的三角关系要么3+（如(a)），要么1+，2-（如(c)），否则结构不平衡。
一个（完全）图是平衡的，当且仅当其中所有三角形都是平衡的。
平衡定理：如果一个完全图是平衡的，则要么它的所有节点两两都是朋友，要么它的节点可以被分为两组，X和Y，其中X组内的节点两两都是朋友，Y组内的节点两两也都是朋友，而X组中的每个节点都是Y组中每个节点的敌人。

2.弱平衡网络

弱平衡网络：不存在2+，1-（如(b)）三角关系的标注完全图。
特性：节点可分成若干组，组内均为朋友（+），组间均为敌人（-）。

五、网络关系中的权力

1.网络交换实验

一般来说，邻居越多，权力越大；邻居的权力越小，权力越大。

2.纳什议价解

假设网络中两个节点的外部选项可以量化为和，在关系上划分1的预期结果：

均分，即A：，B：。

3.稳定结果与平衡结果

不稳定因素：不在结果（匹配）中的一条边，其两端节点的价值之和小于1。
平衡结果：结果中匹配的每条边上的价值划分都满足纳什议价解。

匹配中的边是指达成交易的边，未达成交易的边不在匹配中。

第二部分博弈论

六、博弈论基础

1.几个基本概念与纳什均衡

（1）最佳应对与严格最佳应对

针对参与人乙的策略，若参与人甲采用策略产生的收益大于或等于自己的任何其他策略，则称参与人甲的策略是参与人乙的策略的最佳应对。即：

其中，是参与人甲除外的任何其他策略。

当其中的大于等于变为严格大于，即为严格最佳应对。

（2）占优策略与严格占优策略

参与人甲的占优策略，是指该策略对于参与人乙的每一策略都是最佳应对。

参与人甲的严格占优策略，是指该占优策略对于参与人乙的每一策略都是严格最佳应对。

（3）纳什均衡

假定参与人甲选择策略，参与人乙选择策略。若是的最佳应对，且也是的最佳应对，则称策略组是一个纳什均衡。

在均衡状态，任何参与人都没有动机（理性的动机）去换另一种策略。可以被看成是一种信念上的均衡。

2.简单博弈的推理

如果两参与人都有严格占优策略，则可以预计他们均会采取严格占优策略。

如果只有一个人参与严格占优策略，则这个参与人会采取严格占优策略，而另一方会采取此策略的最佳应对。

如果不存在严格占优策略，则应寻找纳什均衡：

如果存在一个纳什均衡，则就对应合理结果
如果存在多个，就应该需要额外信息辅助决策

如果不存在纳什均衡，则应考虑混合策略。

3.混合策略的纳什均衡

考虑参与人将以一定的概率分布在不同策略间进行选择，一种分布对应一个“混合策略”。混合策略与纯策略相对。

设参与人1采用概率执行，执行，则：

若参与人2采用，则其收益期望是：

若参与人2采用，则其收益期望是：

则求解混合策略的纳什均衡为：

由此求解出，用对称的方法求解出参与人2的。

4.帕累托最优与社会最优

一个策略组被称为帕累托最优，若不存在其他策略组满足：所有参与者得到至少和目前一样高的回报，且至少有一个参与者会得到严格较高的回报。

一组策略选择是社会最优，若它使参与者的回报之和（总收益）最大。

社会最优一定是帕累托最优。