社会计算

课程概述

不同类型的网络的依存：

• 互联网：物理的、技术的网络：服务器的关系
• 万维网：基于互联网的信息网络：网页的关系

技术的发展对网络有多种作用：

1. 催化了各种网络的发展：
   1. 规模变大，范围变广
   2. 新型网络的涌现
2. 使得分析和理解大规模网络的行为成为可能：
   1. 行为数据与网络运行伴生
   2. 海量数据分析的能力：计算设施、算法工具

讨论网络的语言：图论+博弈论

图论

网络的结果分析：需要使用图论来建立相应的模型

• 边的成因：为什么节点会形成关系
• 边的意义：不同位置的边的不同作用：关系的强度
• 节点的重要性：由结构特点带来的节点的权力/权重
• 结构的划分、结构的平衡

连通性分为结构（连接本事）层面和行为（个体行动对系统中其他个体的可能影响）层面

桥：删除后两个端点不再联通

捷径：删除后两个端点的距离至少为3。定义捷径的跨度为删除捷径后两点的距离。

强联系与弱联系

网络在现代社会有重要的作用。如何衡量关系的强弱？

三元闭包原则

社交网络中的不是好朋友的两个人：

• 两个人的共同朋友越多，越有可能成为朋友：量的考虑
• 两个人与共同好朋友的关系越密切，越有可能成为好朋友：质的考虑

定义三元闭包：若两个不临接的节点都与某节点临接，则这两个节点在未来临接的概率就会提高

• 关注了网络的演化特性

衡量网络中三元闭包的强度：聚集系数：A的任意两个节点临接的比例：$C=\frac{A为顶点的三角数}{A的边数}$

大部分网络有较强的聚集系数

强三元闭包

强三元闭包原理（假设）：如果A-B和A-C之间的关系为强关系，那么B-C之间也有关系（可以是强关系也可以是弱关系）的可能性较高。

若A符合强三元闭包，且至少有两个强关系邻居，则与A相联的任何捷径必定为弱关系

• 捷径意味着没有共同朋友，强度为弱
• 捷径是全局的结构概念，关系的强弱是局部的概念
• 推论：共同朋友占总朋友比例越高，则关系强度越高

桥提供了两个网络联通的机会

邻里重合度

边的邻里重合度：与A和B相邻的节点数/与A或B相邻的节点数（不包括AB本身）

• 捷径是邻里重合度为0的边

寻找邻里重合度与边的强度的关系

弱关系在网络中提供了更加关键的连接结构，删除一定的弱关系会导致超大连通分量迅速缩小

闭包与结构洞

边的嵌入性：AB的共同临接节点数

若两点由嵌入度较高的边相联，则往往交往会更加信任：负面信息在共同朋友之间的传递

结构洞：大量捷径的末端，联通了多个网络

• 更早地获取了多个网络中的不同信息
• 维持联系的精力有限，积极联系不同群体更有效投入自身的精力

图划分法

将网络分隔后得到的部分成为区域

介数：一条边承载的一种“流量”

• 对于两个节点AB，假设有k条途径，其中m条经过该边，则该边流过m/k

  • 从A开始坐BFS，将节点分层
  • 确定A到B的最短路径数
  • 沿最短路径，将边的值加一，对所有节点进行该操作，再将值除2

• 考虑所有节点对得到一条边的和即为该边的介数

• 依次去除介数最高的边可以分隔网络的不同部分

  

按照介数，利用聚集法来分隔网络为不同区域

网络及其存在的环境

同质性

基本问题：因为相似所以选择成为朋友，还是变成朋友以后相似

内在因素和外部环境对网络中的边的形成的影响是交叉混合的，并发作用在一个网络上

测度：对同质性的量化

如果没有因为相似所以选择成为朋友，那么理论上朋友中不同类型（无论自己是否属于该类）的比例应该和人群中总体中比例相当，这样才能说明没有根据某种属性（背后的相似性）来选择成为朋友。

因此，对于一种简单情况，某种属性只有AB两种取值情况，假设A在整体网络中的概率为p，B的概率为q，那么一条AA边的概率为$p^2$，BB边的概率为$q^2$，跨属性边AB边的概率为$2pq$，则可以统计边的分布是否服从这种点的分布的关系。

如果跨属性边的概率显著低于$2pq$，则称有同质性现象。显著高于则称为逆同质性。

可以扩展为多个属性的情况，核心思想就是边的整体概率分布是否服从点的相应分布。

选择与社会影响

人无法摆脱自身的社会性，无法避免地需要参与到社会环境中去。个体可变的特征，如行为、活动、信仰和关联等，在个体和网络连接中存在反馈效应，网络的连接会变得复杂。

社会化/社会影响：人因为需要和朋友保持一致而改变了自身的行为。

• 在选择中，个体的特征主导网络连接的形成
• 在社会影响中，已存在的社会网络连接会改变人的（可变）特征

归属

考虑背景在网络形成中的作用，可以建立一种特殊的网络：将情景也作为一种节点，利用三元闭包关系来表示环境在联系之间的影响。

定义社团：社会交往的焦点，包括社会的、心理的、法律的或物理的实体，围绕其组织的各种社会活动。

归属网络

个体和场景的连接：表示参与活动

归属网络不关注个体与个体之间的连接，是一种二部图，用于研究个体参与活动的模式。

社会网络与归属网络的协同

社会网络和归属网络都随着时间在演化发展，具有协同演化：

• 参加同一活动为成为朋友提供了机会
• 如果两人是朋友，会影响彼此参加对方的社团

将两种网络融合，成为社会归属网络，显示人民的友谊和与社会团体的归属关系。将两种网络的协同可以视为社会归属网络中的闭包形成过程。

我会成为你的朋友吗？

如何衡量演变的可能性。

闭包的作用

如果两个个体有多个朋友，那么建立友谊的概率是多少：

1. 选取两次不同时间的网络快照
2. 对于所有k，在第一次快照中找出所有恰好有k个朋友、但没有边的节点对
3. 定义T(k)为第二次快照中这些节点对建立关系的比例

T(0)表示没有朋友下建立友谊的概率，T(k)可以看出相应共同朋友的力量。

一种解释：

1. 每个朋友以概率p促进两人成为朋友
2. 在有k个共同朋友的基础上，未能建立友谊的概率为$(1-p)^k$
3. 因而建立友谊的概率为$P=1-(1-p)^k$

社团闭包、会员闭包可以用类似的方法研究。

衡量行为的相似性

可以使用这样的一种测度：都做过的事/至少一人做过的事

隔离的一种空间模型

谢林模型：描述同质性对空间隔离的影响和作用。

1. 定义代理：假设有一群个体，每个具有不可改变的属性X或O，认为每个代理总是喜欢和同类居住在一起
2. 如果代理的同类代理邻居数量低于阈值t，则有动力前往不同的区域。阈值反映了代理对与同类居住的偏好程度
3. 经过多轮后，达到每个代理都满意的状态（同类邻居数量大于t），发现自动出现了隔离现象

import matplotlib.pyplot as plt
import random
import copy

import numpy as np
from matplotlib.colors import ListedColormap


class Schelling:
    def __init__(self, width, height, empty_ratio, similarity_threshold):
        self.width = width
        self.height = height

        self.empty_ratio = empty_ratio
        self.similarity_threshold = similarity_threshold

        self.house_board = {(i, j): 0 for i in range(self.height) for j in range(self.width)}

        house_position_list = [(i, j) for i in range(self.height) for j in range(self.width)]
        random.shuffle(house_position_list)
        empty_house_num = int(self.empty_ratio * (self.height * self.width))
        self.empty_house_position_list = house_position_list[:empty_house_num]
        self.not_empty_house_list = house_position_list[empty_house_num:]

        for pos in self.not_empty_house_list:
            self.house_board[pos] = (pos[0] + pos[1]) % 2 + 1

    def is_unsatisfied(self, pos):
        race = self.house_board[pos]
        pos_x = pos[0]
        pos_y = pos[1]
        count_similar = 0
        count_different = 0

        step = [-1, 0, 1]
        for dx in step:
            for dy in step:
                if dx == 0 and dy == 0:
                    continue
                x = pos_x + dx
                y = pos_y + dy
                if (0 <= x < self.width and 0 <= y < self.height and
                        (x, y) not in self.empty_house_position_list):
                    if self.house_board[(x, y)] == race:
                        count_similar += 1
                    else:
                        count_different += 1

        if count_similar == 0 and count_different == 0:
            return False
        else:
            return float(count_similar) / (count_similar + count_different) < self.similarity_threshold

    def simulate(self, num):
        for i in range(num):
            old_house_board = copy.deepcopy(self.house_board)
            old_not_empty_house_list = copy.deepcopy(self.not_empty_house_list)

            for pos in old_not_empty_house_list:
                if self.is_unsatisfied(pos):
                    race = old_house_board[pos]
                    empty_pos = random.choice(self.empty_house_position_list)
                    self.house_board[empty_pos] = race
                    self.house_board[pos] = 0

                    self.empty_house_position_list.remove(empty_pos)
                    self.not_empty_house_list.append(empty_pos)
                    self.not_empty_house_list.remove(pos)
                    self.empty_house_position_list.append(pos)

    def plot(self, title):
        colors = {0: 'white', 1: 'red', 2: 'blue'}

        grid = np.zeros((self.height, self.width), dtype=int)

        for pos, race in self.house_board.items():
            grid[pos[0], pos[1]] = race

        plt.figure(figsize=(8, 8))
        plt.title(title)
        plt.xticks([])
        plt.yticks([])

        plt.imshow(grid, cmap=ListedColormap(list(colors.values())))
        plt.savefig(title)
        plt.close()

    def calculate_similarity(self):
        similarity = []
        for pos in self.not_empty_house_list:
            count_similar = 0
            count_different = 0
            race = self.house_board[pos]
            pos_x = pos[0]
            pos_y = pos[1]

            step = [-1, 0, 1]
            for dx in step:
                for dy in step:
                    if dx == 0 and dy == 0:
                        continue

                    x = pos_x + dx
                    y = pos_y + dy

                    if ((0 <= x < self.width) and (0 <= y < self.height) and
                            ((x, y) not in self.empty_house_position_list)):
                        if self.house_board[(x, y)] == race:
                            count_similar += 1
                        else:
                            count_different += 1

            try:
                similarity.append(float(count_similar) / (count_similar + count_different))
            except ZeroDivisionError:
                similarity.append(1)

        return sum(similarity) / len(similarity)


def main():
    schelling = Schelling(50, 50, 0.1, 0.7)
    schelling.plot('initial')
    print("finish init")

    for i in range(20):
        schelling.simulate(1)
        schelling.plot("simulate " + str(i))
        print("finish "+str(i))


if __name__ == "__main__":
    main()

正关系和负关系

先前关于网络都是假设边具有正面的含义，但是实际情景显然并不是这样的。扩充含义的基本方法是让网络的边具有正或负的含义：正面表示友好，负边表示对立。

有了正关系和负关系后，网络的平衡呈现出一种张力，使用结构平衡来描述这种张力。

结构平衡

结构平衡的基础是群体中的三节点组关系，认为当有三条或一条正向边时结构是稳定的，称为平衡关系。

对于一个完全图，如果每个三节点组都是平衡关系，那么认为这个图是平衡的。

这里的平衡关系是一个社会系统的极限，实际的网络中往往允许部分三节点组是不平衡的。

认为两负一正的关系是稳定的，是认为有共同的敌人。而对于三条复变的情况，则认为三人缺乏彼此和解的动力，是一种弱稳定。而两正一负的情况，则认为往往会形成和解，是不稳定的。

结构平衡的特性

在定义了平衡关系后，对于一个平衡的网络分析可以得到结论：任何平衡网络都可以分为两组，组内互为朋友，组件互为敌人。即平衡定理。

平衡定理：对于标记的完全的平衡图，其节点集合可以分为X和Y两个互不相交的子集，其中X和Y自身集合内的两个节点都是朋友，从X和Y中各选两个节点都是敌人。

证明思路：

1. 从图中选择一个节点A，则节点集合可以划分为$X=\{A的朋友\},Y=\{A的敌人\}$
2. 对于任意$x,y \in X$，x和A，y和A均为朋友，故x和y也为朋友
3. 对于任意$x,y \in Y$，x和A，y和A均为敌人，故x和y为朋友，否则不为平衡图
4. 对于任意$x\in X,y \in Y$，x和A为朋友，y和A为敌人，则x和y必为敌人，否则不为平衡图

平衡关系的应用

国际关系：敌人的敌人就是朋友，本质上是三节点之间的平衡

信任关系：信任的评价因素更为复杂（实力、领域等等），有时候不能简单地服从三节点之间的平衡

弱平衡关系

弱结构平衡性质：任意三个节点，均不存在两个正关系边和一个负关系边的存在形式

• 允许三条正边（稳定）、三条负边（不稳定）、两负一正（稳定）的情况

弱平衡网络的特性：对于标记的完全图是弱平衡的，则其节点可以分为不同的组，同一组中任意两个节点均为朋友，组件的节点都是敌人

证明：

1. 选取一个节点A，将其朋友和敌人节点分为两个不相交的集合$X=\{A的朋友\},Y=\{A的敌人\}$
2. 对于任意$x,y \in X$，x和A，y和A均为朋友，故x和y也为朋友
3. 对于任意$x\in X,y \in Y$​，x和A为朋友，y和A为敌人，则x和y必为敌人，否则不满足弱平衡图
4. 对于任意$x,y \in Y$
   1. 若x和y为朋友关系，则不变，研究Y中其他节点
   2. 若x和y为敌人关系，在Y中仿照之前的做法拆分出集合$P=\{x的朋友\},Q=\{x的敌人\}$，P、Q中的元素均与A为敌人关系。持续这个过程，直至无法拆分，拆分出的子集均满足和其他集合为敌人关系，内部为朋友关系

结构平衡的推广

在实际的网络中，两两之间都有友好或敌人关系是不一定的，可能不认识。

对于一般性的网络平衡性，有两种等价的定义：

1. 在填补缺失的边后（方式任意），可以形成一个完全的结构平衡图
2. 可以将节点分为两个集合X和Y，集合内部均为友好关系或没有关系，集合之间均为敌人关系或没有关系

易见这两种方式是等价的：按照2划分后在内部填补友好，在集合之间填补敌人关系

1是一种从缺失角度看网络，认为关系是没有被认识到，不一定不存在。2是从更为全局的角度看待网络的性质。

一般平衡性的推广

一般的：若图中存在一个由奇数条负关系边组成的圈，则图是不平衡的

• 对于平衡性判定的一般方法是看能否划分为两个集合，集合之间为敌人，内部为朋友
• 每经过一条负关系边，节点的集合从属关系就要改变，奇数个则无法划分为两个集合

一个标注图是平衡的，当且仅当其不存在含有奇数个负关系边的图

博弈论基础

基本概念

博弈：决策结果不仅依赖于备选项，还依赖于他人的选择

基本要素：博弈类型、参与人构成、策略及收益

基本假设：

1. 参与人最关心的是自身的收益
2. 每个参与人都对博弈有着充分信息
3. 每个个体策略都是为了达到自身收益的最大化

最佳应对：对于其他参与人的决策情况，当下能做出的收益最高的决策（仅对于当下的他人的决策）

严格最佳应对：对于其他参与人的决策情况，当下能做出的收益唯一的最高的决策（仅对于当下的他人的决策）

占优策略：无论其他参与人选择什么策略，都是最佳选择的决策

严格占优策略：无论其他参与人选择什么策略，都是唯一的最佳选择的决策

对于他者的每一个决策都是严格最佳应对，则是严格占有策略

纳什均衡

纳什均衡强调的并不是最优解，因为在实际的博弈中往往是达不到的，强调的是一种均分：参与者分别做出的决策S和T互相为彼此的最佳应对，具有相互一致性。

如果一方没有选择最佳应对，则由博弈论的基本假设，可以认为会选择切换为最佳应对，最终达到一种均分状态，这是一种信念上的均衡。

多重均衡：协同博弈

当一个博弈中存在多个纳什均衡情况时，两方商量后可能得到彼此更好的结果，但是多个均衡给每一行带来的收益可能是不同的，难以预测那种均衡会被采取。

比如，在进行某项决策中，合作才能带来更高的收益，即均为（D，D）或（H，H）才能带来更高的收益，但是具体选择哪一种，是难以预测的。

多重均衡：鹰鸽（反协调）博弈

在竞争某种资源时，抢占他人，即不采取同样的决策才能带来更高的收益。

比如（D，H）或（H，D）才能带来更高的收益，预期一方采取争夺性行为，另一方则表现出分享性行为，但是无法预期具体会采取哪一种。

同样显然的，如果两方都想争取更大的收益，往往达不到这种均衡，而都采取竞争性行为。

混合策略

大量博弈本身没有纳什均衡，对于此类博弈往往通过扩大策略集，包括一些随机行为，来对参与人的行为进行预测。

零和博弈：总收益为0的博弈，一方收益则另一方损失相同。不存在一组策略是最佳应对，进而也不存在纳什均衡。

对于这种情况，决策难以做出，变为用概率的语言进行描述，是原先决策H和T的概率混合，成为混合策略。如果选择某种决策的概率为1，则称之为纯策略。

引入概率后，收益变为了一个基于概率的期望，也即预期收益，可以探索有关预期收益的纳什均衡。

可以证明：如果存在纳什均衡，那么一方的两种决策的预期收益相等：

• 假设一方采取一种纯策略，另一方一定会有一个与概率有关的预期收益
• 对于两种不同的纯策略，如果对应的两个预期收益不同，则较高的那个应该是追求的
• 故会选择收益较高的那个纯策略作为选择
• 这与假设相矛盾，故预期收益相等，这是是纳什均衡存在的唯一条件

在对称结构中，预期收益相等带来概率相等。

长期博弈后会带来收益相等的效果。

帕勒托最优

在纳什均衡中，每个参与人的策略都是彼此策略间的互为最佳应对，但是这是个体最优，不一定能带来群体最优。

帕累托最优：不存在其他策略选择，使得所有参与者得到至少和目前一样高的回报、且至少有一个参与者会得到严格较高的回报。

社会最优：一组策略使参与者的回报和最大

多人博弈

假设博弈中有n个参与人，每个参与人都有一组可能的策略，每次博弈的结果是包括所有参与人的一次策略选择的集合，即第i个参与人的收益为$P_i$。每个结果由相应策略策略$S_i$组成，记对每个参与人i，存在对应收益$P_i(S_1,S_2,...,S_n)$。

对于第i个参与人，若存在一个策略S，使得对于其他策略S‘，都有$P_i(S_1,S_2,...,S_i,...,S_n) \ge P_i(S_1,S_2,...,S'_i,...,S_n)$，称为第i个人的最佳应对。

若一组决策中的每个策略都是对其他参与者的最佳应对，则称策略组$(S_1,S_2,...,S_n)$对应的结果是纳什均衡。

多人博弈中的非优策略

在多人博弈中，难以直接得到最终的纳什均衡结果，会采用一种严格非优策略的迭代删除法。

当一个策略是非优时，将其从博弈矩阵中删去：没有人有兴趣会选择非优的决策，总可以找到收益更高的决策。通过不断的迭代删除，最后得到可以得到纳什均衡的博弈矩阵。

假设有n个参与者：

1. 找到所有的严格非优策略，将其删除
2. 对于化简后的矩阵，有些策略此时会变为严格非优策略，重复1，直至再也没有严格非优策略

这种方法需要证明的问题时纳什均衡集合在删除中保持不变：

1. 初始博弈的纳什均衡是简化后的纳什均衡

   对于初始博弈的纳什均衡策略$(S_1,S_2,...,S_n)$中的每个策略，在每一次的删除过程中都是最佳应对，不会被删除，故也是简化后的纳什均衡

2. 简化后的纳什均衡也是初始博弈的纳什均衡

   假设不是，则初始博弈的纳什均衡为$(S_1,S_2,...,S_n)$，简化后的纳什均衡为$(S'_1,S'_2,...,S'_n)$，其中必定非优$S_i$和$S'_i$有价值上的高下之分，与删除过程矛盾，故是

弱非优策略

一个策略是弱非优策略，则对于其他决策，在所有情况都至少一样高，且至少比其他另一个决策高

弱非优策略可能是不稳定的：当收益都一样高时，没有严格的最优，弱非优策略可能也是一个最佳应对。

动态博弈

博弈随着时间持续发展：一些参与人先行动，其他参与人观察先行者的行为，再决定自己的策略。

博弈树

原先的博弈语言无法描述动态博弈中的时许关系，用树的方式动态博弈的过程，用树的上下关系代表时序关系。树的节点为已经做出的决策，其子节点为观察到该策略后其他参与人做出的策略。

常规形式

还有一种表示方法：对于参与人1的每个策略A/B，参与人2的策略是根据其置定的，可以列出所有可能的情况：(A if A, A if B), (A if A, B if B), (B if A, A if B), (B if A, A if B)

可以简写为：(AA, AB), (AA, BB), (BA, AB), (BA, BB)

当能预测到其他参与者的所有策略时，也可以采用这种方法

网络中的议价与权力

这里的权力指的是：从广义的社会性互动角度来理解权力，不是经济、法律或政治范畴的有关实体的性质。

在多大程度上由自身特性决定，多大程度上源于网络结构的性质（站在了网络的关键位置上）？

对于价值的讨论：

• 经济学：关系的一方为另一方帮助的能力
• 友谊关系：两个人所称为朋友的事实派生出的社会或心理价值
  • 关系的价值在双方划分的方式可被看作一种社会交换

为了描述权力，需要一些与节点有关的性质：

• 依赖性：价值来源的选择是否依赖于某些节点
• 排他性：是否有能力排除与某些节点的关系
• 饱和性：随着关系数量的增加，获得的收益逐渐减少
• 介数：社会关系的价值并不仅局限于直接相联的边上，还会随着社会网络传递

两人议价方案：纳什议价方案

当A和B讨论分配1单位时，同时有分别有外部选项x和y：当放弃谈判则可以获取外部选项x和y。显然有x+y<1，否则讨论是无意义的，会直接获取外部选项。

基于外部选项，A至少要求x，B至少要求y，则剩余部分s=1-x-y，如果两人具有相同的权力，则会考虑平分剩余部分。

故有纳什议价方案：

• 对于A：$x+\frac{1}{2}s=\frac{x+1-y}{2}$
• 对于B：$y+\frac{1}{2}s=\frac{y+1-x}{2}$​

但是往往，两人的权力不是等同的，不会平分s

两人交互模型：终极博弈

终极博弈是一种探讨权力严重失衡情况下的交互模型

• A提出一种分配一单元的方案：多少给自己、多少给B
• B只有两个选择：要么接受，要么拒绝
• 如果B接受了则按照方案分配，否则两人都得不到任何东西

实验中：

• B只要得到就比不得到好，如果两人没有后续互动，那么A很有可能会严重克扣B。
• 但是过于不均衡会导致B拒绝，A也得不到任何东西。
• 经过博弈，最后往往呈现出均分特性

网络交换模型：稳定结果

不稳定：存在一条边，其两个节点会提出一种划分价值的建议，让两人得到更高的价值

不稳定性：给定一种由节点匹配和价值构成的结果，一个不稳定性指，不在匹配中的一条边，其两个端点X和Y的价值之和小于1

• 若小于1，则这两个端点可以协商，更换为这两个端点进行价值划分，获得更高的价值

稳定性：不包含任何不稳定性

网络交换模型：平衡结果

平衡结果：定义网络的其他部分为每个节点提供了最好的外部选项，一个交换结果构成平衡的条件为，对匹配中的每条边来说，价值的划分体现了两个节点的纳什均分议价结果

万维网结构

信息网络：网络被连接的基本单位是信息，彼此相关的信息通过某种方式连接起来。

万维网

万维网的原始构想和设计包含了两个基本特征：

• 提供了方便因特网使用的文档格式：网页
• 提供了能够方便访问网页的方式：浏览器

网页通过网页之间的跳转关系组成了网，这是一个有向图

超文本：用一种网络结构代替传统文本的线性结构，文本中的任何一部分都可以直接链接到其他文本

信息网络

超文本结构呈现了一种重要的信息网络：节点（网页）包含信息，节点之间的连接表明相互关系。

传统的信息组织方式是线性的，而人的思维方式是一种观念记忆的方式展开，和信息网络的结构是一致的。

有向性和无向性体现了社会网络和信息网络的两种不同的网络特征。

万维网有唯一的超大强联通分量SCC。

对于其他不在超大强联通衡量的节点，将其分为：

• 链入：能够连接到所有超大SCC，但不能通过超大SCC链接访问的节点
• 链出：可以从所有超大SCC链接访问，但不能链接到超大SCC的节点
• 卷须：既不链接到超大SCC，也不能通过超大SCC访问
  • 能够从链入集合链接访问但不能链接到超大SCC
  • 能够连接到链出集合，但不能从超大SCC链接访问
• 游离：不存在到超大SCC的无向路径

链接分析与网络

当万维网中的信息足够多时，通过分析网页结构可以得到网页的排名。

中枢和权威

• 链接是影响网页排名的第一个因素：利用链接评价一个主题相关网页的权威性，是针对一个主题其他网页通过链接到一个网页A而赋予网页A的认可程度。
• 不同网页所具有的权威性是不同的，定义一个网页所具有的列表值是所指向的网页获得的链入数之和（被多少个网页指向）的和。

对于每个网页p，定义$auth(p)$为权威值，$hub(p)$为其权威值，每个网页的初始值均为1.

• 权威网页：认可值较高的网页。
• 中枢网页：列表值较高的网页。
• 权威更新规则：对于每个网页p，以所有指向该网页的网页中枢值之和作为其权威值。
• 中枢更新规则：对于每个网页p，以该网页所有指向的网页权威值之和作为其中枢值。

计算方式：

1. 设所有网页的中枢值和权威值为1
2. 执行k次权威值-中枢值更新操作，每次先更新权威值再更新中枢值
3. 对中枢值和权威值均进行归一化（最后才进行归一化）

网页排名

将网页排名看作一种通过网络流通的价值，沿着边在网络中流动，汇集在最重要的节点上

1. 对于一个有n个节点的网络，设置所有网路的初始排名值为1/n

2. 进行k次排名更新操作

   更新规则：每个网页将其排名值分配给指向的网页，失去原排名值。被指向的网页获得所有指向网页的分配的排名值之和。

   这样更新后网络的排名值总和不变。

网络中的一些特殊结构可能会导致排名值的几句，而无法反映真正的排名值。考虑做出一些修正，使用缩放网页排名规则：定义缩放因子s，指向的节点只能分配到s，由所有节点共享（1-s）/n

再定义一种随机游走定义：经过k步随机游走到达网页X的概率，真实网页X运行k次网页排名基本更新算法后得到的网页排名值。

信息级联

通过网络建立联系，就很容易受到他人的影响。网络作为聚合个人行为的途径，产生了广泛的群体效应。

随大流的背后

信息级联：很多情况下，人们实际上是很理性地放弃了自己的选择，转而去选择他人的选择。

产生信息级联的先决条件：人们可以在不同时间依次做出决定，后面的人可以观察前面的人决策行为，并通过这些行为推断出他们所了解的一些信息。

从众的社会力量会随着一致性群体活动规模的壮大而增强。

另一方面，某些商品被越多的人选择，商品本身的产品价值也会相应改变，此时随大流能带来直接受益效果。

信息级联的简单情景

在信息级联中，会出现这样一种情况：依次根据摸到球的颜色猜测罐中哪种球的颜色多。如果只有三个球，而前两个人都报出了相同的颜色猜测，那么对于后来的人：

1. 第三个人相当于有了三次摸球的机会：前两个人往往缺乏信息会报出自己摸到的球的颜色。而如果前两个人报出的颜色相同，第三个人无论摸到什么颜色，都往往会继续按照这个颜色做出选择
2. 在这种情景下，第三个人在理性选择后，放弃了自己的选择，而继续选择前两个人做出的选择。这时候，第三个人没有传递任何有效信息。
3. 后续的人可能也会继续这样的选择，进行从众，每个人的最佳策略都是依赖于那些少量的有参考价值的信息

从这个简单的实验中可以看出：

1. 信息级联很容易建立，只需要满足适当的结构条件

2. 信息级联可能会带来非优化的结果

   在实验中前两个人的偶然性可能会带来后续从众结果的错误

3. 级联可能带来最终的一致，但是根本上也是脆弱的

   如果后续有人坚持自己的选择，那么很有可能会打破之前的信息级联

贝叶斯规则：非确定性决策模型

利用已有的信息定义一个事情发生的概率：贝叶斯规则。是一种基于观察做出决策的方法。

贝叶斯规则：$P(A|B)=\frac{P(A)*P(B|A)}{P(B)}$，可以用以研究事件B对事件A造成的影响。称$P(A|B)$为A在B给定时的后验概率，$P(A)$为A的先验概率。

由于后续进行决定的个体相当于掌握了多次的信息，故可以从概率上更为详细地判断可能发生的概率。

当然，前几次由于概率可能会出现信息级联的情况。

构建级联模型

假设有一群人，其编号为1，2，……，n，需要做出决定，如判断某事件是否为真

模型构建

1. 状态：判断该事件真实发生的概率。记G为该事件为真的状态，其概率$P(G)=p$，B为该事件为假的状态，其概率为$P(B)=1-p$
2. 回报：每个个体接受/拒绝该选项，都会获得一定的回报。记接受该选项的回报为$v_g$，拒绝该选项的回报为$v_b$。在没有别的信息情况下，对选项的选择的预期回报应该为0，即$p*v_g+(1-p)*v_b=0$
3. 信号：在做出决定前，每个个体都可获得一定的信息，记为私有信号，来帮助做出决策。
   • 高信号H表示接受事件为真
   • 低信号L表示接受事件为假
   • 在相应事件下，接受到相应信号的概率为：$P(L|B)=P(H|G)=q,P(H|B)=P(L|G)=1-q$

个体的选择

假设一个个体得到了一个高信号，那么他的决策激励变为：$v_g*P(G|H)+v_b*P(B|H)$

$$P(G|H)=\frac{P(G)*P(H|G)}{P(H)} \\ = \frac{P(G)*P(H|G)}{P(G)*P(H|G)+P(B)*P(H|B)} \\ = \frac{pq}{pq+(1-p)(1-q)} > p$$

更有可能做出该事件为真的决策。

多重信号

在信息级联的假设中，人们依次做出决策，因此后做出决策的人就会掌握前人的信息，得到一个独立生成的信息序列S，包含a个高信号和b个低信号。

由于信号是独立产生的，故可以认为$P(S|G)=q^a*(1-q)^b$

有：

$$P(S) = P(G)*P(S|G) + P(B)*P(S|B) \\ =p*q^a(1-q)^b+(1-p)*(1-q)^aq^b$$

得到：

$$P(G|S) = \frac{P(G)*P(S|G)}{P(S)} \\ = \frac{p*q^a(1-q)^b}{pq^a(1-q)^b+(1-p)(1-q)^aq^b}$$

易见信息序列对决策造成的影响为：

• 当$a>b$，有$P(G|S)>P(G)$
• 当$a<b$，有$P(G|S)<P(G)$
• 当$a=b$，有$P(G|S)=P(G)$

依次选择与级联

某个人做出决定时，会使用自己的私有信号，以及观察到的所有先前人做出的决定。每个个体无法真正得到其他人的私有信号。

对于N号个体，在其之前做决定的人中：

• 如果接受的数量与拒绝的数量相同，N的私有信号就成为决胜因素，N会按照自己的信号做决定。

• 如果接受的数量与拒绝的数量相差1个，那么或者N的私有信号对决定没什么作用，或者它会加强多数信号。

  无论是哪种情况,N都会遵循自己的私有信号行事

• 如果接受的数量与拒绝的数量相差达到2或者大于2时，那么无论N的私有信号是什么，都不会改变早期形成的信号分布状态。因此，N将按照先前的大多数信号，而忽略自己的信号。

  在这种情况下，这种情况将被进一步加强，后续的个体也将忽略自己的私有信号，每个人都会一直简单遵循多数人的决定，达到一种信息级联的效果。

级联的特点

• 级联可能是错误的。

  接受一个选项实际上并非正确，但前两个人碰巧都得到高信号，这样接受的级联效应便马上开始。

• 级联可能基于很少的信息。

  一旦级联开始，人们便忽略自己的私有信息，只有在前级联阶段，信息会影响人群的行为。这意味着，如果一个级联开始得相对比较快，大多数人群中拥有的私有信息都没有被利用。

• 级联是脆弱的。

  前面提到级联可以基于相对较少的信息，使得它们很容易启动；但也可以让它们很容易停止。一种表现是，当人们接收到略具优势的信息就可以颠覆已经存一段时间的级联。

网络效应

信息级联是一种信息效应：其他人的行为传递了他们所知道的信息，会让个体观察别人的行为并模仿着去做。

网络效应是基于直接受益效应：与他人的决策保持一致能带来直接的利益。

网络效益能够产生，采用的技术需要与其他人交互或相容：很多是具有的潜在价值依托于有多少人在使用，如互联网。

• 积极外部效应：外部效应造成收益变高
• 消极外部效应：外部效应造成收益变低

TODO

幂率与富者更富现象

如何量化流行度，如何看待流行度的不平衡。

幂律

由中心极限定理，有理由认为网页拥有k个链入链接数的概率服从正态分布。当k增大时，概率以指数形式变小。

但是在实际的研究中，发现并不是这样的，拥有k个链入链接数的网页比例近似地与$\frac{1}{k^2}$成正比。当k较大时，随着k的增加，其概率下降相当缓慢，说明拥有很大链入数量的网页相当普遍。

幂率函数：一个函数取值为k的概率为k的幂次$k^p$，如$\frac{1}{k^2}$​。

正态分布被广泛用于自然科学中，而幂率分布被广泛用于流行度分布中。

其函数形式为$f(k)=\alpha k^{-c}$。

富者更富模型

级联效应认为，人们有倾向复制之前他人所做出的决定。

网页之间简历联系的简单模型：（为进行简化，假设每个网页只指向一个网页）

1. 网页按照顺序被简历，编号为1，2，……，N
2. 网页j被创立时，以概率p选择如下的两种简历联系的方式
   1. 以概率$p$随机选择一个i，指向网页i
   2. 以概率$1-p$​随机选择一个网页i，指向网页i所指向的网页

模型的结果为链入数为k的网页所占比例近似于$\frac{1}{k^c}$，c的选择依托于p的选择：p减小时复制减少，c也相应地减少。

选择方式2会导致优先选择高流行度的网页，造成一种富者更富现象。

富者更富具有很大的偶然性，很大概率无法复制当前的结果。

长尾现象

公司销售的成功有两种模式：

1. 依托于少数种类产生较高收益的畅销产品
2. 依托于大量产品，每种吸引一小部分的用户

互联网将媒体和娱乐业推向了后一种模式，一种具有”长尾“的销售模式。

网络中的级联行为

对社会网络的研究可以从两个方面展开：

1. 将网络看作由相对无组织的个体组成的一个群体，研究整个群体的聚合效应
2. 利用网络的具体图结构分析个体如何受其他相邻网络节点的影响

模仿他人的行为进行获益有两种模型：

1. 信息效应：基于他人所作出的选择可以间接提供一些信息
2. 直接受益效应：可以从复制他人的行为中获得直接回报

基于网络构建传播模型

以基本的个体决策模型构建一个新行为的传播模型：当个体根据邻居的选择而做出决定时，一个特定的行为模式就开始穿过网络进行传播。

构建这样的个体层次的模型，可以选择信息效应，也可以选择直接受益模型，此处选择后者。当选择的人多后，可以直接享受到一定的受益。

一个网络协调博弈

对于网络中的每个节点，都有两个选择A和B，对于两个节点u和v，对于其做出的决策：

• 如果都选择A，则分别获得回报a>0
• 如果都选择B，则分别获得回报b>0
• 如果选择不同的选项，那么获得的回报为0

网络中某一节点v的行为实际上时基于所有邻居选择的一种博弈，以期望达到回报最大化。假设有d个邻居，比例为p的部分选择A，其余选择B，那么当$pda \ge (1-p)db$时，选择A，反之选择B。要求$p \ge \frac{b}{a+b}$。

级联行为

对于任何网络，协调博弈存在两个极端：一个是所有节点都选择A，另一个是所有节点都选择B。在特定环境中，网络中的一种平衡颠覆，形成另一种平衡，实际上是相当容易的。

当有一部分节点进行选择的转发后，由于级联效应，会带动其他节点进行相同的转化。

最后的结果有两种：

1. 完全转化为另一种选择
2. 形成两种选择平衡的局面

对于新技术传播，可以有两种有效方式：

1. 提高产品本身吸引力
2. 让一些关键人物使用，利用级联效应带动他人使用

级联与聚簇

量化一个密集连接区域，称一个节点集为密度为p的聚簇，当且仅当其中的每个节点至少有比例为p的网络节点也属于这个节点集合中。

网路中的聚簇可以以不同的规模并立存在。

级联与聚簇的关系

当一个级联遇到一个密度高的聚簇时，会停下来。这是唯一使级联停止的原因，也就是说聚簇是级联的自然障碍。

基于此可以提出断言：考虑一个行为 A的初用节点集,剩余网络中的节点采用行为 A的门槛值为 q。

1. 如果剩余网络包含一个密度大1-q的聚簇，则这个初用节点集不能产生一个完全级联。

2. 而且，如果一个初用节点集不能产生一个完全级联，并且门槛值为q，则剩余网络一定包含一个密度大于1-q的聚簇。

   这个结论说明聚簇不但是障碍，还是唯一障碍：只要级联失败，就一定有聚簇

级联模型的扩展

每个人对选择的估值实际上是不同，记节点v对AB两个选择的估值分别为$a_v,b_v$。

定义网络中的阻塞聚簇：一个节点集，其满足其中任一节点v有超过$1-q_v$比例的邻居也属于同一个节点集

知识、门槛值和集体活动

多元无知现象：人们总是错误估计整个民众对某些意见的反映。

小世界现象

小世界：短路径将社会中几乎所有人连接起来。

基于两个原则建模：存在短路径、短路径能够被发现。

结构与随机性

社会网络呈现三角形态：一个人的朋友中不少也相互认识。这种三元闭包限制了人民可以通过短路径达到的人数。

社会网络的两个基本特征：

• 同质性：人们和与自己志趣相投的人建立联系
  • 产生了许多三角关系
• 弱连接：这些连接能让人们与网络中较远的人建立联系
  • 产生出广泛的三角关系

分散搜索

小世界实验的一个前提是：如果存在关系，那么关系能被找到，但在实际的人际关系中，是不一定存在能够被使用的关系网络的：不能利用理想的BFS方式去搜索关系

如何模拟一个社交网络的生成：小团体与交际花

使用WS网络模型来模拟小世界的生成。

Watts-Strogatz模型

从两种很好理解的图开始：随机图和正则图

• 在随机图中，节点随机连接
• 在正则图中，每个节点具有相同数量的邻居

考虑这些图的两个属性，群聚性和路径长度：

• 群聚是图表的“集团性”的度量。
  • 在图中，集团是所有节点的子集，它们彼此连接；在一个社交网络中，集团是一群人，彼此都是朋友。
  • 定义了一个群聚系数，用于量化两个节点彼此连接，并同时连接到同一个节点的可能性。
• 路径长度是两个节点之间的平均距离的度量，对应于社交网络中的分离度。

正则图具有高群聚性和长路径长度，而大小相同的随机图通常具有群聚性和短路径长度。但这些都不是一个很好的社交网络模型，社交网络应该是高群聚性与短路径长度的组合。

用于构建小世界图的过程：

1. 从一个正则图开始，节点为n，每个节点连接k个邻居。

2. 选择边的子集，并将它们替换为随机的边来“重新布线”。

   1. 边的重新布线的概率是参数p，它控制图的随机性。
   2. 对于两个节点v和w，以$d(v,w)$表示两个节点的距离，用聚集系数q控制产生随机边的几率：以概率$k*d(v,w)^{-q}$的概率产生由v到w的随机边。
   3. 当p=0时，该图是正则的；p=1是随机的。较小的p值产生高群聚性的图，如正则图，短路径长度的图，如随机图。

核心依然是去贴合社交网络的特性：高聚集性、短路径长度

WS模型的关键在于，以远距离弱关系的形式引入了部分的随机性。

• 对于一个较小的聚集系数，随机边较长
• 对于一个较大的聚集系数，随机边较短

对现实世界的考量

现实世界难以用距离来分量真正的关系，转而使用关系的排名来作为距离的代替。

1. 从一个节点v按照亲近程度对其他节点进行排名，$rank(w)$等于比节点w更接近v的节点的数量
2. 则从节点w创建到v的随机连接的概率正比于$rank(w)^{-p}$，p表示聚集系数

p的选择与rank的选择有关，要能描述基本的关系现象。实际的研究发现，朋友关系的聚集系数$p(r) \sim \frac{1}{r}$

核心-外围结构

对于不同目标成功搜索速度的大幅变化，并不是简单地因为不同个体的属性差异，而主要是由于社会网络的结构特性使得地位较高的个体比地位较低的个体更容易被找到。

同质性原则表明：地位较高的人也主要熟知其他地位较高的人，而地位较低的人认识的也大多是地位较低的人。

但是这并不意味着这两个群体是对称的，或在社会网络可以互换位置。相反，大型社会网络往往是以一种所谓的核心-外围结构组成：地位较高的人被连接在一个密集的核心，而地位较低的人都分散在网络的外围。