随机加边才让世界变得更小

我们投Chaos的稿件《Synchronizability of Small-world Networks Generated from Ring Networks with Equal-Distance Edge Additions》（作者：汤龙坤，陆君安，陈关荣）最近刚刚录用，这篇文章我们大概做了将近一年，在研究过程中，对NW小世界网络模型有了新的认识，真正体会到：随机加边才让世界变得更小！

NW小世界网络模型是在邻近规则网络基础上随机化加少量的边生成的网络。我们把邻近规则网络（就取环状网络）上两个节点i和j的距离记为dij,我们做的事情是构建了一种等距随机加边的网络，在环状网络基础上固定相同的加边距离进行加边，大规模多次地计算这种固定加边距离的网络的平均距离和Laplacian矩阵的最小非零特征值。选节点数N=2000的环状网络上，固定相同的加边距离d（譬如d=50,100,150,…,1000）加边（边数由加边概率p控制），加的边数从10到600，显然，加的边数越多，网络的平均距离越小（同时Laplacian矩阵的最小非零特征值也越大，同步能力提高）。可是，没有预料到的现象发生了，当固定加边概率p条件下，平均距离（或者最小非零特征值）关于加边距离d是波动的，而且在某些d值上达到极小值（或者极大值），也就是某些d值的加边方式比另外一些d值的加边方式产生的网络平均距离小，同时这个极小值（或者极大值）不随加边概率p而变化。然后我们计算在环状网络上随机地加边（NW网络），边数与固定相同加边距离的方式一样多，于是发现了更重要的结果：随机加边网络的平均距离比固定加边距离的网络的平均距离的极小值还小得多，最小非零特征值比固定加边距离的网络的最小非零特征值的极大值也大得多。这就说明人为刻意地固定加边距离构造的网络，远不如随机加边构造的网络具有小世界的性质，同步能力也远不如随机加边的网络来得好。那么这究竟是什么原因呢？当在邻近规则网络上随机加边时，对于固定的两点，就能够提供“丰富多彩”的d的加边可能，从一个点到另一个点，就有很多优选的可能，从而很容易取得最短路径，而固定加边距离却不能提供“丰富多彩”的d的加边可能，所以随机加边更有利于平均距离的缩小，更加有利于节点之间的“信息交流”，从而更有利于同步；而刻意的取一种d的加边方式并不有利于节点之间的“信息交流”和平均距离的缩小。这一发现使我们对NW小世界网络有了新的认识：随机加边的NW小世界网络具有天然的优越性，随机加边才让世界变得更小！