Документация

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

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

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

Файл WattsStrogatz.m реализует этот алгоритм графика для неориентированных графов. Входными параметрами является N, K и beta согласно описанию алгоритма выше.

Просмотрите файл WattsStrogatz.m m.

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

% Copyright 2015 The MathWorks, Inc.

Кольцевая решетка

Создайте кольцевую решетку с 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')

Распределение градуса

Распределение градуса узлов в различных графиках Ватт-Strogatz отличается. Когда 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')

Концентрация формирования

График Ватт-Strogatz имеет высокий коэффициент кластеризации, таким образом, узлы имеют тенденцию формировать клики или небольшие группы тесно соединенных узлов. Когда 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