一、概述
小世界网络模型是指某些网络具有局部集聚性和全局短距离特征的网络结构模型。
最早由Duncan J. Watts和Steven H. Strogatz于1998年提出,他们将小世界模型定义为介于完全随机和完全规则的网络模型。该模型呈现了群聚和短路径的特点。
二、特点
小世界网络模型具有以下特点:
1、集聚性:局部节点之间相对密集地连接。
2、短路径:全局通过少量的中间节点就能够互相连通。
3、随机性:节点之间连接的随机性,使得网络比起完全规则的网络更具有鲁棒性。
三、生成算法
Watts和Strogatz用以下的生成算法构造小世界模型:
1. 构建一个普通的、具有n个节点、每个节点有k个近邻的Lattice网络
2. 依次考虑网络中每个节点,并使用以下的方式重新连接网络中该节点的某些近邻:
1)对每个节点i和每个k/2的近邻(按逆时针方向,共k个节点),以概率p重新连接,
2)如果存在重边则不进行。
3)它增加了整个网络的随机性,而该网络构成保持高度集聚的特性。
四、Python实现代码示例
以下是使用Python实现小世界网络模型的代码示例:
import networkx as nx
import random
def watts_strogatz_graph(n, k, p):
G = nx.generators.random_graphs.random_regular_graph(k, n)
for i in range(n):
nodes = [j for j in range(i - k // 2, i + k // 2 + 1)]
nodes.remove(i)
for j in nodes:
if j < 0 or j >= n:
continue
if random.random() < p:
G.remove_edge(i, j)
x = random.randint(0, n - 1)
while G.has_edge(i, x):
x = random.randint(0, n - 1)
G.add_edge(i, x)
return G
五、应用
小世界网络模型具有广泛的应用领域,在社交网络、生物信息学、通信网络等方面常用于研究节点之间的连接方式和性质。
例如,在社交网络中,人们往往会选择一些朋友进行交流,这就构成了局部密集连接。但是,社交网络之间几乎任何人之间都能通过短路程互相连通,这就构成了全局短距离特征。此时,小世界网络模型就是一种较好的描述方法。
六、总结
小世界网络模型是一种具有局部集聚性和全局短距离特征的网络结构模型。它的主要特点包括集聚性、短路径和随机性。它的生成算法是通过构建一个普通的节点k近邻网络,再随机重连部分边构成的。小世界网络模型的应用范围十分广泛,在社交网络、生物信息学、通信网络中都能发挥重要作用。