山东大学众智科学和网络化产业复习笔记

山东大学众智科学复习笔记

写在前面：鹿男神yyds，讲课诙谐有趣，条理清晰，给分可冲，总而言之，众智可冲，题主94，12/160，本文是复习时的总结，希望学弟学妹95

第一章 图论基础

1. 图 = 事物（节点） 联系（边）

2. 同构：图的画法不同，结构上相同，两图同构意味着可以找到一组对应的点，其关系也一致。

3. 邻接矩阵（点集和点集），关联矩阵（点集和边集）

4. 图的直径：任意两个节点之间的最大距离

5. BFS（广度优先搜索）—— 可以用于解决最短路径问题（将节点分层）

6. A ∗ A^* A∗算法——是对BFS求最短路径的优化，BFS是一种乱走，而 A ∗ A^* A∗算法更智能，将曼哈顿距离（点和点之间坐标纵向和横向的距离之和）引入BFS中

7. DFS（深度优先搜索）—— 用于找到所有路径（相比于全排列的包利发，虽然DFS输出的少但仍然是仍然是指数级别的）

8. 佛洛依德算法 —— 一次性求所有节点之间的最短距离（是最简单的最短路算法，比暴力的DFS简单，但复杂度很高为 n 3 n^3 n3）
   算法图解
   

9. 贝尔曼福特算法 —— 单源最短路径问题（给定一个起点s，求其到图中n个点的最短路径)
   优点是边的权值可以为负数。
   算法图解
   
   
   
   
   

10. SPFA = 队列处理 贝尔曼福特算法
    算法步骤
    首先初始化一个数组用以存放源点到每个点的距离（到自己是 0，其他点是无穷），并且把源点加入队列。队列队首元素出列，更新每个节点（队首元素指向的点）到源点的距离，再将队首元素指向的点加入队列。重复操作，直至队列元素为空。

11. Dijkstra（迪杰斯特拉）算法 —— 解决单源最短路径问题（优点是高效且稳定，缺点是只能处理不含有负权边的图）
    算法步骤
    首先初始化数组存放源点到每个点的距离（自己是0，其他是无穷），集合A存放源点，集合B存放剩下的点。更新源点临接的点的距离，在数组中选到源点距离最短的点，加入A集合，并从B集合中删除。更新这一点临接的点的距离，重复上述步骤，直到B集合为空。

12. 在社会网络意义下，某些边具有更加特殊的重要性，比如桥（割边），捷径
    

13. 入度（以该点为终点），出度（以该点为起点）

14. 欧拉通路（从某点出发，遍历整个图，每条边通过且只通过一次）；欧拉回路（起点和终点相同的欧拉通路）

15. 判断一个无向图是否有欧拉回路？—— 图中的点都具有偶数度
    一个无向图是否有欧拉通路？—— 图中有且仅有两个奇数度点，其余点都是偶数度

16. 一个图是二分图，当且仅当其中不存在长度为奇数的圈

第二章 社会网络

1. 快照：某一时刻社会网络图的形状

2. 三元闭包：如果两个互不认识的人有了一个共同的朋友，则他们俩将来成为朋友的可能性会提高。

3. 节点A的聚集系数=A的任意两个朋友之间也是朋友的概率（比如A有三个朋友B,C,D，其中B和C是朋友，B和D，C和D都不是朋友，则节点A的聚集系数为 1 C 3 1 = 1 3 \frac{1}{C_3^1}=\frac{1}{3} C311=31

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

5. 累计度分布函数， P k = ∑ x = k ∞ P ( x ) P_k=\sum\limits_{x=k}^\infty P(x) Pk=x=k∑∞P(x)表示度不小于k的节点的概率分布。

6. 介数：用来描述网络中节点承载最短路径数的能力（不说人话）
   节点（或边）介数=网络中所有最短路径中经过该节点（或边） 的概率之和

7. 介数计算
   
   实例
   步骤1：先从给定点进行BFS进行分层
   
   步骤2：从顶至下从A点向下一层节点发出1个流量
   
   步骤3：从下到上，计算经过每条边的流量（注意，每个点本身有1个流量）
   
   计算过程：K节点有1个流量， 1 2 \frac{1}{2} 21来自I节点， 1 2 \frac{1}{2} 21来自J节点。对于I节点，A到F有两条最短路径，A到G有1条最短路径，故IF边和IG边流量比为2:1，I给K 1 2 \frac{1}{2} 21的流量，本身自己有1个流量，故到I的流量总和为 3 2 \frac{3}{2} 23，故IF流量为1，IG流量为 1 2 \frac{1}{2} 21。

8. 强三元闭包：

   如果A-B和A-C之间的关系为强关系；则B-C之间形成边的可能性很高，如果B-C之间没有关系（强或弱），则称A点违背了强三元闭包原理。

   可以将社交网络中所有关系归为两大类：强关系和弱关系

9. 捷径：若边A-B的端点A和B没有共同的朋友，则称A-B边为捷径。

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

    证明：（反证法）

    已知一社交网络及一节点A，满足强三元闭包性质并至少涉及两个强联系边，假设A和B直接有一捷径相连，且该捷径为强联系。由于A、B之间为捷径，则没有共同朋友，但根据强三元闭包原则，又必须有共同朋友，因此矛盾，因此预期相连的捷径均为弱联系。

第三章 同质性

1. 同质性：我们和自己的朋友往往会有相同点
   每个人的特质分为两种——固有特质（性别，种族，母语等自然属性）和可变特质（外部属性，比如兴趣爱好等）
   社会学一个问题：人们是因为相似才成为朋友还是成为朋友之后变得相似？

2. 同质性的判别基准
   两种节点类型占比分别为p和q，对网络中的任意一条边，两端点不同的概率是2pq（均匀情况），如果实际情况端点不同的比例明显小于2pq，则认为同质性明显。

3. 同质现象的背后机制
   选择性：人们倾向于和他们相似的人成为朋友 -> 社团闭包
   社会化：人们也会因为需要和朋友们保持一致而改变自己的行为 ->会员闭包
   

4. 谢林模型——隔离的一种空间模型
   
   隔离现象并不一定是个人刻意选择的结果。

第四章 正负关系

1. 边的正负性——支持( )与反对(-)；朋友( )与敌人(-)

2. 社会网络中三角关系的稳定性
   

3. 社会网络图的结构平衡：若图中所有三角关系都是平衡的，则该完全图结构平衡。（用定义来判别不方便）

4. 平衡定理：如果一个完全图是平衡的，则要么它的所有节点两两都是朋友，要么它的节点可以被分为两组，一组内的节点两两都是 关系，另一组内的节点两两也都是 关系，而两组之间的节点两两之间都是-关系
   

5. 平衡定理的推广：放松条件 —— 弱平衡网络
   (1) 弱平衡 —— 只是不允许 ±
   (2) 允许边的缺失 —— 考虑非完全图的情况
   可以分成若干组，组内均为 关系，组间均为-关系

6. 近似平衡的网络：允许存在少量三角形不平衡

7. 讨论一个非完全图结构的平衡性
   (1) 可以添加适当的边形成平衡的完全图
   (2) 可以分成两个敌对阵营
   这两种定义等价

8. 非完全图结构的平衡性简单判别
   图是平衡的，当且仅当它不包含奇数个负关系的边的圈。（当且仅当广度优先搜索时不存在同层的边）
   
   
   可以像上图一样去抽象成负关系图
   
   也可以判断图中每个方格中负关系边是否均为偶数

第五章 小世界

1. 六度分隔：人类社会网络中，任何两个人之间的最短路径长度都不超过6

2. 形成社会网络的两种基本力量：同质性，弱关系

3. Watts-Strogatz模型（r,k）
   
   其中，r是同质连接的参数，表示某个节点到那些相距r网格步以内的节点的连接；k是弱关系连接的参数，表示对某个节点，在网络中随机均匀选择k个节点建立弱关系连接。
   疑问：弱连接的概率应该随距离的幂次递减，k值确定弱链接的方式似乎不能反映真实情况

4. Watts-Strogatz-Kleinberg模型
   在Watts-Strogatz模型基础上，让两个节点存在随机边（弱关系）的概率与距离的某个幂次（q）成反比。
   
   理论结果：q=2时，分散搜索达到最佳效果。

第六章 搜索引擎

1. 搜索引擎的基本问题：对用户提交的一个查询，从海量网页集合中将可能满足用户需求的少数结果找出来

2. 网页的中枢与权威性(一篇网页可以兼具两个性质)
   权威性：被很多网页指向
   中枢性：指向很多网页

3. HITS算法：计算网页的权威值(auth)和中枢值(hub)
   计算方法：
   
   示例
   
   
   （上图是运行4轮）
   但是，auth和hub数值会随着迭代次数递增，什么时候收敛？
   数值的意义在于相对大小 —— 在每一轮结束后做归一化（值/总和）
   归一化结果随迭代次数会趋向于一个一个地个极限。

4. PageRank：利用网页间的链接关系计算网页重要性
   示例
   
   算法描述
   

5. PageRank与HITS算法对比
   PageRank不需要归一化
   但有可能出现共谋制造垃圾网页的情况
   
   最后收敛时F和G两个节点的PageRank值会达到 1 2 \frac{1}{2} 21，其他节点为0

6. 改进 —— PageRank的同比缩减与统一补偿
   

7. 随机游走：PageRank的一种等价理解
   问题：考虑一篇网页x，问经过k步随机游走到达x的概率是多少？
   证明：到达x的概率等于运行PageRank基本算法k步得到的值。

第七章 博弈论基础

1. 收益矩阵
   

2. 严格占优策略：对一个参与人来说，若存在一个策略，无论另一个参与人选择何种策略，该策略都是严格最佳的选择，则这个策略称为是前者的严格占优策略。（如上图中“我”的严格占有策略是复习考试）

3. 囚徒困境
   
   

4. 营销战略
   

5. 严格占优策略与不严格占优策略
   严格与不严格的区别，看是＞还是≥
   

6. 纳什均衡：都不改变策略的策略组（互为最佳应对的策略组）
   

7. 鹰鸽博弈
   总共有6个食物，如果是两个鸽子分则一人3个，如果是一只鹰和一只鸽子分则鹰5个鸽子一个，如果是两只鹰分则两人都为0
   
   其中两个纳什均衡为（鹰，鸽）和（鸽，鹰）
   （为什么没有鹰鹰，因为如果鹰鹰，两人都是0，我不如换成鸽，还能拿一个）

8. 零和博弈 —— 不存在纳什均衡的博弈
   

9. 混合策略的引入

10. 混合策略均衡求解：对于某个人而言他的两个策略的收益一致

11. 社会最优：两个人策略收益相加为最大。

12. 社会最优和纳什均衡可能一致。从社会应用的意义上讲，那是均衡和社会最优一致的系统是理想系统。

第八章 博弈论应用

1. 公路交通网
   
   假设有4000辆车，如果同时走A-C或者D-B则所需时间为40 45=85分钟，如果一半司机走A-C-B，一半司机走A-D-B则时间为20 45=65，为纳什均衡

2. 布雷斯悖论
   
   多修了一条路可能情况会更糟，在追求个人利益最大化动机的驱使下，解决社会问题不能仅靠增加资源，还要注意调整结构
   均衡状态下，每个司机的纳什均衡策略都是A-C-D-B，40 40=80>65，增加了一条路情况反倒变得更糟

3. 提高效率的办法
   
   或者收费
   

4. 拍卖
   （1）英式拍卖——增价拍卖
   买方不断出价（提高售价），部分买方逐渐退出，直至剩下一个买方，以当前价格获得商品
   （2）荷兰式拍卖——降价拍卖
   卖方从最高价逐渐降价，直至有第一个买方接受当前价格，获得商品
   （3）首价密封拍卖
   买方同时向卖方提交密封报价，出价最高者以其出价获得商品
   （4）次价密封拍卖
   买方同时向卖方提交密封报价，出价最高者以次价获得商品

5. 考虑次价密封拍卖问题
   次价拍卖鼓励人们说真话，我出价的占优策略即是真实估价，如果我拿到购买权，我会以低于我出价的价格购买商品，赚；如果我没拿到购买权，如果此时我想拿到购买权，需要出价比第一人高，这超乎我对商品的估价，收益为负。因此，出真实估价是占优策略。

6. 匹配问题——形成社会最优
   基于二分图，左侧节点表示一类资源，右侧节点表示另一类资源
   当二分图两边有数目相同的节点，一个完美匹配就是左右节点的配对，使得每个节点都有边连接到另一边节点且不会出现左边两个节点同时连接到右边同一个节点
   引入估值和价格
   
   我们发现对于卖方x和y，商品a带来的收益最大，这就存在一种竞争。
   
   可以通过调整价格来实现最优匹配（市场清仓价格），经济学术语为社会最优
   推广：
   
   一样可以通过调整价格来实现和最大——被竞争商品加价

第九章 广告

1. 广告如何定价——互联网公司给出每个广告位的点击率，供广告主估计广告位价值=点击率$\times$单次点击估值
   
   价格从0、0、0开始加价形成完美匹配

2. GSP：单品次价拍卖机制的一种自然推广
   
   与单品次价拍卖中不同的是，在单品次价拍卖中，每个人的占优策略都是按照自己的估值出价，但是在GSP中可能出现
   
   

3. VCG——为了保持次价拍卖的优良性质
   
   
   
   
   
   

第十章 权力

1. 社交网络中的权力——一个节点具有权力是因为，其他节点对其具有依附性，它具有排他性，饱和性，中心性
   反映在图上：
   依赖性：对于A和C而言，这种价值的来源完全在于B
   排他性：B有能力排除A和C
   饱和性：B比群体中其它成员能获得更多的价值，而一旦饱和之后，B维持这些社会关系的兴趣会降低，它倾向于不满足从一个关系中得到于对方均等的价值份额
   介数：B有高介数，B是网络中多个节点对之间唯一的途径点
   

2. 给定一个图，”结果“是其中的一个匹配（一个点无冲突的边的子集）

3. 结果的稳定与不稳定
   不稳定：存在一条不在结果中的边，其两端的价值之和小于1
   稳定：不存在不稳定的边

4. 两人交互模型——纳什议价解
   

假设A，B两人谈判分配1元钱，但A，B各有一个外部选项x和y

对于x，y的关系有如下两种

（1）x y<=1
这种情况下，A和B才会有可能达成协议，因为，她们都有可能拿到比x（y）更大的收益，如果两人具有同等地位的谈判权力时，即表示两人同意平分剩余的s=1-x-y
则对A来说为x s 2 \frac{s}{2} 2s
则对B来说为y s 2 \frac{s}{2} 2s
为纳什议价解
（2）x y>1
这种请况，谈个毛线

5. 两人交互模型——最后通牒
   同样A和B两人分一元钱，A（通常为具有更高谈判权力的人）提出一个方案，多少给B，剩下归自己；B选择接受或拒绝；如果B接受，拿到收益，如果B拒绝，两人均拿不到钱
   如果B是一个完全理性人，那么不管A提出什么样的方案，都会接受（有总比没有好）
   实际情况，A不会给B很少很少的收益，相对那种极端情况会很温和，”金钱至上“不是人类的典型行为
   结论：现实中出现 1 6 \frac{1}{6} 61和 5 6 \frac{5}{6} 65类似的分配关系就可以认为达到了理论极端情况

6. 网络交换实验——稳定结果
   同样，稳定和不稳定与上文所述概念类似，没有一个节点可以向没和自己达成协议的相邻节点提出一种比现有收益更大的建议即为稳定

7. 网络交换实验——平衡结果
   平衡结果：给定网络其余部分为每个节点提供的最好外部选项，一个交换结果称为平衡的条件是，对匹配的每条边来说，价值的划分体现了两个节点的纳什议价结果
   

图（b）中，对于A和B，其外部选项之和为 0 1 3 = 1 3 0 \frac{1}{3}=\frac{1}{3} 0 31=31，那么两人平分剩下的 2 3 \frac{2}{3} 32，即A为 0 1 3 = 1 3 0 \frac{1}{3}=\frac{1}{3} 0 31=31，B为 1 3 1 3 = 2 3 \frac{1}{3} \frac{1}{3}=\frac{2}{3} 31 31=32。同理C和D也一样满足纳什议价解，故图（b）为一个平衡结果

第十一章 从众和流行

1. 信息级联——当人们放弃了自己的想法与认同别人的看法时，我们认为发生了群集或信息级联

2. 经典问题——判断蓝多罐或红多罐实验
   
   计算过程主要运用贝叶斯公式，我们计算当前学生在拿到蓝（红）球以及知道之前学生拿到的球的颜色的条件下蓝多罐的条件概率
   
   
   
   对于第三个学生而言，即便他抓到了红球，也会说是蓝多罐，即发生了信息级联

3. 有的时候我们需要避免错误的信息级联

4. 幂律——人们发现，拥有k个链入数的网页占比近似地与1/k^2成正比
   

第十二章 新事物扩散

1. 一种经典模型
   
   对网络中的每一条边都转化成一种博弈
   
   对某一确定的节点v，周围有d个邻居，其有占比p的邻居选A，1-p的邻居选B
   如何在A和B两种事物之间进行选择？
   

2. 聚簇——同质性往往可能成为新事物扩散的障碍，新的事物很难从外部进入紧密联系的团体中
   
   密度：计算聚簇中的每个节点，其朋友出现在一个聚簇中的比例；聚簇的密度为这个比例的最小值
   比如上图中，a、b、c、d构成一个聚簇，其中a、b、c的比例都是1，而d的比例是 2 3 \frac{2}{3} 32，所以该聚簇的密度为 2 3 \frac{2}{3} 32

3. 级联定理——描述聚簇和级联的关系
   
   A向B扩散，则 q = b a b q=\frac{b}{a b} q=a bb
   级联定理的简要证明
   

第十三章 信息不对称

1. 制度追求与个人追求的博弈
   个人——一般会在制度下追求自身利益的最大化（我们所讨论的都是“冷血”的理性人，不考虑那些少数利他主义者，我承认是我格局小了）
   制度的设计者——希望达到某种全局最优，不希望有个人逐利情况而破坏制度

2. 外生事件和内生事件；外生事件市场和内生事件市场
   外生事件——该事件如何发生与人们的行为情况无关
   内生事件——该事件如何发生直接取决于人们的行动情况
   外生事件市场——事件发生的概率不受行动者参与的行为影响，比如：彩票（无论多少人去购买彩票，彩票中奖的概率不变），选举（无论多少人投票都会有一个人当选）
   内生事件市场——事件发生的概率受到行动者参与的行为影响，比如：二手车市场（如果人们相信二手车市场的车质量很好，就会倾向于出高价，这样就会促使二手车市场真的有高质量车出卖，车主也就会愿意把自己质量不错的车卖到二手车市场；反之，如果人们不相信二手车市场有好车，那么出价就低，低价就导致车主不愿意将自己的好车卖到二手车市场）
   市场成交与否，在于双方是否达成成交协议，但错误的估值或者信息之间的不对称（信息差）导致原本可以存在的议价空间over

3. 赛马问题——外生事件市场
   
   
   似乎看到——我们会把所有的钱赌在我们直觉中取胜概率大的马上
   这种非“1”即“0”的事件本身就带来一种“风险感”

4. 风险意识——担心坏事出现而带来的损失，宁可放弃一些好事出现带来的利益
   损失厌恶——损失1000元的难过程度要高于得到1000元的高兴程度
   同理，财富增长带来的”好的感受“是随着财富量的增加而减少的
   那我们该如何构建风险意识下的金钱模型呢？

5. 效用函数
   
   $U(w)-U(w-\Delta w)>U(w\Delta w)-U(w)$
   刻画出损失厌恶的一般表达
   针对之前提到的金钱模型，我们有
   

6. 赔付率如何设计——假定赛马场是无赔赚运行（这是一种简单理想情况，实际上马场不可能不赚钱）
   
   
   化简得到
   
   
   每个人对同一局比赛中的胜负情况有自己的判断，比如：A认为甲马获胜概率0.6，乙马获胜概率0.4；但B认为甲马获胜概率为0.3，乙马获胜概率为0.7。我们称这种判断为每个人的”信念“
   通过上式可以看出，如果一个人的下注占收到的注的绝大部分，他的信念对状态价格的影响就越大，进而对计算赔付率的影响也越大

7. 如何制订下注策略保证自己肯定不亏本？——若大家都按照自己的信念下注，且赌场按照上述马场无赔赚方式计算赔付率，一个人有无可能，无论哪匹马赢，都能拿回自己下注的钱，即不亏本？
   答案是可能，如果一个人按照集体信念下注，即，A马赔付率 o A = 2.5 o_A=2.5 oA=2.5，那么我就应该把40%的钱投在A马上
   

8. 内生事件市场的复杂性——信息不对称
   

9. 二手车市场
   
   （1）如果买卖双方信息对称，那么存在议价空间——好车价格在10-12，坏车价格在4-6之间是可以达成交易的
   （2）但是信息不对称
   
   我们作为买家该如何出价？
   对市场上出现的好车占比进行预期，设为h；g为市场中真实的好车占比
   那么买家愿意付的价钱是$12h6（1-h）$
   若$h=0?$
   ——此时买家愿意付6，那些好车（底价10）不会卖，而破车（底价4）全部卖掉，这是出现了一个情况，h真的是0（这个市场一辆好车都没有，其实是因为一辆好车都没成交）
   若$h=g？$
   ——如果代入$h$后的公式$12h6（1-h）$的数值大于等于10，于是所有车都成交，此时$h$真的等于$g$
   ——如果如果代入$h$后的公式$12h6（1-h）$的数值小于10，于是好车没成交，破车全部成交，此时的$h$等于0，没达到预期

10. 阿克罗夫柠檬市场（柠檬比喻质量很差的商品）
    一个小栗子
    

11. 如何减少信息不对称影响
    

第十四章 表决

1. 表决——通过众人的投票，形成对事物的群体判断
   表决的三个重要因素
   （1）投票规则和制度
   （2）被表决对象
   （3）众人

2. 偏好关系——讨论理性表决的基础
   
   偏好关系的性质——完备性和传递性
   

3. 群体偏好——群体表决者对被表决者形成的一个偏好全序
   
   问题：每位表决者都给出了完备且传递的偏好关系，如果组合在一起，一定能形成一个全序嘛？
   反例
   

4. 孔多塞悖论
   合理的个体行为 合理的聚合方式—>不合理的群体结论
   一个小栗子
   
   我们是否可以通过调整聚合方式来寻找合理的群体结论？

5. 逐一胜出
   
   但是好像顺序会影响最终的结果

6. 积分制
   
   一个小栗子
   
   但是这样的积分制真的合理吗？
   
   
   似乎我们很难找到一种适用于所有场景的聚合方式

7. 对聚合方式的两个合理要求
   -趋同性：对任意两个候选项X和Y，如果所有个体都偏好X，那么群体排序中的结果也应该是偏好X
   -独立于无关项：群体对侯选项X和Y的排序，仅取决于个体对它们的偏好，与个体对其他侯选项的看法无关（X和Y在群体排序中的结果，不能因为某一个体调整了某个候选项Z的相对位置而改变）

8. 阿罗不可能定理
   在三个或更多侯选项的条件下，任何多于2人参与的表决系统，都不可能同时满足
   （1）趋同性
   （2）IIA（独立于无关选项）
   （3）非独裁性

9. 单峰偏好
   
   
   定理：在一个奇数个被表决对象的表决情况中，如果所有选举人的排序都满足单峰偏好，那么按照少数服从多数规则两两比较候选项产生的群体偏好是完备且传递的
   
   
   一个全是图的小栗子
   还是刚才候选项为{A,B,C,D,E}的那个例子
   
   
   （1）选择群体序中最大的——在目前最大的三个里选择中间项（序列为A,B,C），也就是B，然后将B删去
   
   （2）选择群体序次大的——同理选C（这时的序列是A,C,C），然后删去C
   
   （3）选择群体序第三大的——同理选A（这时的序列是A,A,D），然后删去A
   
   然后就一目了然了
   但是，为什么这么做是对的？

10. 中位项定理
    
    认为 X 3 X_3 X3第一的那个人，他的偏好序列中， X 2 X_2 X2相比于 X 1 X_1 X1，与 X 3 X_3 X3更近，根据单峰偏好知，他认为 X 2 > X 1 X_2>X_1 X2>X1

证明题汇总

1. 若A节点满足强三元闭包，且A至少有两个强关系邻居，则与A相连的任何捷径必定意味着弱关系
   证明：
   强三元闭包：若节点A与B，A与C都有强关系，那么B与C至少有弱关系
   捷径：两节点A和B没有共同朋友，称为A-B边为捷径
   已知一社交网络及一节点A，满足强三元闭包性质并至少涉及两个强联系边，假设A和B直接有一捷径相连，且该捷径为强联系。由于A、B之间为捷径，则没有共同朋友，但根据强三元闭包原则，又必须有共同朋友，因此矛盾，因此预期相连的捷径均为弱联系

2. 证明次价拍卖鼓励人们真实报价
   证明：
   当人们真实报价时，即按照自己的估值报价时，有两种情况
   第一种，拿到交易权
   如果报价比真实估价高（增加报价），仍然会拿到交易权，收益都是真实估价减去第二位的出价，收益不变
   如果报价比真实估价低（降低报价），如果比第二位出价高，那么仍然会拿到交易权，收益是真实估价减去第二位的出价，收益不变；如果比第二位出价低，拿不到交易权，收益为0
   第二种，没拿到交易权
   如果报价比真实估价高（增加报价），如果比第一位出价高，虽然拿到交易权，但是成交价格高于估价，收益为负；如果没有第一位出价高，拿不到交易权，收益为0
   如果报价比真实估价低（降低报价），仍然拿不到交易权，收益为0
   综上，次价拍卖中人们真实报价是最佳应对

3. 阿罗不可能定理
   在三个或更多侯选项的条件下，任何多于2人参与的表决系统，都不可能同时满足
   （1）趋同性
   （2）IIA（独立于无关选项）
   （3）非独裁性

4. 解释同质现象
   
   同质性是指我们和自己的朋友往往会有相同点，我们经常讨论的问题是，人们是和与自己相似的人成为朋友还是与自己的朋友变得相似，用中国的古话说，是近朱者赤、近墨者黑还是物以类聚、人以群分。在社交网络图中，设不同类型端点的占比为p和q，通过计算边端点类型不同的概率2pq和真实概率做比较，如果真实概率小于2pq，则可以说明该社交网络有同质现象。该图中，白色节点比例为 2 3 \frac{2}{3} 32，红色节点比例为 1 3 \frac{1}{3} 31， 2 p q = 4 9 2pq=\frac{4}{9} 2pq=94，而真实的端点类型不同的边有5条，比例为 5 18 \frac{5}{18} 185， 5 18 < 4 9 \frac{5}{18}<\frac{4}{9} 185<94，故认为该图可以说明同质现象。

5. 证明网格模式中的每一个小方格都稳定，则整体的大结构也稳定
   证明：
   考虑一个圈涉及的边的条数，总是由若干方块构成，每个方块四条边，其中偶数条负关系边，设为2k。一个圈中涉及的边有周长边和内部边，其中设周长边中负关系边数为m，内部边的负关系边数为n。那么，由于内部边为两个方格共享，于是有$2k=m2n$，于是m一定是偶数，因此整体一定平衡稳定

6. 中位项定理的证明
   证明：
   欲证明中位项定理的正确性，即要说明，每一次相继取出的中间项，在少数服从多数的原则下，比其他所有还剩下的候选项都要大
   设 L 1 , L 2 , L 3 . . . L m L_1,L_2,L_3...L_m L1,L2,L3...Lm为个体的单峰偏好排序表，设 L i ( 1 ) L_i(1) Li(1)为对应个体偏好排序表中第一个也就是最大的元素
   将 L 1 ( 1 ) , L 2 ( 1 ) . . . L m ( 1 ) L_1(1),L_2(1)...L_m(1) L1(1),L2(1)...Lm(1)按照从小到大的特征序排序，不妨设为 X 1 . . . X i . . . X m X_1...X_i...X_m X1...Xi...Xm，其中 X i X_i Xi是序列中的中位项，只需证明 X i X_i Xi和其他（m-1）项相比都能以少数服从多数胜出。不失一般性，我们只讨论 X i X_i Xi和左边项相比的情况， X i X_i Xi都至少获得右边所有项的支持，加上自己的一票，获得了大于一半人的票数。在取走第一个中间项后的情况同理，于是证明出中位项定理的正确性。

写在后面：在发布时，感觉本文总结稍微有些粗，强烈建议众智平时一定要认真听课（划重点），不要临时抱佛脚，22年考试难度不大，但是考察很细，很多复习时容易忽略的名词解释（甚至ppt上也无），本文也只是参考，还是建议学弟学妹要自己总结，好啦，旧事重提，祝学弟学妹众智95

这篇好文章是转载于：学新通技术网