本文为课程《社会科学中的计算思维方法》的课程笔记，这门课在Mooc上似乎也有，不过是SPOC的来着。本来打算等期末的时候再一股脑地整理成一篇Blog，不过我发现内容是实在有些多，只好份部分放出，本篇是这门课的三四章内容。
第三章 小世界
3.1 小世界实验及其惊奇
操作化：将一个通俗的概念变成一个可以量化的东西
设计实验：选择一个随机起点，看要经过几个人到一个确定目的地。
→ 六度分隔
小世界现象：
- 世界是小的：六度分隔
- 「自动寻找」短路径
3.2 小世界的普遍现象
网页之间的「社交」：短路径为18.59次连接
书信，加上种族因素，电子邮件等都有小世界现象存在
3.3 小世界基本模型
根据哪些基本原理，可以说明小世界现象的必然性？
两种基本力量：同质性 and 弱联系
watts-Strogatz模型：
- 网格距离 + 网络距离
- 连接近邻（确定性） + 连接远程（随机性）
- 可以证明这样的网络中，任意两点存在短路径的概率很高。
- 但不能很好地体现短视的自动搜索。（要求二）
3.4 小世界精细模型
WS模型局限：短视搜索下，常常导致较长路径。
短视搜索（分散搜索）特点：
- 每个节点有特征，特征 ≠ 距离
- 每个节点知道目标节点特征，自己和邻近节点特征
- 节点将搜索传给距离目标节点距离较近的邻居节点
短视搜索 ≠ 最短路径
网络模型要求：短路径的「存在性」 + 短路径的「可实现性」
watts-Strogatz-Kleinberg模型：让两个节点之间存在随即边的概率与他们网格距离d的函数$\frac{1}{d^q}$成正比。
q越小，随机边越远。q=0时，退化为ws模型。
q=2时，分散搜索效果最好。
3.5 小世界模型的大数据验证
网络模型的优化性质：两个人成为朋友的概率与其空间距离的平方成反比
对社会网络的建立而言，地理距离范围内对人数比距离本身更具有实质性意义。
→ 排名与距离有对应关系：排名 ～ 距离的平方
「实验 - 理论 - 完善 - 实验」对研究范式
3.6 核心-外围结构：一种社会网络观
核心-外围结构：社会较高的人，通常位于社会关系的核心位置。
寻找地位较低的人，会更加困难。
网络结果会因为节点上的人的社会属性不同而不同。
社会属性是影响网络结构及其连通性的重要因素。
第四章 万维网结构，链接分析与网络搜索
4.1 有向图
具有方向性的关系（引用，粉丝，人之间的认识等）
出度，入度，有向路径：有X到Y，不一定有Y到X，就算有，中间节点也可能完全不同
有向图到强连通性：任意两节点之间在两个方向上都联通。
强连通分量：强连通条件+它自己是最大的
一个有向图中，不可能有一个节点属于两个不同的强连通分量。
如果一个有向图没有有向圈，则一定有节点出度为0。
4.2 将互联网信息看成一个有向图
互联网信息结构概貌：「领结状」
获得「领带」的SCC，IN，OUT：生成反向图 - 前向搜索FS - 后向搜索BS - SCC为二者的交集，IN为BS-SCC，OUT为FS-SCC。
广度优先搜索是具体得到领结的手段
4.3 中枢与权威
传统信息检索技术：基于词语的相关性
搜索引擎：有效利用链接关系蕴含的信息
反复改进原理：用推荐的评分反过来评估推荐者的分量，并反复迭代。
网页的「中枢性」（指向多）与「权威性」（被指向多）。
HITS算法：计算网页权威值（auth）和中枢值（hub）
- 先都赋为1
- 用中枢值更新权威值
- 用权威值更新中枢值
- 重复以上两步若干次。
- 每一轮结束后进行归一化，其结果会趋于一个极限。
4.4 网页排名
PageRank：节点重要性的一种测度
- 每个节点将自己的值均分给出向邻居，自己拿入向邻居给的值
- 多次迭代，值会收敛
- 这个值可以用来量化重要性
4.5 同比缩减与等量补偿
当「只进不出」时，PageRank算法会趋向于集中（过于理想化）。
- 同比缩减：每次迭代后，整体乘一个小于1的比例因子s
- 统一补偿：每一节点的PageRank值上都加上（1-s）/n。
随机游走模型结果与其相似。