mio4
Java Web & Web Security
社会计算课程总结
0x2 图论
0x3 强联系和弱联系
- 判断节点是否满足强三元闭包关系：首先选择所有不满足强三元闭包性质的节点（节点A和节点B、C之间有强关系，但是B、C之间没有强关系也没有弱关系）
- 三元闭包关系：社会关系中，有共同的朋友，则成为朋友的可能性很大
0x5 正关系和负关系
- 结构平衡：对于三个节点构成的关系，其中有1个或者3个正关系，那么属于结构平衡，否则是结构不平衡（平衡结构有2种，不平衡结构有2种）
- 判断新加入的节点是否会产生不平衡的关系
- 同质性
- 是因为相似才成为朋友（选择）还是因为成为朋友之后变得相似（影响）
- 投影图：参与了相同社团的节点形成的边
- 谢林模型：
0x6 基本博弈分析
- 博弈：人们的选择不仅取决于选项之间，还取决于互动的其他人的选择
- 理性人：每个个体的选择都会让自己的收益最大化，并且了解其他参与者收益最大化的策略
- 解决一般博弈问题：根据个人的收益矩阵，然后根据别人的选择，对比这种选择之下自己的选择，如果存在严格占优策略，则选择。如果双方处于对称的情景，则结果是可预期的
- 囚徒困境：和“考试-报告”模型一样，坦白是严格占优策略
- 鹰鸽博弈：无法预测具体的选择情况，但是可以根据纳什均衡缩小选择范围，总有一方应该属于“分享型”
- 零和博弈：参与人的总收益是0
- 混合博弈：参与人概率出现一种选择，期望收益是关于概率的函数。
- 混合博弈的硬币模型：存在唯一纳什均衡就是分别选择概率为1/2的策略（Head）
- 纯策略：不通过概率进行选择，固定选择的混合博弈
- 最佳应对：固定参与人2的策略，从参与人1的所有策略中选出最好的
- 占优策略：无论参与人2选择的策略，参与人1选出的策略是最好的
- 纳什均衡：如果S是T的最佳应对，同时T也是S的最佳应对，那么(S,T)也是一个纳什均衡
- 社会最优：一组策略可以让参与者的回报之和最大
- 找出博弈结果中的纳什均衡
0x8 网络流量的博弈论
- 均衡状态下的流量：形成纳什均衡，两条道路的流量是相同的
- 布雷斯悖论：个体最优选择的汇总，不一定是群体最优选择的汇总
- 形成纳什权衡条件：司机会安于自己的选择，没有更换道路的需求
0x12 网络中的权力
- 权力是一种相对的定义
- 采用1-交换原则分析两节点、三节点模型以及加入节点之后权力的变化情况
- 两节点：平分资源池
- 三节点：中间的节点权力相对更大，因为处于两边的节点有被抛弃的可能
0x13 超大强连通分量
- 强连通分量：在有向图中，每个节点都有到任意节点的路径
- 链入：能够链接到SCC，但是不能通过SCC访问的节点
- 链出：能够从SCC访问，但是不能链接到SCC的节点
- 卷须：能够从链入部分访问，但是不能到达SCC；能够访问链出部分，但是不能从SCC访问
0x14 网页排名
- 中枢网站：指向很多网页
- 权威网站：被很多网页所指
- 对网站进行迭代分析：
- 首先初始化所有值为1
- 然后根据中枢网站，更新权威网站：所有权威网站权威值的和
- 然后根据权威网站，更新中枢网站：所有中枢网站中枢值的和
- 最后计算归一化值：值/总值
- 网页排名算法
- 所有网站初始排名为1/n
- 每次网页将自己的排名均分出去，获取的排名加起来，成为新数据
- 检查网络结构是否处于平衡状态：和为1并且迭代之后排名不变
0x16 信息级联
- 信息级联：忽略自己的信息而采用人群的选择
- 由于信息是透明的，所以平均现象之后，可能会破坏信息级联
- 题型：对于已知的现象进行判断，如果因为人群的判断而影响了自己的判断，那么是发生了信息级联效应
- 打破信息级联的影响：采用黑箱投票方式
- 贝叶斯定理：P(A|B) = P(AB) / P(B)
0x18 幂律分布和富者更富
- 设定一个值k，满足k个链接数的网页占比和1/k^2成正比
- 富者更富：网页流行度增加的概率和当前的流行度成正比
- 长尾效应：所有非流行的市场累加起来会形成一个比流行市场还大的市场
0x19 网络中的级联
- 级联：级联是一种随大流现象，并且随大流的条件是邻居中有超过p的比例选择了新生事物
- 聚簇：本质上是一个节点集，集合中的每个节点至少有p的节点属于这个节点集合，则密度为p
- 完全级联：图中所有的节点最终都发生了转换
- 涉及到邻接规则q的范围：采用A获得收益>采用B获得收益
- 聚簇和级联：如果剩余网络中包含一个密度>1-p的聚簇，那么就不能形成一个完全级联（充分必要条件）
- 证明聚簇是级联的障碍：采用反证法，假设一个节点v采用A，那么它的邻居中有大于q的节点采用了A，根据聚簇的定义，产生矛盾，结论成立
- 证明聚簇是级联的唯一障碍：只需要证明剩余节点组成的节点集合密度>1-p，选择其中的一个点选择B，那么邻居中选择A的节点数<p，那么选择B的节点数>1-p…形成了一个聚簇
- 异值门槛：每个节点对于选择A和选择B的回报不同，修改回报矩阵和不等式即可
- 病毒式营销：提高质量和选择关键人物来突破聚簇的障碍，
0x20 小世界现象
- 形成社会网络的两种基本力量
- 小世界现象： 网络中节点的距离L随着网格数呈对数增长
- 小世界现象存在的基础：基于网络中的弱联系
- 忽视小世界现象：增大了人与人之间的距离，对实验会产生误差
附加部分
0x9 拍卖
0x10 匹配市场
0x21 传染病的网络传播
- 树状分支过程
- 基本再生数：R0 = p * k ，概率 * 接触的人数
- R0 ~ 1 出现刀刃特性
- SIR流行病：有三个时期，易感染时期、传染期、结束期
- R0定义为单一节点产生新病的期望
- 有一定概率形成路障
- 静态SIR模型，对每条边进行预定义