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

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

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

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

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

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

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