北京大学通选课《人群与网络》期末复习要点.pdf

WEEK1

1.概念理解：距离、嵌入性、小世界、三元闭包、强联系、弱联系、聚集系数、捷径

2.利用广度优先搜索求距离。

3.求连通分量：广度遍历。注意：连通分量是无向图，强连通分量是有向图。

4.计算聚集系数。

5.根据三元闭包来生成新的边。

6.计算嵌入性。

WEEK2√

1.同质性与同构性的区分。

2.区分固有特征和可变特征

3.计算图是否存在同质性。

4.区分、判断三种闭包:三元、会员、社团。注意分析关系时，如果题目没说明，不要只在

一期中发展关系，要考虑时间推移产生的新边的影响。

5.用矩阵乘法判断闭包。

6.改变一个节点颜色的资源，改变哪一个能最大限度降低同质性。——改变一个颜色的节

点，使得增加的异色边最多。

WEEK3√

1.概念理解：六度分隔、WS模型、WSK模型、排名与距离与聚集指数之间的关系。

2.找短视搜索路径。注意：短视搜索指的是只能看到自己相连的点与搜索目标的“地理”

距离，而看不到它的短路径。区分短视搜索路径和最短路径。

3.聚集指数越小，搜索所需要的次数越少。

4.理解三元闭包如何减小了搜索的范围。如：一个学校里面，三元闭包的影响就比较大，

若学校里的每个人均列出他的五个好友，与你距离两步之遥的好友个数最多可能为25

个，这样的可能性是很小的。

5.注意：rank的定义：包括中心点、不包括自己、包括比自己近的、不包括和自己一样近

的。

WEEK4√

1.找强连通分量：正向搜索+反向搜索。

2.求万维网领结结构的IN,OUT,SCC。

a)SCC(包含已知节点的强连通分量的点集)=FS∩BS。

b)IN=BS–SCC;OUT=FS–SCC.

3.找添加多少条边让一个图变成强连通图——合并强联通分量为一个点。设入度为0的节

点数为p，出度为0的节点数为q，那么最少需要添加的边数为max(p,q).

4.HITS算法:初始值为1；计算各个结点的auth和hub值；归一化优化。

注意：每一轮先更新权威值，再更新中枢值，中枢值的更新以更新过的权威值为依据。

所谓归一化，就是按算法要求更新了节点的权威值后，将每个权威值同时除以它们的和，更新

了节点的中枢值以后，将每个中枢值同时除以它们的和。哪个选项的结果是正确的：

☆计算多步递归结果时，归一化不一定要每更新一轮就进行一次，最后统一进行归一化

得到的效果是一样的。

5.PageRank算法：初始值1/n;均分点值；缺陷；同比缩减、统一补偿。

a)同比缩减：每次运行完PageRank以后都将每一个节点的PR值乘以一个比例因子

s，(0s1)。一般在0.8到0.9之间。

b)统一补偿：在每一个节点的PR值上加上(1-s)/n。

6.通过解方程计算HITS和PageRank的均衡值。

7.通过增减边来改变SCC,IN,OUT.关键：合并强连通分量为一个点。

WEEK5

1.概念理解：博弈三要素、最佳应对、占优策略、纳什均衡

2.计算：纯策略均衡和混合策略均衡。

WEEK6

1.概念理解：布雷斯悖论、几种拍卖方式和它们各自的应用

2.计算布雷斯悖论下不同的纳什均衡交通图。

3.分析：在首价密封拍卖中，买家不真实报价可能获得额外的收益；但是在次价密封拍卖

中，买家不真实的报价不会获得额外收益。（首价密封拍卖最好的方式是稍微降低出价）

4.根据估值矩阵构建市场清仓价格。（市场清仓价格：使得市场上的所有商品恰好得以完

美匹配）。

注意：构建市场清仓价格时，最后要统一约减，使得市场最低价为0.

5.拓展的英式拍卖和荷兰式拍卖。

6.在次价密封拍卖中，不按估价出价的人会对自己和其他人的利益都造成负的影响。

WEEK7

1.概念理解：点击收入、点击率、广告位的估价

2.注意：广告位拍卖中，广告主的出价都是点击价，但是最后的VCG和GSP价格都是指广

告位的价格=点击率*点击价。

3.VCG机制：使得所有估值总和最大。

a)求VCG价格。

b)VCG价格是社会最优。

c)真实报价是占优策略。

d)注意：VCG价格挖掉的是广告主、不是广告位。

4.GSP拍卖：次价拍卖的推广。

a)GSP机制产生的价格不一定是纳什均衡。