Описание алгоритма

Создание графа Ваттса-Строгатца включает два основных шага:

После первого шага граф представляет собой совершенную кольцевую решётку. Таким образом, когда, никакие ребра не перемотаны, и модель возвращает кольцевую решетку. В противоположность этому, когда все рёбра перемотаны и кольцевая решетка преобразуется в случайный граф.

Файл 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

Решетка кольца

Построение кольцевой решетки с 500 узлами с помощью WattsStrogatz функция. Когда 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, . Однако, как 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 увеличивается.

Постройте график модели Ваттса-Строгатца, сделав размер и цвет каждого узла пропорциональными его степени. Это эффективный способ визуализации формирования хабов.

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