大规模网络上的随机行走过程研究+文献综述(2)
在网络理论中，小世界网络是一种特殊的复杂网络结构，在此类网络中大多数的节点彼此之间并不互相连接，但是绝大多数节点之间可以经过少数几步便可到达。
如今已经有了许多小世界模型，其中使用最多、最有名气的便是Watts和Strogatz在1998年提出的的小世界模型，即WS模型。WS模型是基于两人的一个假设：小世界模型是介于规则网络和随机网络之间的网络。
WS模型定义如下：
步骤1 建立一个规则的网络：起初构造一个规则的网络，网络中有N个节点，网络中的每一个节点都连接到与他最邻近的2k个节点，在通常情况下k<<N。规则网络中的初始连接叫做“短程连接”，短程连接集中分布在每个节点的附近。
步骤2 断键重连：循着顺时针方向轮流考虑每一个节点vi(1≤vi≤N)，将vi的后续的k个相邻节点分别标记为 (1≤ ≤k)。在每一条边(vi， )的 端，以概率p断开连接，然后将该端随机连接到网络上的另外一个节点上。这些重连的边称为“长程连接”。
当p从0变化到1时，上述网络会从规则网络变化到随机网络。当p=0．01左右时，网络将出现小世界特征，即具有较大的聚类系数和较小的特征路径长度。
WS模型的聚集系数公式为
(1)
1.1.2 无尺度网络模型
在网络理论中，无尺度网络（或叫做无标度网络）是一种带有一类特性的复杂网络，它的典型特征是网络中的大部分节点只和少量的节点连接，只有非常少数量的节点与极多的节点相连接。这种关键的节点（称为“枢纽节点”）的存在可以让无尺度网络对意外事故有极强的承受能力，但会显得非常脆弱在面对协同性攻击的时候。
在1998年，Albert-László Barabási、Réka Albert等人共同研究一个关于环球网的项目时，观察到通过超链接与网页、文件所构成的环球网网络没有均匀的度数分布，这与一般网络有所不同。他们观察到，环球网是由少数拥有高连接性的页面串联起来的。绝大多数（超过80%）的网页只有不超过4个超链接，但极少数页面（不到总页面数的万分之一）却拥有极多的链接，超过1000个，有一份文件甚至与超过200万个其他页面相连。用网络来表示，便是大多数节点只有很小的度数，却有小部分节点拥有极大的度数。Barabási等人将其称为“无尺度”网络。
无尺度模型也存在着致命的缺陷：如果在整体网络中去掉一个节点和与该节点有联系的连接，那么原网络中的其它节点或许也会受到其影响。本来相互连接的两个节点也许将会不再互相连接；即使这两个节点依旧互相连接，从其中的一个节点到另一个节点也许会走更远的路程。总而言之，网络的连通性变差了。BA网络模型与一般的随机网络模型相比，对“随机攻击”（即在网络中随机的去除一些节点）的抵御比较强；但是在受到“蓄意攻击”（即优先去除有最高连接度的节点）时，抵御能力非常差，仅仅去除5%到10%的大度节点，就会导致整个无尺度网络瘫痪。
1999年，Albert-László Barabási和Réka Albert在论文中提出了一个模型来解释复杂网络的无尺度特性，称为BA模型。这个模型基于两个假设：
假设1.增加：实际网络往往是一直扩增形成的，比如在互联网中创建新网页，航空网络中建设新的机场，发表新的论文，新的朋友加入社群中，等等。
假设2.优先连接：当新节点加入网络时，将有更大的概率与拥有大度数的节点进行连接，比如新建的网页一般会有到知名的网络站点的连接，新建设的机场会优先考虑建立与大型机场之间的航线新加入，新的论文更容易引用那些已经被被广泛引用的知名著作，人际网络的人会想与人际网络中的知名度高的人结交等等。