Collective-dynamics-of-'small-world'-networks阅读报告.docx

Collective dynamics of 'small-world' networks

本篇论文中瓦茨和斯特罗加茨提出许多生物网络、技术网络和社会网络介于完全规则网和完全随机网之间，因此他们提出了一个模型来解释，后来被称为瓦茨-斯特罗加茨模型（简称WS模型），模型从一个完全的规则网络出发，以一定的概率将网络中的连接打乱重连。
WS模型以传染病为例提出：
1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的K个节点相连 
2、随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。

如果概率P=0，那么重连永远不会发生，最后得到的是原来的规则网络。如果概率，那么所有的连接都被重连了一次，最后得到的是一个完全的随机网络。而对于概率的情况，瓦茨和斯特罗加茨考察了集聚系数和平均路径长度与的关系，将这两者看作是关于P的函数：集聚系数C=C(P)，平均路径长度L=L(P)。他们发现，在P从0变到1的过程中，L(P)下降得很快，而C(P)下降的比较慢。

图中的横轴是P（使用对数坐标轴表示），纵轴是比值（介乎0与1之间）。从右图可以看到，L(P)/L(0)曲线很快就逐渐下降到0.2以下，而C(P)/C(0)曲线则超过P=0.1后才开始有显著下降。所以对于很小的P，L(P)可以很小，但C(P)可以很大，这正是小世界网络的特征。
通过本篇论文的阅读，主要了解了描述小世界现象的Watts-Strogatz模型，该模型指出小世界网络同时具有特征路径长度短和集群程度高的特点，它们并不能从规则网络或随机网络中推导出来，因此引入随机重连概率P模拟了规则网络和随机网络之间的情况，验证了小世界网络中短路径的存在性。虽然模型较好地验证了短路径的存在，但是并没有具体指出如何找到这些短路径，因此还需要在进一步优化模型来找到短路径。