ワッツ・ストロガッツモデル

ワッツ・ストロガッツモデルは、平均パス長が短く、クラスタリングが高いなど、スモールワールド特性を持つグラフを生成するランダムグラフ生成モデルです。このモデルは、ダンカン・J・ワッツとスティーブン・ストロガッツが1998年に科学雑誌「ネイチャー」に発表した論文で提案しました。^{[1]このモデルは、ワッツが彼の人気科学書}「シックス・ディグリーズ」で定式化したことから、(ワッツ)ベータモデルとしても知られています。 ${\displaystyle \beta }$

ランダムグラフの正式な研究は、ポール・エルデシュとアルフレッド・レーニの研究にまで遡ります。^[2]彼らが検討したグラフは現在、古典的グラフまたはエルデシュ・レーニ（ER）グラフとして知られており、多くの用途を持つシンプルで強力なモデルを提供します。

しかし、ERグラフには、多くの現実世界のネットワークで観察される 2 つの重要な特性がありません。

1. ER グラフは、ローカル クラスタリングや3 項閉包を生成しません。代わりに、2 つのノードが接続される確率が一定でランダムかつ独立しているため、クラスタリング係数は低くなります。
2. これらはハブの形成を考慮していない。正式には、ERグラフの次数分布は、多くの現実世界のスケールフリーネットワークで観察されるべき乗法則ではなく、ポアソン分布に収束する。^[3]

ワッツとストロガッツのモデルは、2 つの制限のうち最初の制限に対処する最も単純なモデルとして設計されました。このモデルは、ER モデルの短い平均パス長を維持しながらクラスタリングを考慮します。これは、ER グラフに近いランダム構造と通常のリング格子の間を補間することによって行われます。その結果、このモデルは、電力網、C. elegansのニューラル ネットワーク、映画俳優のネットワーク、出芽酵母の脂肪代謝コミュニケーションなど、さまざまなネットワークにおける「スモール ワールド」現象を少なくとも部分的に説明できます。^[4]

必要なノード数、平均次数（偶数と仮定）、およびパラメータ（すべて および を満たす）が与えられると、モデルは次のように ノードとエッジを持つ無向グラフを構築します。${\displaystyle N}$ ${\displaystyle K}$${\displaystyle \beta }$${\displaystyle 0\leq \beta \leq 1}$${\displaystyle N\gg K\gg \ln N\gg 1}$${\displaystyle N}$${\displaystyle {\frac {NK}{2}}}$

1. 正則リング格子、つまり各辺に隣接するノードが接続されたグラフを構築します。つまり、ノードにラベルが付けられている場合 、次の場合にのみ辺が存在します。${\displaystyle N}$${\displaystyle K}$${\displaystyle K/2}$${\displaystyle 0\ldots {N-1}}$${\displaystyle (i,j)}$${\displaystyle 0<|i-j|\ \mathrm {mod} \ \left(N-1-{\frac {K}{2}}\right)\leq {\frac {K}{2}}.}$
2. すべてのノードについて、その右端の隣接ノードに接続するすべてのエッジ、つまり となるすべてのエッジを取得し、確率 で再配線します。再配線はと置き換えることによって行われます。ここで は、自己ループ ( ) とリンクの重複を回避しながら、すべての可能なノードから一様にランダムに選択されます(アルゴリズムのこの時点ではとなるエッジはありません)。${\displaystyle i=0,\dots ,{N-1}}$${\displaystyle i}$${\displaystyle K/2}$${\displaystyle (i,j)}$${\displaystyle 0<(j-i)\ \mathrm {mod} \ N\leq K/2}$${\displaystyle \beta }$${\displaystyle (i,j)}$${\displaystyle (i,k)}$${\displaystyle k}$${\displaystyle k\neq i}$${\displaystyle (i,{k'})}$${\displaystyle k'=k}$

モデルの基本的な格子構造は、ローカルにクラスター化されたネットワークを生成する一方で、ランダムに再配線されたリンクは平均パス長を劇的に短縮します。アルゴリズムは、約 のこのような非格子エッジを導入します。 をに変更すると、通常の格子 ( ) と、でエルデシュ・レーニイランダムグラフに近い構造との間の補間が可能になります。すべてのノードが少なくとも他のノードに接続されるため、実際の ER モデルに近づくことはありません。 ${\displaystyle \beta {\frac {NK}{2}}}$${\displaystyle \beta }$${\displaystyle \beta =0}$ ${\displaystyle G(N,p)}$${\displaystyle p={\frac {K}{N-1}}}$${\displaystyle \beta =1}$${\displaystyle K/2}$

興味深い 3 つの特性は、平均パス長、クラスタリング係数、次数分布です。

リング格子の場合、平均経路長^[1]はであり、システムサイズに比例して増加します。の極限の場合、グラフは のランダムグラフに近づきますが、実際には収束しません。 中間領域 では、平均経路長は の増加とともに急速に減少し、すぐに極限値に近づきます。 ${\displaystyle \ell (0)\approx N/2K\gg 1}$${\displaystyle \beta \rightarrow 1}$${\displaystyle \ell (1)\approx {\frac {\ln N}{\ln K}}}$${\displaystyle 0<\beta <1}$${\displaystyle \beta }$

リング格子の場合、クラスタリング係数^[5] は、システムのサイズとは無関係に、 が大きくなるにつれて に近づく傾向があります。 ^[6]クラスタリング係数の極限ケースでは、は古典的なランダムグラフのクラスタリング係数と同じオーダーであり、したがってシステムのサイズに反比例します。中間領域では、クラスタリング係数は通常の格子の値に非常に近いままであり、比較的高い でのみ低下します。この結果、平均パス長は急速に低下しますが、クラスタリング係数は低下しない領域が生じ、「スモールワールド」現象が説明されます。 ${\displaystyle C(0)={\frac {3(K-2)}{4(K-1)}}}$${\displaystyle 3/4}$${\displaystyle K}$${\displaystyle \beta \rightarrow 1}$${\displaystyle C=K/(N-1)}$${\displaystyle \beta }$

クラスタリングの尺度として定義されるバラットとワイグト^[6]の尺度を、ノードの隣接ノード間のエッジの平均数と、これらの隣接ノード間の可能なエッジの平均数との間の割合として定義すると、あるいは、${\displaystyle C'(\beta )}$

${\displaystyle C'(\beta )\equiv {\frac {3\times {\text{number of triangles}}}{\text{number of connected triples}}}}$

すると${\displaystyle C'(\beta )\sim C(0)(1-\beta )^{3}.}$

リング格子の場合の次数分布は、を中心とするディラックのデルタ関数に過ぎません。多数のノードとに対する次数分布は、次のように表すことができます。^[6]${\displaystyle K}$${\displaystyle 0<\beta <1}$

${\displaystyle P(k)\approx \sum _{n=0}^{f(k,K)}{{K/2} \choose {n}}(1-\beta )^{n}\beta ^{K/2-n}{\frac {(\beta K/2)^{k-K/2-n}}{(k-K/2-n)!}}e^{-\beta K/2},}$

ここで、 はノードが持つエッジの数、またはその次数です。ここで 、 、 です。次数分布の形状はランダム グラフの形状に似ており、 で顕著なピークを持ち、 が大きい では指数関数的に減少します。ネットワークのトポロジは比較的均質であり、すべてのノードの次数が同様であることを意味します。 ${\displaystyle k_{i}}$${\displaystyle i^{\text{th}}}$${\displaystyle k\geq K/2}$${\displaystyle f(k,K)=\min(k-K/2,K/2)}$${\displaystyle k=K}$${\displaystyle |k-K|}$

このモデルの主な制限は、非現実的な次数分布を生成することです。対照的に、現実のネットワークは、ハブとスケールフリーの次数分布を持つ、次数が不均一なスケールフリー ネットワークであることが多いです。そのようなネットワークは、その点では、バラバシ–アルバート (BA) モデルなどの優先接続モデル ファミリによってより適切に説明されます。(一方、バラバシ–アルバート モデルは、現実のネットワークで見られる高度なクラスタリングを生成することができません。これは、ワッツとストロガッツのモデルにはない欠点です。したがって、ワッツとストロガッツのモデルもバラバシ–アルバート モデルも完全に現実的であると見なすべきではありません。)

Watts と Strogatz のモデルもノード数が固定されていることを意味するため、ネットワークの成長をモデル化するために使用することはできません。

• スモールワールドネットワーク
• エルデシュ・レーニ (ER) モデル
• バラバシ・アルバートモデル
• ソーシャルネットワーク