Main Content

このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

ワッツ・ストロガッツのスモール ワールド グラフのモデル作成

この例では、ワッツ・ストロガッツのスモール ワールド グラフを作成し、解析する方法を示します。ワッツ・ストロガッツのモデルは、クラスタリングや短い平均経路長など、スモール ワールド ネットワークのプロパティをもつランダム グラフです。

アルゴリズムの説明

ワッツ・ストロガッツ グラフの作成には 2 つの基本ステップがあります。

  1. 平均次数が $2K$ である $N$ 個のノードでリング状格子を作成します。各ノードはいずれの側でも $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

リング状格子

関数 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')

ある程度のランダムなエッジ

beta0.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')

次数分布

ワッツ・ストロガッツのグラフにおけるノードの次数分布は、グラフに応じて変化します。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')

ハブ形成

ワッツ・ストロガッツのグラフは高いクラスタリング係数をもっているため、ノードはクリーク、すなわち密接に相互接続しているノードの小さなグループを形成する傾向があります。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

参考

|