社会计算（二）

第三部分信息网络与万维网

七、万维网结构

1.万维网结构

万维网包括一个超大强连通分量SCC，链入IN，链出OUT和卷须、管道、游离等部分组成。

获取一个有向图的类万维网结构：

第一步：生成图的反向图
第二步：选择一个在最大强连通子图中的节点
第三步：以为出发节点，在图中宽度优先搜索直到没有新的节点发现，得节点集合
第四步：以为出发节点，在图中宽度优先搜索直到没有新的节点发现，得节点集合

则，，，其他结构为剩余的节点。

2.万维网规模——标志重捕法

其中为万维网规模，为第一次标记数，为第二次捕获数，为第二次捕获中标记数。

八、链接分析与网络搜索

1.中枢性和权威性（HITS）算法

初始化：一个有向图，对于每一个节点，。（auth 为权威值，hub 为中枢值）
对于每一个节点，让等于指向的所有节点的之和。
对于每一个节点，让等于指向的所有节点的之和。
在每一轮结束后做归一化：值／总和，重复上述两步若干次。

2. PageRank 算法

一个有个节点的网络（有向图），设所有节点的PageRank初始值为。

每一轮：

每个节点将自己当前的PageRank值通过出向链接均分传递给所指向的节点。（若没有出向链接，则认为传递给自己）
每个节点以从入向链接获得的（包括可能自传的）所有值之和更新它的PageRank。

PageRank 算法是一轮一轮进行的，每次更新的是下一轮的值，不是本轮的值！

第四部分网络动力学

九、小世界现象

1.形成社会网络的两种基本力量

同质性（选择，社会影响），三元闭包
弱联系

2.小世界模型

（1） Watts-Strogatz 模型

存在许多“三角形”和少数随机的“远程边”。

小世界网络指聚类系数较大且平均路径长度较小的网络。

（2）扩展 Watts-Strogatz 模型

让两个节点之间连接的概率与它们的网格距离的幂次成反比关系（即随距离增加而衰减）。

记为到的距离（网格步数），则产生一条从到的随机边的概率与成正比。

十、幂率与富者更富现象

1.幂率

查看是否幂率，取和对应，观察在常规坐标下曲线是否像一条直线。
幂率不受尺度影响，即。

2.富者更富效应

“富者更富”也具有级联的意味，现实生活中有不少体现这种情形的现象。
最初阶段充满不确定性，“富”到一定程度后就开始“起飞”。

3.“长尾”分布

销量至少为的品种数：（也是幂率）

结论是：在长尾规律下，如果品种足够多，经营利基产品也能够获得很大利益。

十一、信息级联

1.贝叶斯公式

条件概率：在观察到B的情况下出现A的概率。

贝叶斯公式：在已知结果是B的情况下，发生的概率

一种简单的情况是

2.级联模型

考虑第N个人，假设N号个体知道前面每个人都遵循自己的信号做决定，也就是说，这些早先的人拒绝/接受的决定完全取决于他们收到的是高信号或低信号，N号个体很清楚这一点。

在N号个体之前做决定的人中，如果接受的数量和拒绝的数量相同，或者接受的数量和拒绝的数量相差1个，N的私有信号就成为决胜因素，N会按照自己的信号做决定。
在N号个体之前做决定的人中，如果接受的数量和拒绝的数量相差2或大于2时，N将选择先前的大多数信号的选择，而忽略自己的信号，N+1，N+2以及后面的人都会如此。

十二、网络中的级联

网络结构对新事物传播影响的模型

问题描述：
一个社会网络中，A,B两类事物在其中流行，每个人只能采纳A或B之一，对于一条边（w,v），他们的收益矩阵为：
A B
A (a,a) (0,0)
B (0,0) (b,b)

	A	B
A	(a,a)	(0,0)
B	(0,0)	(b,b)

（1）决策门槛

设v有个邻居，比例的邻居选A，比例的邻居选B：则v选A的回报，v选B的回报，如果
$即$
选A好，否则选B好，称为门槛。

（2）新生事物在网络中的传播

同时考察每一个采用B的节点采用A的邻居比例是否达到门槛，是则节点放弃B，转用A，否则继续采用B。

重复这个过程，直到网络中采用A的节点集合不再变化。

若全部节点选择了A，则称实现了完全级联。

（3）阻挡级联的因素——聚簇

称一个节点集为密度为的聚簇，则其中每个节点至少有比例为的网络邻居也属于这个节点集合。

设网络中一个初用节点集采用A，剩余网络的其他节点采用B，且它们改用A的门槛值为。

如果剩余网络中包含一个密度大于的聚簇，则这个初用节点集不能形成A的完全级联。

而且，如果一个初用节点集不能形成一个完全级联，则剩余网络一定包含一个密度大于的聚簇。

突破阻碍：
提高A的质量，从而减少值
在密度大于的聚簇中选择关键人物