3.3 小世界模型仿真

本节将对NetworkX包中的W-S模型源码进行解读，并采用伪代码来进一步解释W-S-K模型，最后验证所生成网络的小世界特性，如代码3-1所示。

代码3-1 W-S模型伪代码

输入： 节点总数 n ，每个节点的邻居节点设为 k ，边进行重连的概率 p

输出： 边重连概率为 p 的W-S小世界网络

1. G =Graph（）#　新建简单无向图

2.nodes=list（range（ n ））　# 新建 n 个节点

3.edges=connect_neighbors（nodes）# 将节点与 k /2个邻居节点连接

4.#随机选择先前建立的邻居边进行断链重连

5.for（ u ， v ）in edges：

6.if select_probability（（ u ， v ））＜ p ：#随机过程，当随机概率小于 p 时进行断链重连

7. w =random.choice（nodes）#随机选择当前要去重连的节点

8. w =filter（ w ）#检验 w 是否就是原边连接的节点 v或者w与u 本来就存在边，若是则随机选择另一个节点再进行判断，直至返回不是 v节点且与u 先前没有边连接的节点

9.if G .degree（ u ）≥ n -1：#如果 u 节点已经与图中所有节点产生连接边则退出重连过程

10.break

11.else：

12. G .rewire（ u ， v ， w ）#将（ u ， v ）边重连为（ u ， w ）边

13.return G

通过调用NetworkX程序包，建立一个包含100个网络节点的W-S模型，研究 p 从0到1以0.1间隔变化时，网络平均路径长度和聚类系数的变化趋势。

如图3-14和3-15所示，随着 p 增大，平均路径长度不断减小，在 p 从0变化至0.1的过程中呈现明显的变小趋势。聚集系数随着 p 的增大，整体呈现下降趋势。并且如上文W-S模型特性中提到的，从图3-14中可发现，当 p 值较小时，引入随机边对平均路径长度有着很大的非线性影响，平均路径长度迅速减小。但较小的 p 对聚集系数影响很小。此时所形成的网络具有高聚集系数和短路径特征的小世界网络特性。

接下来进行W-S-K模型的构建，如代码3-2所示。

代码3-2 W-S-K模型构建伪代码

输入： 节点总数 n ，每个节点的邻居节点设为 k ，随机边的条数 r ，产生连接的概率与 d（u，v） 的 -q 次方成正比

输出： 输入 q 值对应下的W-S-K小世界网络

1. G =Graph（）# 新建简单无向图

2.nodes=list（range（ n ））# 新建 n 个节点

3.edges=connect_neighbors（nodes）# 将节点与 k /2个邻居节点连接

4.for u in nodes：#对每个节点建立随机边

5.for i in range（ r ）：#建立 r 条随机边

6.select_nodes=prepare（ G ，nodes， u，k，r ）#筛选出度小于 k + r 的节点作为可进行随机连接的节点集合

7.if G .degree（ u ）＜ k + r ：#检查 u 节点的度小于 k + r 才可增加随机边

8.while w == u ：

9. w =random.choice（select_nodes）#从可选节点集合中随机选择节点

10.path=shortest_path_length（ G，u，w ）#计算（ u，w ）间的晶格距离

11. p =pow（path，- q ）# #计算（ u，w ）间产生连接的概率

12.if random.random（）＜ p ：#如果该边未被随机选中则继续选择可链接的节点

13. w=u

14.continue

15.else：

16. G .add_edge（ u，w ）#被选中则建立（ u，w ）的随机边

17.break

18.return G

完成以上对W-S-K模型的仿真，接下来将验证在不同 q 值下对应的网络特性。

如图3-16所示，可以发现，在 q 较小时，如图3-16 a所示，每个节点更多建立对较远节点的随机边， q 较大时，如图3-16 c所示，节点更易建立对临近节点的随机边。本节只介绍了W-S模型与W-S-K模型，并未介绍改进后的W-S模型，实际上，该模型与W-S-K的模型建立过程相似，只是在网格的晶格距离上定义有所不同，感兴趣的同学可以预设出基于社会距离的晶格网络，之后再进行W-S-K中的随机连边，就可以完成改进后的W-S模型仿真。