北航社会计算作业答案.pdf-资料库

第1页 / 共40页

第2页 / 共40页

第3页 / 共40页

第4页 / 共40页

第5页 / 共40页

第6页 / 共40页

第7页 / 共40页

第8页 / 共40页

《网络、群体与市场－揭示高度互联世界的行为原理与效应机制》习题参考答案第 2 章 2.1 图论作为有效建模工具的原因之一即在于它的灵活性。许多大型系统都可以通过图论语言来总结该系统的属性，并用来系统地研究其结构。本章练习的第一部分，主要讨论上述过程的一个实例，该实例将引入一个关键节点（pivotal node）的概念。首先，第 2 章所讲的两节点间最短路径可能为该节点间的最短距离。对与节点组 Y 和 Z，若 X 存在于 Y 和 Z 间所有最短路径，则称 X 为 Y 和 Z 间的关键节点（X 与 Y 和 Z 均不重合）。例如：在图 2. 1 中，节点 B 是节点对 A 和 C、A 和 D 的关键节点（注意： B 并不是节点对 D 和 E 的关键节点，因为 D 和 E 间存在两条不同的最短路径，而其中的一条（包含 C 和 F）并不通过 B。由此可见，B 并不存在于 D 和 E 间的所有最短路径）。另一个例子是：节点 D 并非图中任意节点对的关键节点。图 2. 1 练习 2.1 示意图。节点 B 是两个节点对的关键节点：节点对 A 和 C，以及 A 和 D，而节点 D 并非图中任意节点对的关键节点（1）请列举一个图例，使其满足以下条件：该图中每个节点均为至少一个节点对的关键节点。请就你的答案给出合理解释。（2）请列举一个图例，使其满足以下条件：该图中每个节点均为至少两个节点对的关键节点。请就你的答案给出合理解释。 1

（3）请列举一个图例，满足以下条件：该图中包含至少 4 个节点，并存在一个节点 X，它是图中所有不包括含 X 的节点对的关键节点。请就你的答案给出合理解释。参考答案：两个节点 Y 和 Z 之间的关键节点 X：X 存在于 Y 和 Z 之间的所有最短路径上。（1）一个节点数大于或等于 5 的圈图（V-W-X-Y-Z-V）满足“每个节点均为至少一个节点对的关键节点”的要求。例如，对于 5-圈，W 和 Y 之间的最短路径只有一条（长度为 2），经过 X。其他类推。（2）一个节点数大于或等于 7 的圈图（R-U-V-W-X-Y-Z-R）满足“每个节点均为至少两个节点对的关键节点”的要求。例如，对于 7-圈，W 和 Y 之间的最短路径只有一条（长度为 2），经过 X，V 和 Y 之间的最短路径只有一条（长度为 3），也经过 X。其他类推。（3）以 X 为中心的 5 节点“星图”（A-X，B-X，C-X，D-X）满足要求，此时 X 就是每个节点对的关键节点，任何两个节点之间的路径都经过它。 2.2 接下来的问题中，我们将引入一组相关定义，以帮助我们规范化“一些节点可在网络中起到“看门”的作用”这一概念。第一个定义内容如下：对于节点 X，若存在另两个节点 Y 和 Z，使 Y 和 Z 间的所有路径均通过 X，则称 X 为门卫（gatekeeper）。举例来说，图 2. 2 中，节点 A 即为一个看门节点，因为存在于节点 B 到 E 的所有路径中（除此之外，A 还存在于其他节点组间的所有路径中，比如 D 和 E 等）。该定义具有一个“普遍”特点：因其需要我们纵观整个图，以确定某一特定节点是门卫。相比之下，另一“本地化”版本将上述定义的条件限定于只需观察一个节点的相邻节点。我们将之规范化，即有以下定义：我们定义一个节点 X 为局部门卫，若其满足以下条件：存在节点 X 的两个相邻节点，称为 Y 和 Z，其中间没有任意边相连。（换句话说，X 为局部门卫的前提是，至少存在 X 的两个相邻节点 Y 和 Z，满足 Y 和 Z 分别有边与 X 相连，但彼此并不相连的条件。）例如图 2. 2 所示，节点 A 同时满足门卫和局部门卫的条件，而节点 D 仅为局部门卫，却不满足门卫的条件。（注意：尽管 D 的两个相邻节点 B 和 C 彼此并没有边相连，但对于包括 B 和 C 在内的所有节点组之间，均存在一条不包含 D 的路径。） 2

图 2. 2 练习 2.2 示意图。节点 A 是门卫，节点 D 是局部门卫而非门卫综上所述，我们目前得到两个定义：门卫和局部门卫。每当我们讨论新的数学定义时，一个有效帮助我们理解定义的方法通常是先从典型例子入手，随后将之理论化，再尝试将该理论应用于其他例子。让我们按以上方法来讨论下面几道问题：（1）给出一个图例（包含解释），满足条件：该图中超过一半的节点为门卫；（2）给出一个图例（包含解释），满足条件：该图中所有节点均不是门卫，但均为局部门卫。参考答案：按照给出的定义，“门卫”和“局部门卫”的概念，可以与教材中的“桥” 与“捷径”类比。“门卫”亦即这样的节点，删除它，至少有两个原来之间存在路径的节点不再有路径；“局部门卫”则是这样的节点，删除它，至少有两个原来是其邻居的节点之间的距离不小于 2。根据这个理解，就有（1）5 个节点的路径图，A-B-C-D-E，其中 3 个节点（B、C、D）是门卫；（2）4 个节点的回路图，A-B-C-D-A，显然都不是门卫，因为任意两个节点之间都有两条独立的通路，而且每个节点都是局部门卫，因为任何一个节点的两个邻居节点之间都不存在一条边。 2.3 当我们试图就一个已知图中节点间的距离寻找一个单一的综合衡量标准时，有两个原始数量值得我们考虑。一个是直径，我们定义它为图中任意两节点之间的最大距离；另一个是平均距离，我们定义它为图中所有节点对间的平均距离。 3

在许多图中，上述两个数量在数值上非常接近。但以下的两个例子却可能是例外：（1）请给出一个直径比平均距离大三倍的图例；（2）请根据你解答问题（a）的方法，说明你可以通过改变某一特定因数的大小，来控制直径比平均距离大的倍数。（换句话说，对于任意数字 c，你能否构造一个图，使其直径比平均距离大 c 倍？）参考答案：在给定点和边资源的情况下，路径图直径最短（1）。于是我们可以一般地考虑这个问题，考虑一个图表示 1 nK 的 + ， P m 1)m - 的“辫子”，整个图有n m+ mP 共有一个节点。不难看出，这个图的直径是 m 。下面考虑 n + 个节点的完全图加上一条长度为( 1)m - ，完全图 += G K 个节点， 1nK + 和 mP 的直径最长( 1n “平均距离”，分三个部分， nK 内部的节点之间（此时不算与 mP 的共同节点）， mP 内部的节点之间，以及均距离分别为 1， 1 m + 3 nK 和 m + 2 和 mP 的节点之间。稍作计算，可知这三部分的平 1 ，也就是独立于n 。对于 1m > ，总体的平均距离大于 1，记为 A。在给定m 的情况下，增加n ，A 将减小，且趋于 1。于是当我们考虑构造一个直径大约是平均距离C 倍的图的时候，可以利用上述结论，即取 m C= + ，然后选择足够大的 n ，使得， 1 1 < < A C 1 + C ，也就是 CA C < + < + 。（下面是一个详细推导） C ( 1) A 1 因图中一共有 n m+ 个节点，于是有个节点对。分三种情况：（1） 1nK + 除去那个共有节点，即 Kn 中所有节点对的距离都为 1，一共有。（2） mP 的 m 个节点（包括与 Kn ＋1 共有的那个），一共有个距离，和为之间的平均距离也就是 1 m + 3 和为，它们，与n 无关。（3） nK 和 mP 之间，则有nm 个距离，，它们之间的平均距离为 1 m + 2 ，也是与 n 无关。也就是说，我们要考察平均距离 4

1m = 成立，从图的构造中，这也是 1m > ， A A 随 n 趋向于 1。也就是说，我们可以 m C= + ，则总有合适 1 1 1) A 与直径 m 的关系（最右边的等号仅当显然的）。我们看到，当给定构造直径是平均距离任意倍数（C ）的图，例如，取的n ，使第 3 章 < + < + 。 CA C C ( 3.1 用两三句话解释什么是三元闭包，以及它在社会网络形成中的作用。如果有必要，可以用图例来说明。参考答案三元闭包指的是在社会网络中，若当前还不是朋友的两个人有了一个共同朋友，则他们俩成为朋友的可能性增加。三元闭包是社会网络中由于网络结构自身的特性促成新边形成的基本力量，它背后有机会、信任和动机三个方面的原因。 3.3 如图 3. 2 所示的社会网络，每条边的属性不是强联系就是弱联系，哪些节点满足第 3 章中讲述的强三元闭包特性？哪些不满足这个特性？请解释你的答案。图 3. 1 用于练习 3.3 的图，其中的边带有强弱联系标记 5

参考答案 A、B、D 满足强三元闭包性质，C、E 不满足强三元闭包性质。理由是： C-B，C-E 之间是强关系，但 B，E 间却无边连接，故 C 不满足强三元闭包性质； E-D，E-C 之间是强关系，但 C，D 间却无边连接，故 E 不满足强三元闭包性质。 3.5 下图所示的社会网络中，每条边都标注了关系的强度（S 表示强关系，W 表示弱关系）。试指出其中哪些节点满足教材第 3 章中介绍的强三元闭包性质？哪些不满足该性质？请解释你的答案。图 3. 2 用于练习 3.5 的图，其中的边带有强弱联系标记参考答案： A，B，D，E 都满足强三元闭包性质；C 不满足，因为它和邻居 A 和 E 都是强关系，但 A 和 E 之间没有任何关系，B 和 E 也是 C 的两个强关系邻居，但它们之间也没有任何关系。第 4 章 4.1 讨论下如图 4. 1 所示的社会网络。假设此社会网络是在一定时间点，观察一定族群个体间的友谊关系。另外假设我们在将来的某个时间节点会再观察此 6

网络。根据三元闭包的理论，有什么新的关联会很可能出现？（比如，那些节点对，目前之间没连接，但当我们再次观察时，会有很到可能建立了连接？）请简述你的答案理由。图 4. 1 用于练习 4.1 的图，其中是节点表示人，边表示人们在某一时间友谊关系的图参考答案在下一个观察时间之前，B-D 之间的关联（边）形成的可能性比较高，因为 B 和 D 有 3 个共同的朋友（相邻节点），其他节点对都只有两个共同的朋友。 4.2 根据一个表示人们参与不同社会活动的二部归属图，研究者有时会创建一种仅仅涉及到相关人员的“投影图”，其中两个人之间有一条边，当且仅当他们参与了相同的社会活动。（a）画出与图 4. 2 对应的投影图，其中的节点应该是在图 4. 2 中的 7 位人员，且如果两个人在某一董事会共职，则他们之间应该有连接。（b）试给出一个例子，涉及两个不同的归属网络，它们有同样的人群，不同的社团关系，但所导致的投影图是相同的。该例子说明信息可能在从完整归属图到投影图过程中被“丢失”。 7

图 4. 2 用于练习 4.2 的图。截至 2009 年，各个公司管理层与个体之间的相互联系参考答案基本认识就是：从社会活动出发，一个社会活动若有k 个人参与，则在他们之间形成一完全子图，共 ( k k - 1) / 2 条边。（a）对于这个例子来说，结果就是 John-Shirley ， John-Arthur ， Shirley-Arthur ， Arthur-Al ， Arthur-Steve ， Arthur-Andrea，Al-Steve，Al-Andrea，Steve-Andrea，Andrea-Susan （b）有两个层次的可能导致不同的归属图但相同的投影图。第一，让社会活动交换。例如在图 4. 2 中，让 Shirley 和 Arthur 都关联到 Amazon，同时取消他们和 Google 的关联，我们得到另一个归属图，与图 4. 2 有相同的投影图。这种情形实际上是图的重新标注，属于简单情形。另一种考虑更具实质性，利用在形成投影图中完全子图的重叠部分。例如基于归属图 4. 2，让 Al 也和 Disney 有关联，得到不同的归属图，但对应的投影图与图 4. 2 的投影图一样。这里的 8

资料库

北航社会计算作业答案.pdf

相关推荐

课程资源

热门标签

最新资料