小世界网络
在《Collective dynamics of ‘small-world’ networks》中,Watts和Strogatz发现了复杂网络中一种具有特殊现象的网络–小世界网络(small-world)。他们注意到复杂网络可以按照两个独立的结构特性分类——集聚系数和平均路径长度。
在网络中,某个的集聚系数是指这个点与邻居的连边数与这些顶点之间可以连出的最大边数的商值,这个指标反映了这个点附近点的抱团行为,也就是集聚行为,一个点的集聚系数越大,说明他所处的位置的社团行为更加明显,更进一步,若网络上的平均集聚系数更大,说明网络内部的社团行为更明显。某个点的平均最短路径是指该点到网络其他点的最短距离的平均值,它一定程度上反映里该点进行信息交流的能力,这个值越小,说明该点的获得信息和传播信息能力越强,而一个网络的平均最短距离越小,说明信息在网络上的传播速度更强。
一般而言,随机网络的集聚系数和平均最短距离都很小。而小世界网络的集聚系数很大,平均最短距离小,这就意味着小世界网络会有各种明显的社团形式的存在。
对于网络上的结点来说,为了获得信息而形成链接,但是形成链接是需要付出能量代价的,所以我们总希望网络的边越少的同时平局最短距离越小,并且尽可能保证网络的连通性。显然,一个网络中所有结点都互相认识,平局最短距离最小=1,但是,这样每次增加一个新节点要增加的边就会越来越多,为了希望能量消耗更小,就需要有某些结点承担一群人与另一群人的信息交流问题,而小世界网络就对这个问题给出了很好的解答。
所以小世界网络的实际背景应该是,在一个大规模网络上,:一个结点应当有有限的注意力(结点连边边数有限),并且它会更倾向与共同邻居多的点连边。而无标度网络则是单纯倾向与度大的点链接,这也是无标度网络与小世界网络的最大区别。