生成瓦茨-斯特罗加茨小世界图形模型

此示例演示如何构建并分析瓦茨-斯特罗加茨小世界图形。瓦茨-斯特罗加茨模型是一个包含小世界网络属性（例如集群和平均短路径长度）的随机图形。

算法说明

创建瓦茨-斯特罗加茨图形包含以下两个基本步骤：

创建一个环形网格，其中包含个平均出入度为的节点。每个节点都与任一侧的个最近邻点相连。
对于图中的每条边，重新连接概率为 $\beta$ 的目标节点。重新连接的边不能是重复或自环的。

执行第一步操作之后，图形将是一个完美的环形网格。因此当 $\beta = 0$ 时，不会重新连接任何边，并且该模型会返回一个环形网格。而如果 $\beta = 1$ ，则所有边都将重新连接，并且环形网格会变成随机图形。

文件 WattsStrogatz.m 对无向图实现该图算法。根据上面的算法说明，输入参数为 N、K 和 beta。

查看文件 WattsStrogatz.m。


% Copyright 2015 The MathWorks, Inc.

function h = WattsStrogatz(N,K,beta)
% H = WattsStrogatz(N,K,beta) returns a Watts-Strogatz model graph with N
% nodes, N*K edges, mean node degree 2*K, and rewiring probability beta.
%
% beta = 0 is a ring lattice, and beta = 1 is a random graph.

% Connect each node to its K next and previous neighbors. This constructs
% indices for a ring lattice.
s = repelem((1:N)',1,K);
t = s + repmat(1:K,N,1);
t = mod(t-1,N)+1;

% Rewire the target node of each edge with probability beta
for source=1:N    
    switchEdge = rand(K, 1) < beta;
    
    newTargets = rand(N, 1);
    newTargets(source) = 0;
    newTargets(s(t==source)) = 0;
    newTargets(t(source, ~switchEdge)) = 0;
    
    [~, ind] = sort(newTargets, 'descend');
    t(source, switchEdge) = ind(1:nnz(switchEdge));
end

h = graph(s,t);
end

环形网格

使用 WattsStrogatz 函数构建包含 500 个节点的环形网格。beta 为 0 时，该函数会返回其节点出入度均为 2K 的环形网格。

h = WattsStrogatz(500,25,0);
plot(h,'NodeColor','k','Layout','circle');
title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 0$', ...
    'Interpreter','latex')

一些随机边

通过将 beta 增大到 0.15 和 0.50，增加图形中的随机性。

h2 = WattsStrogatz(500,25,0.15);
plot(h2,'NodeColor','k','EdgeAlpha',0.1);
title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 0.15$', ...
    'Interpreter','latex')

h3 = WattsStrogatz(500,25,0.50);
plot(h3,'NodeColor','k','EdgeAlpha',0.1);
title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 0.50$', ...
    'Interpreter','latex')

随机图形

通过将 beta 增大到其最大值 1.0，生成一个完全随机的图形。这会重新连接所有边。

h4 = WattsStrogatz(500,25,1);
plot(h4,'NodeColor','k','EdgeAlpha',0.1);
title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 1$', ...
    'Interpreter','latex')

出入度分布

不同瓦茨-斯特罗加茨图形中节点的出入度分布会有所不同。beta 为 0 时，这些节点的出入度均为 2K，因此出入度分布只是一个以 2K 为中心的 Dirac-delta 函数 $\delta(x-2K)$ 。但是，随着 beta 的增大，出入度分布也会发生变化。

该绘图显示 beta 的非零值的出入度分布。

histogram(degree(h2),'BinMethod','integers','FaceAlpha',0.9);
hold on
histogram(degree(h3),'BinMethod','integers','FaceAlpha',0.9);
histogram(degree(h4),'BinMethod','integers','FaceAlpha',0.8);
hold off
title('Node degree distributions for Watts-Strogatz Model Graphs')
xlabel('Degree of node')
ylabel('Number of nodes')
legend('\beta = 1.0','\beta = 0.50','\beta = 0.15','Location','NorthWest')

枢纽的形成

瓦茨-斯特罗加茨图形具有较大的集群系数，因此节点往往会形成团或较小的紧密互联的节点组。当 beta 朝其最大值 1.0 方向增加时，您会看到枢纽节点或度数相对较高的节点的数量不断增加。枢纽是其他节点之间以及图形中的团之间的常见连接。枢纽之所以存在，旨在允许形成团的同时保留平均短路径长度。

对 beta 的每个值计算平均路径长度和枢纽节点数量。就此示例而言，枢纽节点是指出入度大于或等于 55 的节点。与原始环形网格相比，这些节点的出入度全都增加了 10% 或更多。

n = 55;
d = [mean(mean(distances(h))), nnz(degree(h)>=n); ...
     mean(mean(distances(h2))), nnz(degree(h2)>=n); ...
     mean(mean(distances(h3))), nnz(degree(h3)>=n);
     mean(mean(distances(h4))), nnz(degree(h4)>=n)];
T = table([0 0.15 0.50 1]', d(:,1), d(:,2),...
    'VariableNames',{'Beta','AvgPathLength','NumberOfHubs'})

T =

  4x3 table

    Beta    AvgPathLength    NumberOfHubs
    ____    _____________    ____________

       0         5.48              0     
    0.15       2.0715             20     
     0.5       1.9101             85     
       1       1.9008             92

随着 beta 的增大，图形中的平均路径长度很快减少到其极限值。这是由于形成了紧密连接的枢纽节点，枢纽节点的数量将随着 beta 的增大而变得更多。

绘制 $\beta = 0.15$ 瓦茨-斯特罗加茨模型图，使每个节点的大小和颜色与其出入度成比例。这是使枢纽形成过程可视化的有效方式。

colormap hsv
deg = degree(h2);
nSizes = 2*sqrt(deg-min(deg)+0.2);
nColors = deg;
plot(h2,'MarkerSize',nSizes,'NodeCData',nColors,'EdgeAlpha',0.1)
title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 0.15$', ...
    'Interpreter','latex')
colorbar

另请参阅

digraph | graph