文章目录
-
- 教材版本
- 第1章：概述
- 第2章：图论
- 第3章：强联系和弱联系
- 第4章：网络及其存在的环境
-
- 4.1 同质性
- 4.2 同质现象背后的机制：选择与社会影响
- 4.5 隔离的一种空间模型
- 第5章：正关系和负关系
-
- 5.1 结构平衡
- 5.2 结构平衡网络的特性
- 5.4 结构平衡的一种弱形式
- 第20章：小世界现象
-
- 20.1 六度分隔
- 20.2 结构与随机性
- 20.3 分散搜索
- 20.4 构建分散搜索过程的模型
- 20.5 实验分析以及推广模型
- 第14章：链接分析和网络搜索
-
- 14.2 利用中枢和权威进行链接分析
- 14.3 网页排名
- 第6章：博弈
-
- 6.1 何为博弈
- 6.2 博弈中的行为推理
- 6.3 最佳应对和占优策略
- 6.4 纳什均衡
- 6.5 协调博弈 6.6 鹰鸽博弈
- 6.7 混合策略
- 第8章：网络流量的博弈论模型
-
- 8.1 均衡的流量
- 8.2 布雷斯悖论
- 第9章：拍卖
-
- 9.1 拍卖的类型
- 9.2 何时拍卖适宜
- 9.4 次价拍卖
- 第10章：匹配市场
-
- 10.1 二部图与完美匹配
- 10.2 估值和最优分配
- 10.3 价格与市场清仓性质
- 10.4 构造一组清仓价格
- 第15章：商业支持的搜索市场
-
- 15.1 与搜索行为关联的广告业
- 15.2 广告业作为一种匹配市场
- 15.3 在匹配市场中鼓励真实出价：VCG原理
- 15.4 分析VCG机制：真实报价是一个占优策略
- 15.5 广义次价拍卖
- 第12章：网络中的议价与权力
-
- 12.1 在社会网络中的权力
- 12.2 权力于交换的实验性研究
- 12.3 网络交换实验的结果
- 12.5 两人交互模型：纳什议价解
- 12.6 两人交互模型：最后通牒
- 12.7 网络交互模型：稳定结果
- 12.8 网络交换模型：平衡结果
- 第16章：信息级联
-
- 16.1 随大流现象
- 16.2 一个简单的群集实验
- 16.3 贝叶斯规则：非确定性决策模型
- 16.4 在群集实验中运用贝氏规则
- 16.5 一种简单通用的级联模型
- 16.6 依次抉择与级联
- 第18章：幂律和富者更富现象
-
- 18.1 流行度成为一种网络现象
- 18.2 幂律
- 第19章：网络中的级联行为
-
- 19.1 网络中的传播
- 19.2 基于网络构建传播模型
- 19.3 级联与聚簇
- 19.5 基本级联模型的扩展
- 19.6 知识、门槛值和集体行动
- 第22章：市场与信息
-
- 22.1 外生事件的市场
- 22.2 赛马、博彩和信念
- 22.5 内生事件的市场
- 22.6 柠檬市场
- 第21章：流行病学
-
- 21.1 疾病和传播网络
- 21.2 分支过程
- 21.3 SIR流行病模型
- 21.4 SIS流行病模型
- 21.5 同步性
- 21.6 短暂接触与并发的危险
- 21.7 宗谱、基因遗传和线粒体夏娃
教材版本
《网络、群体与市场》——揭示高度互联世界的行为原理与效应机制
清华大学出版社
本笔记按照老师讲课顺序整理，并不按课本上章节的顺序
第1章：概述
应用数学和计算机的基础知识，讨论社会学和经济学的基本问题
涉及的主要内容
- 图论与社会网络
- 制度及其聚合问题
- 流行性的起源，物以类聚，从众心理，三元闭包，阿罗不可能定理，布雷斯悖论等等
第2章：图论
首先明确几个概念
图 = 事物 + 联系
图的同构：画法不同，但本质上结构相同
图在计算机中的表示：使用邻接矩阵或关联矩阵
两点间的路径，最短路径
两点间的距离
图的直径：任意两点的最大距离
图的广度优先搜索（BFS）的过程，要求掌握
使用BFS算法求最短路的方法
A*算法
深度优先搜索DFS算法
弗洛伊德算法
贝尔曼——福特算法
迪杰斯特拉算法
连通的概念，连通分量，割点，割边
有向图的入度和出度
强连通图，强连通分量
欧拉回路
二分图（二部图），二分图的判断（染色法）
匈牙利算法
总的来说，第一章图论部分的重点不多，主要是要熟悉图这种类型，掌握基本概念，因为之后的内容很多和图有关，需要用到这一部分的知识
第3章：强联系和弱联系
1.三元闭包：如果两个互不认识的人有了一个共同的朋友，则他们将来称为朋友的可能性提升
拓展：两个人拥有的共同朋友越多，则两个人成为朋友的可能性越高
2.节点聚集系数
节点聚集系数是社交网络的关系的简单测度
节点A的节点聚集系数定义为A的任意两个朋友彼此之间也是朋友的概率
节点A的节点聚集系数 = 与A相邻的节点之间边的实际数与A相邻节点对的个数之比
8.邻里重叠度
定义一条边A-B的邻里重叠度如下式
邻里重叠度 = 与A、B均为邻居的节点数 / 与A、B中至少一个为邻居的节点数
第4章：网络及其存在的环境
4.1 同质性
影响社交网络结构最基本的概念之一是同质性，即我们和自己的朋友间往往会有相同的特点
社交网路中互相连接的人倾向于相似
每个人的特质可分为两种
- 固有特质：性别，种族，母语
- 可变特质：居住区，专长，偏好
量化同质性
社交网络中同质性判断的一个测度
我们如何判断在一个社交网络中，同质性的程度/p>
4.2 同质现象背后的机制：选择与社会影响
同质性对社会演化网络的影响
通常情况下，人们倾向于和他们相似的人之间形成友谊，这通常被称为选择性，即人们根据相似的特征选择朋友
但于此同时，另一个过程也在发挥作用，人们会因为需要和朋友们保持一致而改变自己的行为。这个过程被称为社会化和社会影响。
由于网络中存在的社会联系影响力节点个体的特征。社会影响可以看作是和选择相反的观念：在选择中，个体的特征主导网络连接的形成。社会影响可以看成是与选择相反的观念。在选择中，个体的特征主导网络连接的形成，但在社会影响中，已存在的社会网络连接将会改变人们（可变）的特征
了解并知晓三元闭包，会员闭包，社团闭包的形成，区分这三种闭包
对同质性的理解
第5章：正关系和负关系
5.1 结构平衡
正关系和负关系的基本模型。假设一群人构成一个社会网络，其中每个人都互相了解，于是每对节点间都有一条边。
这样的网络叫做完全图。
用+和-标识每条边，+表示两个端点是朋友，-表示两个端点是敌人
而既有边的正负属性可以影响未知或未来的关系
社会网络中三角关系的稳定性
5.4 结构平衡的一种弱形式
1.弱平衡网络的特性
弱平衡结构性质：任意三个节点，均不存在两个正关系边和一个负关系边的连接模式
仅不允许出现两正一负的情况
弱平衡网络的特性：如果一个标记的完全图是弱平衡的，则它的节点可分成不同的组，并且满足同一组中任意两个节点互为朋友，不同组之间任意两个节点互为敌人
但是使用上面的定义有不足之处，这个不足之处是，由于情况多变，有时我们很难判断一个标注图是否平衡，会出现判断困难
一个简单判别的方法
一个标注图是平衡的，当且仅当它不包含有奇数个负关系的边的圈
（由于每经过一个负关系的边，就要改变一次集合，因此如果一个圈有奇数个负关系，那么起始点的集合就会出现紊乱，则该图绝对不平衡）
课堂作业
该模型为网络中每个节点创建两种连接，一种是纯粹的同质性连接，一种是弱关系连接。
同质连接是某个节点到那些相距r网格步以内的节点的连接，r是常数
对于另一个常数k，每个节点也形成到网络中k个其它节点的连接，这些节点被均匀分布地选择
在这样的网络图上，可以证明：任何两个节点之间存在短路径的概率很高
20.3 分散搜索
考虑小世界实验中的第二个观点：人们实际上能够找到到指定目标的短路径
一个分散搜索模型
20.4 构建分散搜索过程的模型
1.扩展的网络模型
为模型引入一个衡量远距离弱连接跨越距离的“尺度”。网络中的节点像以前一样，每个节点在r个网络步内与其它节点相互连接
定义聚集系数q，对于两个节点v和w，设d(v,w)表示它们之间的网格步数（即一个节点沿着到相邻节点的边到另一个节点的步数）
要产生一条由v发出的随机边，用与1/d(v,m)^q的正比的概率产生由v连接到w的随机边
具体的不用掌握了，课件上也没有
第14章：链接分析和网络搜索
14.2 利用中枢和权威进行链接分析
当向搜索引擎中查询一个词时，是什么决定了网页的排名/p>
1.由链入链接投票选择
链接是影响网页排名的第一个重要因素：利用链接评估一个主题相关网页的权威性，是针对一个主题其它网页通过链接到一个网页而赋予这个网页的认可程度
即，一个网页的链入数越高，说明排名应该越靠前
2.一种发现列表网页的技术
无标记的圆表示与查询词“报纸”相关的网页样本，右边是对应网页得到的票数（认可度）
4.中枢网页和权威网页
针对一个查询得到的那些认可度较高的突出网页称为该查询的权威网页
对于每个网页p，可以使用网页权威值（auth（p））和网页中枢值（hub（p））来估算网页本身的价值
设两者初值均为1
权威更新规则：对于每个网页p，以所有指向该网页的网页中枢值之和更新这个网页的权威值
中枢更新规则：对于每个网页p，以所有该网页指向的网页权威值之和更新这个网页的中枢值
计算权威值和中枢值的算法
- 设所有网页中枢值和权威值为1
- 选择一个运行次数k
- 执行k次中枢-权威更新操作，具体操作过程如下
- 首先运行权威更新规则，利用当前中枢值更新当前网络的权威值
- 然后运行中枢更新规则，用权威更新产生的值对网页中枢值进行更新
- 最后，中枢值和权威值会变得很大，但我们值关心它的相对值大小，为此将把它们进行归一化处理，将每个权威值除以所有权威值的总和，每个中枢值除以所有中枢值的总和。
当k值趋近于无限大时，经过归一化处理后的中枢和权威值也收敛于稳定的极限值。
ppt上有个小练习，考前试一试
课堂练习，考试前练一练
2.网页排名的均衡值、
当更新步数k趋于无穷大时，所有节点的网页排名值收敛于相应的极限值
3.按比例缩放网页排名
PageRank算法有时会导致一种不好的情况，即慢泄漏
随机游走：一种网页排名的等价定义
一个人从一篇随机选择的网页开始，随机选择其中的链接浏览到下一篇网页，并不断如此进行，称为“随机游走”
考虑一篇网页X：经过k步随机游走到达X的概率是多少/p>
可以证明：到达X的概率等于运行PageRank算法k步得到的值
第6章：博弈
在之前的部分里，研究了，任何人的行为结果至少潜在地依赖于其它人之联合行为
从这一部分开始，我们将用博弈论研究行为层次地关联性
博弈论研究的是这样一种情境，即人们的决策结果不仅取决于他们如何在不同的备选项之间进行选择，而且取决于与他们互动的其它人做出的选择
6.1 何为博弈
一个案例
中国古代的博弈：田忌赛马
博弈的基本要素
- 参与人
- 策略集
- 回报
博弈特点
- 每个参与人有一个策略集
- 策略组：每个参与人出一个策略构成的策略组合
- 对应每个策略组，每个参与人有一个回报
比如在田忌赛马中
严格占优策略：无论其它人选择何种行为策略时，都会存在一个决策是最佳选择，则定义这个策略为严格占优策略
在上面这个策略中，两个人最优的策略都是复习考试。所以，预期结果是两个88分的情况
囚徒困境
有的时候，并不是两者都有严格最优策略，可能只有一个参与人有严格占优策略，那么另一个参与人可以知道，这个参与人大概率会选择这个严格占优策略，而在这个严格占优策略当中，另一个参与人可以选择它最优的策略
区分严格占优策略，占优策略，最佳应对和严格最佳应对
6.4 纳什均衡
当参与人在双人博弈中都无占优策略时，则需要通过其它方式来预测什么行为倾向于在实际中发生
1.案例：三客户博弈
具体的说明间书p104
收益矩阵如下：
2.混合策略
引入随机行为最简单的方式，是说明实际上每个参与人都不是直接选择H或T，而有概率
在该模型中，设参与人1选择H的概率为p，选择T的概率为1-p
设参与人2选择H的概率为q，选择T的概率为1-q
对于传统的博弈来说，包含参与人、各自的策略集以及对应的收益三个部分，但这里我们放开了随机化条件，实际上已经改变了博弈类型
对于这种新的模型，依然有两个参与人，但每个参与人不再只有两个策略。他们的策略现在表示为概率区间[0,1]中的数。我们把这种称为混合策略
这组混合策略仍包括初始的两个选项H和T，分别对应概率1或0，称为这种博弈中的两个纯策略
3.混合策略收益
对于新的策略集合，定义收益的微妙之处在于此时的收益是随机量。每个人以一定的概率拿到+1收益，以剩余的概率拿到-1的收益
参与人1采取纯策略H的收益期望是(-1) * q + 1 * (1-q) = 1-2q，如果采取纯策略T，其收益期望是1*q + (-1) * (1-q) = 2q-1
如果1-2q ≠ 2q-1，那么纯策略H和T之一就会是参与人1针对参与人2采取策略q的唯一最佳应对
但之前已经说明了在硬币配对博弈中纯策略不会是任何纳什均衡的一部分
因此在硬币配对博弈的混合策略版本中，任何纳什均衡都必有：1-2q = 2q-1，即q = 1/2
因此p=1/2和q=1/2这一对策略就是纳什均衡存在的唯一可能，而这对策略互为最佳应对
第8章：网络流量的博弈论模型
在本章中，我们将利用博弈论的思想构建网络流量模型。在这个过程中，会发生一个非常意外的结果——布雷斯悖论的观点表明：增加网络容量有时反而会减慢网络流通的速度
8.1 均衡的流量
考虑下面这个运输网络，A-D边和C-B边不受交通状况影响，不论有多少辆车行驶在其中，都需要45分钟穿越
而A-C边和D-B边受拥堵的影响较大：当有x辆车行驶在同一条路线时，穿越该路线所需要的时间为x/100分钟
在这个新的运输网络上存在唯一的纳什均衡，但它导致大家花费更多的时间
均衡状态下，每个司机都是用从C到D的路线，结果每个司机需要的行驶时间为80 > 65
多修一条路，情况反而变得更糟了
对布雷斯悖论的一些思考
布雷斯悖论本身并没有自相矛盾
在很多设置环境中，给博弈增加一个新策略会使情况变得更糟
另外的提高效率的方法
第9章：拍卖
博弈论的第二个应用：拍卖中买方和卖方的行为
9.1 拍卖的类型
-
增价拍卖——英式拍卖
增加拍卖，卖方不断提高售价，竞拍者不断退出，直到剩下最后一位买家，这个卖家最终赢得商品
-
降价拍卖——荷兰式拍卖
卖方从最高价起逐步降价，直到第一个竞拍者接受并支付当前价格。
-
首价密封拍卖
竞拍者同时向卖方提交密封报价。出价最高者以其出价赢得商品
-
次价密封拍卖
同样密封报价。出价最高者赢得商品，但以第二高出价购买商品
9.2 何时拍卖适宜
1.已知估值
假设一个卖方希望出售他认为价值为x的商品，所有潜在的买家对这个商品的最高估值为一个更大的数值y。在这种情况下，销售这个商品将产生一个y-x的盈余
9.4 次价拍卖
在次价密封拍卖钟，竞标者提交独立的私密的竞标价，此时提交真是估值是一个占优的策略，即对竞标者来说，最好的选择是竞标价格恰好是他认为商品所值的价值
换句话说，次价拍卖鼓励人们说真话
1.从博弈论视角看次价拍卖
设vi为竞拍者i对商品的真实估值。竞拍者i的策略是以bi为竞标价，其中bi为真实估值vi的函数
在一个次价拍卖中，竞拍者i的回报定义如下：
- 如果bi不是中标价，则i的回报为0
- 如果bi是中标价，并且bj是第二高的竞标价，则i的回报为vi-bj
2.在次价拍卖中真实出价
断言：在一个密封次价拍卖中，每个竞拍者i的占优策略是选择一个竞拍价bi=vi
证明这个断言：
假设你按真实价bi出价后，可能有两种情况
2.完美匹配
当二部图两边有数目相同的节点，一个完美匹配就是左右节点的配对。
- 每个节点都有边连接到另外一列的节点
- 不会出现左边两个节点同时连到右边同一个节点上
下面用黄线标记的就是一组完美匹配
一个合理分配房间的方法就是寻求尽可能高的分配方案质量。我们称之为最优分配，因为这种方案使每个人的满意程度最高
二部图匹配是最优分配的一个特例，即将最优分配中的数值变为1和0
注意，对于每位买家，他们偏好卖家的组合如何根据价格变化而变动
2.市场清仓价格
市场清仓价格：如图b，每间房屋都有了不同的买家。
最后每个买家都会得到一套不同的房子
图d显示了市场清仓价格这一概念的微妙之处，每个买家都可以得到不同的房子，但仍需要协调。在某些情况下，这种“平局”是难以避免的，如果所有买家对全部商品的估值一样，那么没有任何价格组合能消除他们之间的对称性
如果一组价格形成的偏好卖家图有完美匹配，那么它就是一组市场清仓价格
3.市场清仓价格的属性
市场清仓价格的存在性：对于任何买家估值的组合，总存在一组市场清仓价格
市场清仓价格的最优性：对于任何一组市场清仓价格，偏好卖家图中的一个完美匹配使估值总和在所有买家与卖家的配对中达到最高
10.4 构造一组清仓价格
找到清仓价格的步骤（考试时直接按这个步骤来就可以了）
- 每轮开始时，会有一组既定价格，最小值为0
- 构造偏好卖家图，检查是否有完美匹配
- 如果有，过程结束：目前的价格即为市场清仓价格
- 如果没有，我们找到一组受限买家S和他们的邻居N(S)
- N(S)中的每个卖家同时将出价提高一个单位
- 如果需要，我们统一降低卖家价格，让每个价格都减少相同数额以使最低价格为0
- 用新的价格开始下一轮拍卖
课堂练习，要求必须掌握
来源：叶卡捷琳堡
声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！