와츠-스트로가츠의 좁은 세상 그래프 모델(Watts-Strogatz Small World Graph Model) 생성하기

이 예제에서는 와츠-스트로가츠의 좁은 세상 그래프를 생성하고 분석하는 방법을 보여줍니다. 와츠-스트로가츠 모델은 클러스터링과 짧은 평균 경로 길이 등의 좁은 세상 네트워크 속성을 갖는 랜덤 그래프입니다.

알고리즘 설명

와츠-스트로가츠 그래프를 만들려면 다음 두 가지 기본 단계를 수행해야 합니다.

평균 차수가 인 개의 노드를 갖는 링 모양 격자를 만듭니다. 각 노드는 양쪽으로 개의 최근접이웃 노드에 연결됩니다.
그래프의 각 간선에 대해, 확률 $\beta$ 를 사용하여 타깃 노드를 재연결합니다. 재연결된 간선은 중복 간선이거나 자가 루프일 수 없습니다.

첫 번째 단계를 수행한 후에 그래프는 완벽한 링 모양 격자가 됩니다. 따라서 $\beta = 0$ 이면 어떤 간선도 재연결되지 않으며, 모델은 링 모양 격자를 반환합니다. 반대로, $\beta = 1$ 이면 모든 간선이 재연결되며, 링 모양 격자가 랜덤 그래프로 변형됩니다.

파일 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

링 모양 격자

WattsStrogatz 함수를 사용하여 500개의 노드를 갖는 링 모양 격자를 생성합니다. 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')

차수 분포

노드의 차수 분포는 와츠-스트로가츠 그래프(Watts-Strogatz Graph)마다 다릅니다. beta가 0이면 노드는 모두 동일한 차수 2K를 가지므로, 차수 분포는 2K를 중심으로 하는 디랙 델타 함수(Dirac-delta Function) $\delta(x-2K)$ 가 됩니다. 그러나 beta 값이 증가하면 차수 분포가 달라집니다.

다음 플롯은 0이 아닌 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')

허브(Hub) 형성

와츠-스트로가츠 그래프(Watts-Strogatz Graph)는 클러스터링 계수가 높기 때문에, 노드가 밀접하게 상호 연결된 작은 그룹인 클릭(Clique)을 형성하기 쉽습니다. 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

참고 항목

digraph | graph