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

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

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

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