浅谈小世界网络 20世纪末，很多科学家发现研究过的自然、社会和技术网络中，大都具有这些特征：高度的集群性、不均衡的度分布以及中心节点结构。这些特征的出现不是偶然的，为什么现实世界中的网络会具有这些特征呢？这是网络科学的主要问题，目前基本上已经通过建立网络的发展模型解决了。其中有两类模型被深入地进行了研究，分别是小世界网络和无尺度网络，这里结合原始论文谈谈对小世界网络的认识。 1998年，邓肯·瓦特和斯托加茨在《自然》杂志上发表了关于小世界网络模型的论文Collectivedynamics of‘small-world’ networks，首次提出并从数学上定义了小世界概念，并预言它会在社会、自然、科学技术等领域具有重要的研究价值。 所谓小世界网络，就是相对于同等规模节点的随机网络，具有较短的平均路径长度和较大的聚类系数特征的网络模型。以前，人们认为网络分为完全规则网和完全随机网，这两类网络具有各自的特征。规则网具有较大的特征路径长度，聚类系数也较大，而随机网络具有较小的特征路径长度，但是聚类系数较小。难道特征路径长度较大（小）一定伴随着较大（小）的聚类系数？另外，很多现实中的网络如电网，交通网络，脑神经网络，社交网络，食物链等都表现出小世界特性，即具有较小的特征路径长度。 Watt采用一种随机重连边的方法，以探求位于规则网和随机网的中间地带。如图： 规则网有N个节点,每个节点与K个最近邻节点相连（K是偶数）。上图的规则网有20个节点，每个节点与相邻的4个节点互联。然后，对每条边进行以概率P进行随机重连（0<=P<=1）。P=0时对应规则网，P=1时对应完全随机网，通过调整P的值可以得到位于两种网络中间的网络模型，然后探究其特征。 通过实验并统计网络呈现出的特征，得到下图（归一化处理后）。 可见，在P较小时(P<0.01)，特征路径长度急剧下降，而聚类系数几乎没有变化。这样，我们发现这些网络具有较短的特征路径长度和较大的聚类系数，我们称其为“小世界网络”。为了验证试验结果的稳定性，作者采用了多种不同的规则网络和随机重连算法进行试验，得到了相同的结果. 那么为什么会出现这种特征呢？关键是“捷径”的添加。所谓“捷径”，即随机重连过程中添加的长边。如试验中P<0.01时，规则网络中会添加极少量的长边，不仅使长边两端的节点（假定A和B）路径长度变小，而且A节点的和B节点的邻居乃至B的邻居的邻居之间距离都变小了。于此同时，随机重连对网络的聚类系数影响很小，至多是线性减少。于是，P较小时生成的网络具有小世界特征。当P较大时，随着长边的增多，网络的聚类系数开始迅速变小，向完全随机化网络演变。 在论文中，通过对三个现实中的案例：美国西部的电力网络、电影演员的协作网络、蠕虫的神经网络分析，发现三者都具有小世界特征，如下图。 人们发现在具有小世界特征的动力系统中，信息的传播能力、计算能力等都得到了增强。瓦茨认为;局部行为导致了全局性的结果，而局部动态特性和全局动态特性之间的关系，则主要依赖于网络的结构。在这篇论文中，作者利用人群中传染病的传播、博弈论中合作的演化、元胞自动机的计算能力、耦合相位振子的同步等具有小世界特征的动力系统进行了研究，并对小世界的前途进行了展望。 为什么很多现实网络具有“小世界特征”？ 结合现有假说和自己的理解，可能是以下原因; 1、由于现实的需要，如交流、效率、成本等原因，真实网络中存在着“捷径”。 2、“捷径”的数量与需求相匹配。 3、“捷径”的生成和维护往往需较高的“代价”。 本文来源：https://www.wddqw.com/doc/3b302f0724d3240c844769eae009581b6bd9bdf9.html