1998年, Watts和Strogatz 提出了小世界网络这一概念,并建立了WS模型。 实证结果表明,大多数的真实网络都具有小世界特性(较小的最短路径) 和聚类特性(较大的聚类系数) 。

WS小世界模型构造算法

1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。

2、随机化重连：以概率p随机地从新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。

-In 1998, Watts and Strogatz proposed the concept of the small world network, and the establishment of the WS model. The empirical results show that most real networks have small world (the smaller the shortest path) and clustering properties (high clustering coefficient).

WS small-world model construction algorithm

1, from the rules FIG: consider a nearest neighbor coupling network with N points, they are surrounded by a ring, wherein each node and its left and right adjacent to each of K/2 connected to the node, K is an even number.

The 2 randomized reconnection: randomly with probability p from the new connection on each side of the network, coming section of one of the endpoints remain unchanged, while the other endpoint is taken as the random selection of a node in the network. Which states that between any two different nodes can have at most one edge, and each node can not be connected to its own side.