vlambda博客
学习文章列表

小世界网络模型

但是传统的随机图过于简单，难以模拟“现实世界”特征。许多现实世界网络通常具有两个特点：（1）任意节点对之间的距离都相对较小，（2）同时传递性或聚类的等级相对较高。因此，通过引入某种简单的机制来产生这些特征，是当代网络建模的重要创新之一。

就而言，它的平均路径长度确实很短，这意味着一对节点之间往往只有一条路径，而该路径只涉及少数几个边（即（1）成立）。但是，其缺乏一定程度的可传递性（但（2）不成立）。

增加传递性的一种方法是将所有节点排列在一个晶格中。最简单的格子是将节点排成一排，甚至将两端连接成一个圆，这样就不必担心边界。然后，如果每个节点只连接到附近的节点，那么结果网络中的传递性自然就会产生。由于连接到第三个节点的一对节点将趋向于靠近晶格中的每一个节点，因此很可能它们也已连接。即网络图中的数量将相对较高，产生高传递性或聚类（即满足了（2））。然而，这样的晶格模型中由于所有连接都是两个附近的节点，因此需要很长的连接链才能到达晶格上距离较远的节点。如果将节点排列在一个圆上，则圆相反处的节点之间的最短路径将非常大（但（1）将拒绝）。

下图展示了小型世界网络的特征，显示了网络（ℓ）和（C）随重连概率p改变的关系。

当概率p低时，大多数边仍然是原始的局部连接，它们连接的是晶格附近的节点，因此传递性仍然很高。但是，一些被重新连接的边可能会变成长距离的连接，连接晶格中彼此距离很远的节点，这些长距离连接会立即在任一端附近的节点之间创建一个短距离。这个结论隐含了这样一个事实，即路径长度将每条边的长度都计算为1，所以即使我们经常将它们作为长连接，它们也只向路径长度添加1。

当重连概率p变大时，网络将与相似，传递性变低。但是，存在一个较大的概率p的取值范围，在该范围内，聚类系数高且平均路径长度小，网络被认为是一个小世界网络。

考虑以下示例，通过R包igraph模拟小世界网络。

library(igraph)
 
#模拟小世界网络，详情 ?watts.strogatz.game
set.seed(123)
par(mfrow = c(2, 2))
 
#生成具有 Nv=25 个节点，r=5 个邻居，重连概率 p=0 的网络（p 越小，聚集性越高）
g_rand <- watts.strogatz.game(dim = 1, size = 25, nei = 5, p = 0)
plot(g_rand, layout = layout.circle)
 
#更改重连概率 p=0.01
g_rand <- watts.strogatz.game(dim = 1, size = 25, nei = 5, p = 0.01)
plot(g_rand, layout = layout.circle)
 
#更改重连概率 p=0.05
g_rand <- watts.strogatz.game(dim = 1, size = 25, nei = 5, p = 0.05)
plot(g_rand, layout = layout.circle)
 
#更改重连概率 p=0.1
g_rand <- watts.strogatz.game(dim = 1, size = 25, nei = 5, p = 0.1)
plot(g_rand, layout = layout.circle)

在具有相同数量节点和边的情况下，随着重连概率p的增加，网络传递性变低。

为了更清晰展示网络特征与重连概率p的关系，我们从p=0开始，依次增加0.01，直到0.5，模拟网络并绘制网络和随重连概率p改变的关系。

##在固定节点和边数量前提下，逐步增加重连概率 p 值的模拟
#模拟网络，并计算聚类系数和平均路径长度
clustering_coefficient <- c()
average_path_length <- c()
 
set.seed(123)
for (p in seq(0, 1, 0.01)) {
        g_rand <- watts.strogatz.game(dim = 1, size = 100, nei = 5, p = p)
        clustering_coefficient <- c(clustering_coefficient, transitivity(g_rand))
        average_path_length <- c(average_path_length, average.path.length(g_rand, directed = FALSE))
}
 
dat <- data.frame(p = seq(0, 1, 0.01),
        clustering_coefficient = clustering_coefficient,
        average_path_length = average_path_length)
 
#作图展示趋势
source('two_axis.r') #ggplot2 组合坐标轴，r 代码见 https://pan.baidu.com/s/1L-G96AhiqIZ5nvGInBFQvw#list/path=%2F
 
p1 <- ggplot(dat, aes(log10(p), clustering_coefficient)) +
geom_smooth(color = 'blue', se = FALSE) +
theme(axis.title.y = element_text(color = 'blue'))
 
p2 <- ggplot(dat, aes(log10(p), average_path_length)) +
geom_smooth(color = 'red', se = FALSE) +
theme(axis.title.y = element_text(color = 'red')) +
theme(panel.background = element_rect(fill = NA))
 
ggplot2.two_y_axis(p1, p2)

该曲线反映的趋势和上述一致，即随着重连概率p的增加，网络传递性变低。

比较小世界网络与经典随机网络。

##与经典随机图的比较
set.seed(123)
 
#生成具有 Nv=25 个节点，r=5 个邻居，重连概率 p=0.05 的网络
g_rand_s <- watts.strogatz.game(dim = 1, size = 25, nei = 5, p = 0.05)
 
#具有相同节点和边数量的经典随机图
g_rand_ER <- erdos.renyi.game(n = vcount(g_rand_s), p = ecount(g_rand_s), type = 'gnm', mode = 'undirected')
 
#网络图
par(mfrow = c(1, 2))
plot(g_rand_s, layout = layout.circle)
plot(g_rand_ER, layout = layout.circle)
 
#聚类系数和平均路径长度比较
transitivity(g_rand_s)
average.path.length(g_rand_s, directed = FALSE)
transitivity(g_rand_ER)
average.path.length(g_rand_ER, directed = FALSE)

在重连概率p为低值时，网络呈现小世界特征，低（与经典随机网络相似，低平均路径长度是它的特征）且高（相比之下明显高于经典随机网络的聚类系数）。

现在我们提升重连概率p，再比较二者。

#提升重连概率，再比较二者
set.seed(123)
 
#生成具有 Nv=25 个节点，r=5 个邻居，重连概率 p=0.2 的网络
g_rand_s <- watts.strogatz.game(dim = 1, size = 25, nei = 5, p = 0.2)
 
#具有相同节点和边数量的经典随机图
g_rand_ER <- erdos.renyi.game(n = vcount(g_rand_s), p = ecount(g_rand_s), type = 'gnm', mode = 'undirected')
 
#网络图
par(mfrow = c(1, 2))
plot(g_rand_s, layout = layout.circle)
plot(g_rand_ER, layout = layout.circle)
 
#聚类系数和平均路径长度比较
transitivity(g_rand_s)
average.path.length(g_rand_s, directed = FALSE)
transitivity(g_rand_ER)
average.path.length(g_rand_ER, directed = FALSE)

可以看到，当重连概率p为一个较高的值时，网络将不再具有小世界特征，归因于此时的低（接近随机网络，如果重连概率p继续提升还可能小于随机网络），失去了小世界对高传递性特征的要求。因此，此时原则上不能再称呼为“小世界”，此时的网络将呈现与经典随机图比较类似的特征。