WS小世界模型构造算法

NW小世界模型构造算法

小世界网络模型是一类具有较短的平均路径长度又具有较高的聚类系数的网络的总称。

小世界网络模型是Watts和Strogatz在1998年提出的基于人类社会网络的网络模型，它通过调节一个参数可以从规则网络向随机网络过渡，该模型成为WS小世界模型。

由于WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性，Newman和Watts提出了NW小世界网络模型，该模型是通过用“随机化加边”取代WS小世界网络模型构造中的“随机化重连”。

WS小世界模型构造算法

1、一个环状的规则网络开始：网络含有N个结点，每个结点向与它最近邻的K个结点连出K条边，并满足N>>K>>ln(N)>>1。

2、随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。这样就会产生pNK/2条长程的边把一个结点和远处的结点联系起来。改变p值可以实现从规则网络(p=0)向随机网络(p=1)转变。

NW小世界模型构造算法

1、一个环状的规则网络开始：网络含有N个结点，每个结点向与它最近邻的K个结点连出K条边，并满足N>>K>>ln(N)>>1。

2、随机化加边：以概率p在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。改变p值可以实现从最近邻耦合网络(p=0)向全局耦合网络(p=1)转变。当p足够小和N足够大时，NW小世界模型本质上等同于WS小世界模型。