试题 10 图 现在，你选择了一个机构做实地考察。该机构共有 11 个成员｛A，B，C，D，E，F，G，H，I，J， K｝ 。因工作关系，在他们之间形成了一些人员相互交叉的工作组之类的子机构，你得到了这些子 机构的人员信息。 ｛A，B｝ ， ｛A，B，C，D，H｝ ， ｛B，E，F，I，J｝ ， ｛C，D｝ ， ｛C，E，G｝ ， ｛D，H，I，J｝ ， ｛ E， F， G｝ ， ｛ G ， H ， J， K ｝ ， ｛ H ， J， K ｝ 同时，你也得到了这机构人员之间在过去一年里的电子邮件交往数据。 有专家告诉你说，两个人之间的“社会距离”可以用他们共同所属最 小机构的人员数来定义。例如，根据上面的信息，A 和 B 的社会距离 就是 2，等等。同时你也知道，如果两个人之间经常通邮件，就可以 认为他们的关系比较密切（即是“朋友” ） 。于是，你根据电子邮件数 据，并适当考虑了“密切”的含义（例如在一年里每个月至少有一次 通信） ，得到了如下图所示的朋友关系。 现在，你应该可以完成任务了，试试看！为简化起见， （1）只考虑社 会距离≤5 的情形， （2）只计算 A，B，C，D 这 4 个节点的加权平均概率。为准确起见，请把得 到的数据值填到如下表中。 社会距离 成为朋友的概率 2 3 4 5
4
（提示：根据三个投票人的偏好，画个有向图应该有助于看出关键所在。 ）
4. 考虑如教材第 16 章介绍的群集实验和信息级联模型。一个“红多”（R）的罐子中有 2 个红球（r）和 1 个蓝球（b），“蓝多”（B）罐子中有 2 个蓝球（b）和 1 个红球（r）。“红多”或“蓝多”的先验概率 分别都是 0.5。在模型中，当第 1 和第 2 人给出了相同判断后，第 3 人无论摸到什么颜色的小球，都将放 弃自己的私有信号，给出与前面相同的判断，称“级联从第 3 人开始”。问： （ 1） （ 2） 试给出一个“R 级联从第 5 人开始”但第 5 人实际摸到的是蓝球（b）的私有信号和判断序列。 接着上一问。假设第 5 人在给出自己的判断后，将自己的私有信号也悄悄告诉第 6 个人了（后面 的人也观察到 5，6 两人的交流，但不知 5 到底说了什么），于是产生了一点信息扰动。该扰动有 没有可能引起一个从第 11 人开始的 B 级联？如果不可能，给出理由。如果可能，给出一个符合 模型规则的对应私有信号和判断序列。 （提示：可以通过试填下表来帮助思考。将结果写到答题纸上。） 序号 私有信号 公开判断 1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 b R 6 ? ? 7 ? ? 8 ? ? 9 ? ? 10 ? ? 11 ? B 12 ? ?
1
（ 2）
现在，考虑同样的问题，但有稍微不同的个人排序，选举人 3 对后两个选项做了个交换。即
B !1 C !1 D !1 A C !2 D !2 A !2 B D !3 A !3 C !3 B
你能设计一个让 A 胜出的议程吗。如果可以，描述你的设计，如果不行，解释为什么。 （ 3） 现在一般地考虑上面两种情形。对于（1） ，你是不是感觉“让谁胜出，谁就能胜出”？（通过议 程设置） 。对于（2） ，你是否感觉任何议程设置都阻拦不了 C 的胜出？。试对你的回答给予解释。
试题 2 图 3. （此题为慕课试题之一的简单变形） 。 在学习表决机制的时候， 我们讨论了基于少数服从多数规则的表决系 统，在议程设置情况下会受到质疑的问题。下面通过一个简单例子来看它的影响。 （ 1） 设有 4 个选项（A，B，C，D） ，有 3 个投票人（1，2，3） ，分别给出了下列偏好：
第 1 次结束后各自财富量分别为多少？ 第 10 次结束后各自财富量分别为多少？
2
初始 第 1 次后 第 10 次后 甲 100 乙 100 丙 100
要求写出计算过程，在答题纸上给出这样一个表结果（近似到小数点后 1 位数就可以了） 。若感觉算起来
较麻烦，列出由相关基础数字构成的算式也可以。提示：市场只是分配财富，而不创造或消耗财富。
ห้องสมุดไป่ตู้
7. 我们已经比较熟悉一个交通网络结构（如下图） 。其中边上的表达式为一定流量（x）下的通行时间。现在 假设有 3000 辆车（而不是课上讨论的 4000）要从 A 到 B，试给出均衡流与最优流模式。所谓“流模式” ， 指的是 3000 在线路 ACB、ADB、ACDB 上的某种分配， “均衡”就是任何人不可能通过改变路线而有更短 的行驶时间， “最优”就是他们行驶时间的总和不可能在别的流模式下更短。 均衡流模式下 最优流模式下 ACB = ？ ACB = ？ ADB = ？ ADB = ？ ACDB = ？ ACDB = ？
你的回答不能只是“是”或“否” ，需要给出解释。 （说明：由于每个农户占用 1 公里长的河岸，两个相 邻农户之间的距离可以理解为“不超过 1 公里” ，依此类推）
2. 考虑题图所示社会网络， 我们关心两个问题。 （ 1） 请给出图中节点 A， B， C， D， E， F 的聚集系数 （clustering coefficient，定义为一个节点的邻居互为朋友的概率） ； （2）假设：若两个相邻节点有两个（或以上）共同 朋友，则认为他俩之间的边为强关系边，否则就是弱关系边。分别指出节点 A，B，C，D，E，F 是符合还 是违背强三元闭包原理。 （将下表画到答题纸上，给出结果。当然，最好也有过程。 ） 聚集系数 符合/违背 A B C D E F
5. 此题是关于结构变化对 PageRank 值的影响。下图有 4 个节点，考虑基本 PageRank 算法。 （ 1） （ 2） 给出每个节点的 PageRank 值。 现在假设你是节点 A，有在图中增加一条有向边的资源来改进你的 PageRank 值，增加哪一条边将 获益最大？给出增加该边后各节点的 PageRank 值。 （建议：如果你尝试了多种可能，不妨将所有 情况都列举出来） （ 3） 试从图的结构特点解释，为什么增加那一条边，而不是其他边能有最好的效果。
试题 5 图 6. 此题是关于市场对财富的分配问题，对应第 11 周的慕课或教材第 22 章的部分内容。考虑有三个人（甲， 乙，丙）参与赛马（A，B）下注，他们分别有财富和信念如下： （w,a,b）=（100, 0.5, 0.5） ， （100, 0.3, 0.7） ， （100, 0.6, 0.4） 。设三个人都是按照自己的信念下注并在整个过程中不做调整。赛马一共进行了 10 次， 开始 3 次，A 赢，接着 2 次，B 赢，再接着 A 赢了 2 次，最后 3 次 B 赢。赛马场按照无赔赚方式运行。 问： （ 1） （ 2）
试题 9 图 10. 假设你想验证“人们成为朋友的概率与他们的社会距离成反比”这样一种认识。我们知道，相对于每个人 （ A） ，给定一个社会距离，就可以定义一个人群（假设有 G 个人） ，A 和其中有些人交朋友了（假设有 F 个人） ，但没和另一些人交朋友。我们关心交朋友数在总人数中的占比，即 F/G。具体目标（任务）就是 要在下面这坐标系中给出验证数据点（现在图中的点只是示意） ，看它们的走向。其中，横轴是人们的社 会距离（后面有具体定义） 。纵轴表示给定社会距离下一个人朋友数在该距离下人数中的占比（概率） 。由 于在社会网络中涉及到很多人，在具体计算中，这就是人们概率数据的加权平均（等价于在一定社会距离 下交友总数除以该距离下的总人数） 。
B !1 C !1 D !1 A C !2 D !2 A !2 B D !3 A !3 B !3 C
现假设你是负责设计议程的（即，将候选项排成某种顺序，依次俩俩比较，并按照少数服从多数 原则进行删除） 。如果你想让候选项 A 胜出，能通过设计一个议程做到吗。如果可以，描述你的议 程设置，如果不行，解释为什么。
提示：均衡流模式相对比较容易确定。最优流模式的确定有些难度，但有多种方法。其中一种是利用如
下结论：在总流量 r 下的均衡流模式也就给出了在总流量 r/2 下的最优流模式。
试题 7 图 8. 广告位点击率 广告主点击估值 （ a） （ b） （ c） （ d） 9. 考虑下图所示的 4 个网络（a，b，c，d），假设分别在上面做如同课中介绍的网络交换实验。按照所给出 的“结果”、“稳定结果”和“平衡结果”的定义，我们问（从理论上讲）： （1）在网络（a）上是否存在一个稳定结果，如果存在，试给出；如果不存在，为什么？ （2）在网络（b）上是否存在一个平衡结果，如果存在，试给出；如果不存在，为什么？ （3）在网络（c）上是否存在一个稳定结果，如果存在，试给出；如果不存在，为什么？ （4）在网络（d）上是否存在一个平衡结果，如果存在，试给出；如果不存在，为什么？
3
设某搜索引擎有 3 个广告位（a, b, c）出售，三个广告主（x, y, z）有兴趣购买。相关基本数据如下表所示。 a=4 x=7 b=3 y=4 c=1 z=2
广告位如何分配是社会最优？给出相应社会最优值。 假设搜索引擎采用 VCG 定价方式，广告主按估值出价。给出 x, y, z 应该支付的广告位价格（不用 求点击价格） 。 这一组价格是均衡价格吗？ （均衡即没有广告主能通过另一个广告位获得更大差价） 假设搜索引擎采用 GSP 定价方式，试说明此时广告主按估值出价不是均衡。 假设搜索引擎采用 GSP 定价方式，试给出一组广告主的均衡出价。
社会科学中的计算思维方法（04832680）／人群与网络（03131840）期末考试题
2017 年 12 月 27 日，15:10-17:10，一教 101
1. 假设你和一些人类学家一起去某热带雨林做调研，那里有 100 个农户生活在沿 100 公里长河段的一个人 烟稀少的地区。每个农户住在占用河岸 1 公里长的一片土地上，他们正好划分完 100 公里河岸。 （ 1） 假设距离不超过 5 公里的农户之间是强关系，距离在超过 5 公里但不超过 12 公里的农户之间是 弱关系，若两个农户之间距离超过 12 公里，则他们之间不存在任何关系。按照这样的假设，不难 想到可用一个 100 个节点的网络，表达这些农户之间的关系。每个节点代表一农户，有些节点之 间有边，有些则没有，强关系边用 s 标注，弱关系边用 w 标注。问，在上述定义下，是否所有在 这个网络中的节点都符合强三元闭包性质？ （ 2） 现在我们对条件做点改变，还是假设所有距离不超过 5 公里的农户之间是强关系，但距离在 5-8 公里之间的农户之间是弱关系，若距离大于 8 公里，则相关的两个农户之间不存在任何关系。在 这个新情形下，所对应的网络中的节点是否都符合强三元闭包性质？