1.3　社交网络模型

复杂网络理论兴起于20世纪90年代，是对复杂系统的一种抽象。随着功能越来越强大的计算设备和互联网的迅猛发展，人们逐渐能够收集和处理规模巨大且种类不同的网络数据，因此对复杂网络的研究变得越来越必要。其中，社交网络是复杂网络应用中最直观的例子。本节首先介绍复杂网络中著名的小世界理论，接着在此基础上介绍一些常见的社交网络模型：ER随机网络模型、WS小世界网络模型、BA无标度网络模型。

1.3.1　ER随机网络模型

1. 随机图简介

在了解ER随机网络模型之前，首先需要了解随机图的概念。随机图的“随机”体现在边的分布上。一个随机图是将给定的顶点之间随机地连上边。具体来说，给定一定数量的顶点，随机地将两个顶点之间连上一条边，多次重复后，最终得到一个随机图。由于边的产生可以依赖不同的随机方式，因此就产生了不同的随机图模型。图1-7所示为一个ER随机网络。

2. ER随机网络模型

在图论中，ER随机图是一种网络，因此也被称作ER随机网络模型（Erdős-Rényi model）。ER随机图于1959年被提出，以Paul Erdős和Alfréd Rényi的名字命名。同年，Edward Gilbert独立提出了另一个模型，该模型和ER随机网络模型是两种不同但又密切相关的描述方式。

在ER随机网络模型中，当顶点集数量相同时，具有固定边数的所有图均具有同等的出现概率。在Gilbert引入的模型中，每条边都有固定的出现概率，并与其他边独立。将该模型用于概率方法能证明满足各种属性的图的存在，或者对几乎所有图的属性提供严格的定义。下面分别对这两种模型进行介绍。

ER随机网络模型的第一种描述方式是：给定网络顶点数N，网络中的任意两个顶点以概率p连接，生成的网络全体记为，构成一个概率空间。中的一个图平均有条连边。任意特定顶点的度服从二项分布：

　　（1-20）

特别地，若N很大且p很小，得到其满足泊松分布：

　　（1-21）

ER随机网络模型的第二种描述方式是：给定网络顶点数N和网络的边数M，从构成的所有图的集合中随机选择一个图（不能出现重边和自环）。生成的网络全体记为，构成一个概率空间。

M条连线是从总共条可能的连线中随机选取的，生成的网络全体记为，构成一个概率空间。这样，生成的不同网络的总数为，它们出现的概率相同，服从均匀分布。

3. ER随机网络模型的简单应用

ER随机网络模型与现实世界非常相关。研究表明，在社交媒体平台中，随机选择一个用户作为顶点，与该用户互为好友的用户用边相连，最终得到的网络结构特征类似于随机图。因此，理解ER随机网络模型有助于理解小型社交网络的结构。

此外，人们常利用实际网络与模型的巨大差异来识别社交网络中的虚拟账号和人工智能账号，从而发现网络中的异常情况。ER随机网络模型更直接的商业应用是广告，利用该模型可以发现业务趋势或识别用户特征，从而实现更精准的广告推送。

1.3.2　WS小世界网络模型

20世纪60年代，美国心理学教授Stanley Milgram做了一个著名的连锁信件实验。实验发现，任意两人之间的间隔陌生人数不会超过6个，换句话说，最多通过6个中间人，你就能够认识任何一个陌生人。此现象被称为六度分隔理论（又称小世界理论），它奠定了社交网络的理论基础。

在网络理论中，小世界网络是一类特殊的复杂网络结构，是以小世界理论为基础引出的网络模型。在这种网络中，大部分的顶点彼此并不相连，但绝大部分顶点之间经过少数几步就可到达。小世界网络是Watts和Strogatz在1998年提出的介于完全规则网络与完全随机网络之间的网络模型，即Watts-Strogatz模型。该模型具有高集聚系数和小平均路径长度的特点，是最典型的小世界网络模型。图1-8是经典网络的演变过程。

1. WS小世界网络模型的构建过程

WS小世界网络模型基于一个假设：小世界网络是介于规则网络和随机网络之间的网络。首先开始于规则图形，初始有数量固定的N个顶点，每个顶点有K个最近邻，构成一个规则的一维圆环。然后进行随机化重连，选择网络中的一个顶点，每个顶点的每条边都以概率p随机地选择网络中的边进行重新连接，重新连接的边需要保持该顶点一端不变，将连接的另一端随机换成网络中的另一个顶点，但不能使两个顶点之间有多于一条边。最后，由于最初的NK个连接中每个连接都恰好有一次重连的机会，所以这个过程最后一定会结束。最终得到的网络称为WS小世界网络。

对于上述的构建方式，当p=0时，重连永远不会发生，最后得到的是原来的规则网络，此时网络是具有高集聚系数与较大平均路径长度特性的完全规则网络；当p=1时，所有的连接都被重连了一次，最后得到的是一个完全随机网络，此时网络是具有低集聚系数与较小平均路径长度的完全随机网络。图1-9所示为网络顶点数为20、连接概率为0.9的WS小世界网络。

2. 疾病传播中的小世界网络

研究者通过研究简易化的疾病传播模型揭示了小世界网络的动力学性质^[6]。现实中的疾病传播通常简化为其中一个人（网络中的一个顶点）被感染，其余人健康。患病者在一段时间后因死亡或被隔离而永久离开网络。在这段时间中，病毒感染者传染引起其余健康个体患病的可能性为p。在接下来的时间中，病毒不断在人群中传播，直到整个群体被感染或者病毒灭亡。最终得出结论：尽管网络中只形成了少量的捷径，小世界网络模型中全体感染所需的时间与随机图被全体感染的时间十分接近，即疾病在小世界网络中迅速传播。

1.3.3　BA无标度网络模型

1. 无标度网络

对比ER随机网络和WS小世界网络可以发现，它们都是一种典型的均匀网络，即度分布函数能用泊松分布曲线来近似表示。小世界网络模型说明在现实中大多数人都拥有差不多规模的社交圈，但是现实的许多网络，比如微博，并不符合均匀网络的分布特性：在该网络结构中，通常微博“大V”的粉丝数巨大，普通用户的粉丝数非常少，不同顶点的入度极其不均匀，这一特征与小世界网络所表现出来的特性极其不同。

Barabási和Albert从数理统计出发，提出了建立无向网络的数学方法，其度分布函数服从幂律分布，由他们提出的方法所建立的无标度网络被称为BA无标度网络模型。

在网络理论中，无标度网络是带有一类特性的复杂网络，其典型特征是网络中的大部分顶点只和很少顶点连接，而有极少的顶点与非常多的顶点连接，这些顶点在网络构建中起到中枢顶点的作用，如图1-10所示。这种无标度网络具有普遍性，很多社交网络都具有无标度网络特征。

2. BA无标度网络模型的构建过程^[8]

BA无标度网络模型基于两个假设：一是增长模式，即大多数的现实网络是不断扩大的；二是优先连接模式，即新的顶点在加入时会倾向于与有更多连接的顶点相连。基于这两个假设，BA无标度网络模型的具体构建可以分为如下两步。

（1）增长

网络通常通过添加顶点和边的方式增长，这些增长形成了网络结构特征。BA无标度网络的增长过程是：网络初始顶点数为m₀，在建立网络的每个时间步都有一个顶点加入网络并与当前网络中的m个顶点相连，其中。

（2）优先连接

新顶点加入网络时会选择与m个顶点相连，连接原则为优先考虑度数大的顶点。对于某个原有顶点，将其在原网络中的度数记作，新顶点与其相连的概率为

　　（1-22）

经过t个时间步长后，网络顶点数变为m+t，新增mt条边。3个初始顶点以及3条边组成了BA无标度网络，该网络的演变过程如图1-11所示。

BA无标度网络模型属于无权网络，即网络中顶点之间只表示是否存在连接，而不用考虑这种连接关系的强弱性。而在现实中，如社会关系网中人与人之间的相识程度、通信网络中干线的带宽等，它们彼此的连接强度是不同的，这种不同显然会影响顶点之间的关系。为了处理这种情况，可以为顶点与顶点之间赋予一定的权值，通过权值来描述这种差异性，即加权网络。