와츠-스트로가츠의 좁은 세상 그래프 모델(Watts-Strogatz Small World Graph Model) 생성하기
이 예제에서는 와츠-스트로가츠의 좁은 세상 그래프를 생성하고 분석하는 방법을 보여줍니다. 와츠-스트로가츠 모델은 클러스터링과 짧은 평균 경로 길이 등의 좁은 세상 네트워크 속성을 갖는 랜덤 그래프입니다.
알고리즘 설명
와츠-스트로가츠 그래프를 만들려면 다음 두 가지 기본 단계를 수행해야 합니다.
평균 차수가 인 개의 노드를 갖는 링 모양 격자를 만듭니다. 각 노드는 양쪽으로 개의 최근접이웃 노드에 연결됩니다.
그래프의 각 간선에 대해, 확률 를 사용하여 타깃 노드를 재연결합니다. 재연결된 간선은 중복 간선이거나 자가 루프일 수 없습니다.
첫 번째 단계를 수행한 후에 그래프는 완벽한 링 모양 격자가 됩니다. 따라서 이면 어떤 간선도 재연결되지 않으며, 모델은 링 모양 격자를 반환합니다. 반대로, 이면 모든 간선이 재연결되며, 링 모양 격자가 랜덤 그래프로 변형됩니다.
파일 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) 가 됩니다. 그러나 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
값이 증가하면서 점점 더 많아지는, 밀접하게 연결된 허브 노드의 형성으로 인한 것입니다.
각 노드의 크기와 색을 차수에 비례하게 하여 인 와츠-스트로가츠 모델 그래프를 플로팅해 보겠습니다. 이렇게 하면 허브의 형성을 효과적으로 시각화할 수 있습니다.
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