Построение графа "мир тесен" Ватца-Строгаца

В этом примере показано, как создать и анализировать граф "мир тесен" Ватца-Строгаца. Модель Ватца-Строгаца является случайным графиком, который имеет маленько-мировые сетевые свойства, такие как кластеризация и короткая средняя длина пути.

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

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

  1. Создайте кольцевую решетку с$N$ узлами средней степени$2K$. Каждый узел соединяется со своими$K$ самыми близкими соседями с обеих сторон.

  2. Для каждого ребра в графике повторно соедините целевой узел с вероятностью$\beta$. Пересоединенное проводом ребро не может быть копией или самоциклом.

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

Файл 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$\delta(x-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 увеличения.

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

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

Смотрите также

|