SDU考试特别提醒：概念不是关键，只需理解透重点概念（如三元闭包、纳什均衡、柠檬市场等），以算法应用为主。
2021考点：三元闭包、清仓价格、GSP&VCG、布雷斯悖论、贝叶斯定理、博弈、拍卖、信息级联。
每章都有涉及（除了图论、流行病、网络级联），纳什均衡一定要悟透了灵活运用，有时间多看应用题。
第一章：图论基础
同构：画法不同，但本质上（结构上）相同的两个或多个图。
路径、最短路径、距离、直径、最短路问题
BFS：图上的广度优先搜索，能有效地将图中节点分层，有利于讨论图的一些性质
DFS：图上的深度优先搜索，是一种“盲目”的搜索算法，优化后有A*算法（利用曼哈顿距离）
Floyd-Warshall（弗洛伊德）算法：一次性求出所有节点对的最短距离，动态规划，
Bellman-Ford算法：单源最短路，每次更新时用相邻点到目标点的距离更新当前点到目标点的距离
SPFA算法：优先队列优化的Bellman-Ford，先让起点入队并尝试更新所有邻居，被更新的邻居也入队，直至队列为空。
Dijkstra算法：单源最短路，贪心思想，每次选最短路径已被确定的点来更新其他点，依次更新完所有点。
连通分量：无向图中一个点集，其中所有节点都是连通的，且不包含在其他连通分量中。
超大连通分量：全球可能不是一个连通图，但会同时存在多个含有巨量节点的连通分量，成为超大连通分量。
桥（割边）：一条边，去掉该边会使一个连通分量分裂为两个更小的连通分量。
割点：一个点，去掉该点会使一个连通分量分裂为两个或更多的连通分量。
捷径：连接A、B的一条边，且A和B没有共同的相邻节点。去掉捷径会使AB间的距离至少增加2
强连通分量：有向图中一个点集，其中所有节点都能相互到达，且点集尽可能大。
出度、入度、度数、奇点、偶点、欧拉回路
欧拉回路：从图中某点出发，遍历整个图，每条边通过且只通过一次，且最终回到起点。
存在条件：对于无向图，当且仅当存在0个或2个度为奇数的点；对于有向图，当且仅当每个点的出度等于入度，或仅两个点的度数分别为-1和1。
二分图匹配：把无向图G=(V, E)分为两个集合V1、V2，所有的边都在集合间，而集合内部无边。每条边都会产生一个匹配，每个点至多参与一个匹配。找出一种连边方案使得匹配数最大。
二分图判断（能否完全匹配）：染色法
二分图匹配：最大流、匈牙利算法
第二章：社会网络
形成社会网络的两种基本力量：同质性、弱联系
三元闭包：在一个社交圈内，如果两个互不相识的人有了一个共同的朋友，则他们俩将来成为朋友的可能性提高。
节点聚集系数：A的聚集系数 = A的任意两个朋友之间也是朋友的概率（即邻居间朋友对的个数除以总对数）
社会网络的统计特征：度分布（度为k的节点所占比例）、平均路径长度（距离平均值）、网络直径（最长路径长度）、–平均直径（至少90%的互连节点对之间的距离均不超过的最小值）、介数（网络中所有最短路径中经过该点或边的概率）
介数的计算：从一个节点开始BFS，将节点分层；确定该点到其他点的最短路径条数；计算从该点经最短路向其他每个节点发送1单位流量时，经过每条边的流量。对每个点重复上述过程，累计每条边的流量再/2，即得每条边的介数。
强三元闭包：将关系（边）细分为强关系、弱关系。如果A-C和B-C都是强关系，则AB之间有边（无论强弱）的概率很高；否则称C违反了强三元闭包原理。
断言：若节点A符合强三元闭包，且至少有两个强关系邻居，则与A相连的任何捷径必定是弱关系。
弱关系在不同的节点群中提供更关键的连接。
两人关系的强度如何与是否有共同朋友相关。共同朋友越多，关系强度越高（邻里重叠度越高）。
边的嵌入性：这条边的两个端点的共同邻居的数量。结构洞：多个群体的唯一交汇点。
图划分：将一个庞大的社会网络划分为多个“联系紧密的节点群”
Girvan-Newman方法：依次删除介数最大的边
同质性：以性别为例，假设p占比是男性，q占比是女性，如果跨性别边所占比例显著低于2pq，就有同质性的迹象。
隔离：同质性的影响和结果（谢林模型，研究不变特征与可变特征的联系）
正负性：对图中的每条边加上标记，正（+）边表示友好，负（-）边表示敌对。
结构平衡：在完全图中，取3个节点及其相连的3条边，如果其中有1或3个+，称此三角关系为平衡关系，如果其中有0或2个+，称为不平衡关系。如果图中所有的三角都是平衡关系，称这个图是平衡的。
平衡定理：如果一个标记的完全图是平衡的，要么它的所有节点两两是朋友，要么它的节点可以分为两个组X, Y，其中每个组内的节点两两是朋友，而X组中的每个节点都是Y组中每个节点的敌人。
弱平衡网络：与平衡网络相比，只有“+ + -”不被允许（允许“- - -”）
特性：如果一个完全图是弱平衡的，它的节点可分成多个组，同一组内任意两点为朋友，不同组间任意两点为敌人。
非完全网络的结构平衡：方法一是通过添加边，并根据平衡关系的要求为边标记，补充成一个平衡网络。方法二是根据节点间的友好和敌对关系将节点分为两组。
断言：一个标注图是平衡的，当且仅当它不包含有奇数个负关系边的圈，即它是一个二分图。
简约图：只考虑正关系边，将图中的连通分量视为一个个超节点（即合成一个点），点之间通过负关系边连接，形成简约图。简约图中如果有奇数条边形成的圈，则原图是不平衡的（可以通过BFS找出这样的圈）。
第三章：社会网络应用
小世界与六度分隔理论
小世界：人类社会网络中，任何两个人之间最短路径长度都不超过6，且短视搜索几乎总能沿最短路径前进
Watts-Strogatz模型：节点环路中以远距离弱关系的形式引入少量随机性（即与随机点连边），就足以使世界变“小”。
分散搜索：网格中遍布节点， 每个节点在r个网格步内与其他节点互相连接，每个节点有k条随机边，以到该节点距离衰减的方式生成。对于两个节点u和v，设其网格距离为，聚集指数为q，用与成正比的概率产生u到v的边。
Watts-Strogatz模型对应q=0的情况。
在大型网络规模下，分散搜索当q=2时最有效（此时随机连接遵循反平方分布）
朋友关系排名：用排名取代物理距离。从节点u出发，节点v的排名记作，等于其他比v更接近u的节点数。
每次以与成正比的概率选择节点v创建连接，称其为基于指数p的朋友关系排名。p常取1.
流行病学与线粒体夏娃
社会网络→接触网络（其中一人患病时，患病者会以一定概率把疾病传染给对方），行为或思想与病毒同理。
分支过程模型
当一个体患病时，以一个独立的概率p传染给遇到的每个人（有连边的个体），形成第一个疫情波；被传染的人再以概率p传给其遇到的每个人，形成第二个疫情波……
基本再生数：一个单一体引发新病体数的期望值。假设模型中每人遇到k个人，每人受感染概率为p，.
如果＜1，疾病在有限的疫情波后必定消失；如果＞1，疾病持续在每一波以大于0的概率至少传染一个人。
因此，当接近于1（门槛值）时，社会应该付出加倍的努力来降低基本再生数，从而消灭疾病。
SIR模型
在分支过程的基础上，每个节点有三个阶段：易感期S、传染期I、结束期R（终身免疫）。
最初，一些节点处在传染期，所有其他节点处在易感期；传染期的节点在固定步骤期间具有传染性，每一步都有概率p传染给易感期的邻居；经过传染步骤后，该节点进入结束期，不再传染，也不易感（S—I—R）
SIS模型
与SIR类似，其不同点是：节点离开传染期后立刻进入易感期，即终身易感（S—I—S）
SIRS模型
振荡模型，节点离开传染期后进入暂时免疫期，暂时免疫期结束后又进入易感期（S—I—R—S）
小世界接触网络
SIRS模型会在网络中一些局部区域产生振荡，并随着大量集中感染产生一块块免疫区域。
在整个网络范围内，由于网络丰富的远程连接，不同地区的疾病爆发在大致相同的时间内呼应，产生大规模振荡。
假设远程连接的概率是c（弱连接），根据c值的不同会产生不同的结果（c越大，振荡越强烈）
短暂接触：给每条边加上时限。同一人与其他人的接触时间重叠称为并发，会导致某些疾病传播更活跃。
线粒体夏娃：现代所有人类有同一个母系祖先。将世系自下往上看，每个个体等概率选择一个前代个体作为自己的父母，当两个体恰巧选择同一个前代时，就合并为同一个世系。因此在有限的时间内所有世系会合并为一个单一世系。
第四章：博弈
见《众智科学》：博弈
第五章：拍卖
拍卖的基本假设：每个竞拍者对拍卖品有一个独立的估值（竞拍者认为该商品的真实价值），如果出售价不高于估值，竞拍者会接受并购买，否则就不会购买。
拍卖的类型
降价拍卖与首价密封拍卖类似，增价拍卖与次价密封拍卖类似。
次价拍卖
设是竞拍者对商品的真实估值，出价是的函数，如果不是中标价，的回报为0；如果是中标价，是第二高（也可能与第一并列）的竞标价，的回报为.
在密封次价拍卖中，每个竞拍者的占优策略是以真实估值出价。
首价拍卖
如果不是中标价，的回报为0；如果是中标价，的回报为.
此时真实估值出价不再是占优策略（因为会导致回报为0），最好的出价方式是略微降低出价，但难以找到最佳点。
全支付拍卖
如果不是中标价，的回报为；如果是中标价，的回报为.
一般以低于真实估值的价格出价，但也要在出价较高（更有可能赢）和出价较低（降低花费）之间平衡。
二分图匹配
以学生选宿舍为例，如果学生数和宿舍数相同（节点数相等），每个学生都能进入想要的宿舍，且没有两个学生进入同一个宿舍，称为完美匹配。如果有节点组限制了完美匹配的形成（如三个学生一共只有两个想要的宿舍，必有一人不能进入想要的宿舍），称该节点组（三个学生）为受限组。
匹配定理：如果一个两边节点相等的二分图无法形成完美匹配，一定包含一个受限组。
最优分配：寻求尽可能高的分配方案质量（价值和最大）。
偏好卖家图：假设卖家以价格出售房子，如果买家以该价格买到此房，买家的回报就是她对该房的估值.
买家为了最大化回报，会选择使最大的卖家购买（称为偏好卖家）。如果有多个符合条件的，买家会任选其中一个。如果所有的都会令回报小于0，买家不会购买任何房子。
对于一组价格，在每个买家和偏好卖家之间连一条边，定义一个偏好卖家图
市场清仓价格：如果一组价格形成的偏好卖家图有完美匹配，那么该价格就是一组市场清仓价格。
存在性：对于任何买家估值的组合，总存在一组市场清仓价格。
最优性：对于一组市场清仓价格，偏好卖家图中的该完美匹配使估值总和在所有配对中达到最高。
最优性'：一组市场清仓价格及其对应的偏好卖家图中的完美匹配，能产生买家和卖家回报总和的最大可能值。
清仓拍卖过程
每轮开始时，卖家有一个固定价格，最小为0
构造偏好卖家图，检查是否有完美匹配，有则结束过程，目前价为市场清仓价格
若无完美匹配，使图中所有受限买家对应卖家的价格+1（只有1个偏好卖家也可以算作受限买家）
如有需要，可以统一降低卖家价格至最低价格为0
用新的价格开始新一轮拍卖
拍卖一定会结束
对于当前价格集合，定义买家的势能是他当前可能获得的最大回报，卖家的势能是他当前给出的价格，拍卖的势能是所有参与者的势能之和。初始时卖家势能和为0，买家势能为其最大估值，拍卖的势能是. 每一轮价格变化后，如果价格减少了，卖家减少的势能会被买家提升的势能抵消；如果价格提高了，受限买家组中所有买家的势能降低，而卖家的势能提高。由于受限买家的数量多于卖家，因此整体势能至少降低1。又由于买家和卖家的势能在每一轮开始时都至少为0，因此拍卖的势能最低降至0，于是拍卖一定会在轮内结束。
只要制定恰当的价格，人们在追求个体最优的过程中能够达成社会最优（市场的力量）
第六章：搜索与广告
万维网中的一个网页，如果被很多网页指向，说明权威性高；如果指向很多网页，说明中枢性高。
权威值更新规则：对于每个网页p，以所有指向该网页的网页中枢值之和更新该网页的权威值.
中枢值更新规则：对于每个网页p，以它指向的所有网页权威值之和更新该网页的中枢值.
设所有网页的中枢值和权威值均为1，设定一个运行次数k，执行k次上述更新，对权威值和中枢值进行归一化处理。除极少数退化情况外，中枢值和权威值将收敛于稳定的极限值。
网页排名PageRank
对有n个节点的网络，设所有节点的网页排名初始值为1/n. 选定运行次数为k. 对网页排名作k次更新操作，每次更新使用以下规则：
基本网页更新规则：每个网页均等地将自己当前的排名值分给所有向外的链接，传递给所指向的网页。每个页面以其获得的所有网页排名值的总和更新自己的网页排名。
PageRank算法不需要额外的归一化，但会被“自私”的节点（出度为0，吸收其他节点的排名值）干扰。为解决这一问题，引入同比缩减和统一补偿规则，既能维持排名性质，也能避免排名值被不恰当地集中到少数点上。
同比缩减是在每次运行更新规则后，将每一节点的排名值*s（0<s<1)。统一补偿是给所有节点的排名值增加(1-s)/n.
随机游走
从随机一个网页开始，每次随机地选择一个链接并点击（如果没有链接就留在原地），称为随机游走。
断言：经过k步随机游走到达网页X的概率就是网页X运行k次网页排名更新后得到的排名值。
与搜索相关的广告业
对于点击支付，可以构造匹配市场如图所示：
其中价格由卖方（互联网公司）制定，与点击率正相关；买方对广告的估值是点击率*点击收入，买方获得的回报是点击率*(点击收入-价格)。将每个买方连接到能得到最高回报的卖方，形成偏好卖家图，根据清仓拍卖过程求出清仓价格。
GSP机制
GSP是广义次价拍卖，该机制简单地将次价拍卖推广到多物品，将广告位i分给出价排在第i位的广告商，其支付价格是排在(i+1)位的价格。在GSP机制中，真实报价不一定构成纳什均衡，而且可能存在多个均衡，有些无法达到估值总和最高。
买家可能通过适当降低自己的报价，放弃高档商品，而以更低的价格得到中档商品，增加回报。
可见GSP机制是有缺陷的，而VCG机制弥补了这一缺陷。
VCG原理：广告商报告点击收入，卖方按收入递减的顺序将广告位分配给广告商，点击价格与报价相同。
VCG原则：每个个体支付他对其他所有个体造成的总“损失”，即该个体不出现时其他个体得到的价值增量总和，这一点类似次价拍卖。买方j为获得商品i支付的VCG价格 . 这个原则能鼓励真实出价。
VCG机制
买方宣布他们对商品的估价（可以是不真实的）
卖方依据估价选择一个最优分配方案，使得每个买方获得的商品估价总和最高。
每个买方支付相应的VCG价格，如果买方j获得商品i，则应支付.
VCG价格是个性价格，是买方与商品共同决定的；而上文的市场清仓价格是通告价格，任何买方都可以该价格购买商品。
断言：在VCG机制中，真实报价是每个买方的占优策略，并且在所有的完美匹配中，这样能使估值总和最高。
第七章：权力，市场与网络
在网络中，不同位置的节点能够拥有不同的权力。如果假定网络中每条边上都有$1，而该边的两个端点需要对这$1的分配达成协议，且每个节点只能与至多一个点达成协议，则越是处于中心位置的节点（依赖性、排他性、介数等）权力越大，就越有可能得到有利的分配份额。
纳什议价解
假设网络中有一2-节点路径，A, B两点分$1。若A有外部选项x（即如果A对B给他的份额不满意，就可以放弃与B谈判而获得x），B有外部选项y，且（如果x+y>1，A和B就不可能达成协议），则纳什议价结果为：
对A来说是 ，对B来说是 . （s=1-x-y）
最后通牒博弈
即使中间结点拥有全部权力，一般也无法将其对手的份额挤压为0. 尤其在真人实验中，严格的金钱最大化原则并不合适。
稳定结果
稳定性：不存在节点X，它可以对节点Y提出一种划分使得X和Y都能得到更多价值，从而将Y从旧的协议中偷出来。
不稳定性：存在不在匹配结果中的一条边，其两个端点的价值之和小于1. 网络包含不稳定性时是不稳定的。
平衡结果
对于匹配中的每条边来说，价值的划分体现了两个节点的纳什议价结果。
平衡结果一定是稳定结果，反之不然。
外生事件：事件如何发生的概率不受人们行动影响，如预测市场（聚合人们对未来事件的预测，形成群体的一个认识）。
赌客下赌注时主要考虑两个因素，赔付率和对待风险的态度。
在下赌注时，人们通常倾向于选择期望回报更大的选项。但对回报的感受取决于已有的财富量，拥有的财富越多，人们就会对风险越敏感，对财富增长越不敏感。可以令效用函数，即财富倍增给人带来的感觉是一样的，而与具体增加的财富数量无关。此时再下赌注就应当选择效用函数的期望更大的选项。
通过推导，得出结论：投在A上的财富占比最好等于A取胜的概率。在这样的效用函数下，投注策略与赔付率无关。
赌客根据自己的信念下注
状态价格：赔付率的倒数，实际上是群众的平均信念，且随着群众规模扩大，这个平均值收敛到真实的概率。
如果随大流（信念=状态价格），则总不会吃亏。
内生事件：事件如何发生直接取决于人们的选择，如布雷斯悖论。
内生市场的复杂性源于信息不对称，如二手市场，卖家比买家更了解真实情况。信息弱势的一方会在考虑到另一方有充分信息的情形下形成对交易商品质量的预期，并按照预期决定自己愿意支付（接受）的期望价格。
以二手车市场为例，假设市场有好坏两种车，好车售价不低于10，买家愿意支付至多12；坏车售价不低于4，买家愿意支付至多6. 设买家都预期好车占比为h，并因此同意支付，若大家认为h=0，则只愿意支付6，此时好车都不同意出售，买家只能买到坏车，也就是h=0实现了。若大家认为1>h>=2/3，即支付至少10，所有的车就都能卖出去了，h>=2/3也实现了。但如果大家认为0<h<2/3，只愿意支付不到10的价格，好车仍不会出售，买家只能买到坏车，结果就不符合预期了。
劣币驱逐良币（柠檬市场）
市场上的商品有不同的质量等级，买家也有不同的质量预期，且买卖双方对不同质量的商品有不同的价格底线。由于信息不对称性，买家只能给出一个价格，卖家根据底价决定是否完成交易。若质量较差商品占比太高，买卖底价差太小，会导致市场失效，买家对市场的预期下降，而这种下降会导致买家更加无法买到高质量的商品，预期进一步下降，形成柠檬市场。
为避免柠檬市场，需要尽量减少信息不对称的影响：第三方权威评价、买家评价、建立品牌、学历学位等。
第八章：信息级联
贝叶斯定理
信息级联的形成
假设不透明罐子里放有三个除颜色外完全相同的小球，实验者告诉大家这个罐子可能是红多罐（2红1蓝），也可能是蓝多罐（2蓝1红）。学生们依次随机取出球，背对其他人查看球的颜色，然后向大家宣布他对罐子的猜测（红多R或蓝多B）。可能出现以下状况：
信号 b, r, b, r, r, b, b, r
宣布 B R B R R B B R
信号 b, r, b, r, r, r, b, r
宣布 B R B R R R R R ←信息级联已经形成
当两种信号个数相差2（连续三个信号相同）时，会形成信息级联。
未形成级联时，个体作出的判断与信号（他实际拿到的小球）一致；信息级联形成后，个体忽略自身信号从众。
信息级联形成的要素：足够多的参与人、依次决策、部分私有信号、缺乏明确公共信息、有限（2个）选项、理性决策
信息级联的脆弱性：即使级联已经持续了很长时间，仍旧可以被一个很小的力量推翻
信息级联的应用：新产品广告、房屋拍卖等，造成大家都在使用的感觉，只展示级联结果而避免展示私有信息
打破信息级联：有影响的个体、打破依次决策、公布私有信息
幂律分布
一个随着k值的某个固定幂次递减的函数称为一个幂律。
正态分布描述许多独立的随机选择最终形成的平均状态，幂律分布源自人群决策结果的信息反馈。
拥有k个链入数的网页占比近似地与成正比。
基于人们倾向于复制他人做过的决定，给出一个在网页之间创建链接的简单模型：
网页按顺序被创建，标记为1,2,3,...N. 当网页j被创建时，有p的概率会从已经创建的网页中随机选择一个网页i并以链接指向i；有(1-p)的概率会从已经创建的网页中随机选择一个网页i并以链接指向i指向的网页。
以上述规则更新网页会出现“富者更富”规则，因为网页i的流行度（被指向）增加的概率与i当前的流行度成正比。
如果历史重演多次，每次的流行度都会服从幂律分布，但最流行的对象未必保持一致。
流行度模型与信息级联有相似之处，但前者包含众多可能的选项，且参与者的信息非常有限，且复制的基础是模仿前人，可能不那么理性。
“长尾”现象
作为k的函数，多少品种的流行度至少是k？
将流行度曲线的x轴和y轴互换，曲线的尾部会慢慢向右下降，形成“长尾”（Zipf图）
网络级联——网络中新事物的扩散
网络中有A,B两类事物，A是旧事物，是大部分人的选择；B是新事物，只吸引了少数年轻人。
假设：每个人只采纳A或B之一，相邻两人如都采用A，则得到回报w；如都采用B，则得到回报v. 如采用不同事物，回报为0. 切换事物的过程没有成本。
上述可以表达为一个博弈：
扩展到一个网络，设点a有n个邻居，在某一时刻，若占比p的邻居选择A，占比(1-p)的邻居选择B，则a选A的回报为 ，a选B的回报为. 显然点a应当选择回报更大的那一种。
阻挡网络级联的因素：聚簇（“抱团”）
称一个节点集为密度为r的聚簇，若其中每个节点都至少有占比为r的邻居属于这个聚簇。
设网络中一个初用节点集采用B，其他网络节点采用A，每个点更换为B的门槛值为p. 如果存在密度至少为1-p的聚簇，则无法形成网络级联（充要条件）。
异质门槛值
社会网络中每个人对A和B的估值不同，对于节点v定义一个回报 表示v配合其他节点采用A得到的回报，表示v配合其他节点采用B得到的回报。此时点v与其相邻节点w的博弈演变为下表所示：
本文地址：http://lianchengexpo.xrbh.cn/quote/8197.html 迅博思语资讯 http://lianchengexpo.xrbh.cn/ , 查看更多