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

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

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

Файл WattsStrogatz.m реализации этот алгоритм графика для неориентированных графов. Входными параметрами является NK, и 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