# スモールワールドモデル Navigation: [[The structure and function of complex networks]] ## 定義 スモールワールドモデル(small-world model、Watts–Strogatz モデル)は、周期境界条件を持つ1次元格子(各頂点をリング上で k 個以下離れた頂点と接続)から出発し、各辺を確率 p で再配線することで、少数のパラメータ p のみで「規則格子(高クラスタリング・長い経路長)」から「ランダムグラフ的(低クラスタリング・短い経路長)」へ連続的に補間するグラフ生成モデルである(Watts and Strogatz [411, 412, 416])(出典: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 6 The small-world model]], p.27)。p=0 と p=1 の間には、低い経路長と高いクラスタリング係数を同時に持つ領域が存在し、これが多くの実ネットワークに見られる「small-world 効果」(短い平均距離と高いクラスタリングの共存)を再現する単純なモデルとして提案された動機である。指数ランダムグラフより単純だが、高い推移性を持つネットワークのモデルとして位置づけられる。 再配線の代わりに、下敷きの格子から辺を除去せずランダムなショートカットを追加する変種(Monasson、Newman and Watts が独立に提案)も並行して用いられ、こちらは頂点が孤立しないため頂点間平均距離が常に有限であるという利点を持つ。 ## 未解決の問い - 通常の small-world モデル(1次元、ショートカットあり)について、平均測地距離 ℓ の厳密解、および ℓ=ξg(L/ξ) の形のスケーリング関数 f(x)・g(x) の閉形式は得られていない(平均場近似と展開による近似のみ)。 - 高次元格子版・近接優先ショートカット版(Kleinberg のモデル)・格子なしショートカットのみの版について、詳細なスケーリング挙動の解明は完了していない。 ## 未編纂の観察 - 構成上、モデルには「再配線版」(辺の一端を再配線、Barrat and Weigt によるクラスタリング係数 C=[3(k-1)/(2(2k-1))](1-p)^3)と「ショートカット追加版」(辺を再配線せず追加、Newman によるクラスタリング係数 C=3(k-1)/[2(2k-1)+4kp(p+2)])の2つの主要な変種があり、解析的な扱いやすさのために両端再配線・多重辺許容の版も導入されている(Source: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 6 The small-world model]])。 - 平均測地距離のスケーリング指数 τ は、当初 Barthélémy and Amaral により数値的に τ=3/2 と見積もられたが、後に繰り込み群処理(Newman and Watts)とスケーリング的議論(Barrat)により τ=1 が正しいことが示された(Source: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 6 The small-world model]])。 - モデルの次数分布は多くの実ネットワークの次数分布とはあまり一致しないが、これはモデルの目的(高いクラスタリングと短い経路長の両立を示すこと)ではなかったため驚くことではない(Source: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 6 The small-world model]])。 - NCM ch.20 は Watts-Strogatz モデルを、2 次元格子上でホモフィリーによる近接リンク(半径 r 以内)と各ノード k 本のランダム長距離リンクの組み合わせとして定式化する。これは [[@2003__SIAMReview__The structure and function of complex networks - Chapter 6 The small-world model]] が扱う「1 次元リング上で各辺を確率 p で再配線する」定式化とはパラメータ化が異なる(近接半径 r・長距離本数 k による構成的モデル vs 再配線確率 p による連続補間モデル)が、少量のランダム性がクラスタリングを保ったまま経路長を短くするという定性的結論は共有する(Source: [[@2010__CambridgeUP__Networks, Crowds, and Markets - Chapter 20 The Small-World Phenomenon]], ch.20.2; [[@2003__SIAMReview__The structure and function of complex networks - Chapter 6 The small-world model]])。 - NCM ch.20 はスモールワールドモデルを分散探索(decentralized search)の基盤として拡張し、長距離リンク確率を d(v,w)^(-q) に比例させるクラスタリング指数 q を導入する(Kleinberg のモデル)。q が格子の次元に等しいとき分散探索が最も効率的になることを一次元リング上で証明しており(ch.20.7)、既存の未解決の問いに挙げられている「近接優先ショートカット版(Kleinberg のモデル)の詳細なスケーリング挙動」のうち、探索効率の最適指数の存在自体は本章で示されている。ただし本章が扱うのは静的なグラフ特性(クラスタリング係数・平均測地距離のスケーリング指数 τ)ではなく、探索という動的な過程の効率であり、既存の主題節(定義節)が扱う範囲とは独立した拡張である(Source: [[@2010__CambridgeUP__Networks, Crowds, and Markets - Chapter 20 The Small-World Phenomenon]], ch.20.3-20.4, ch.20.7)。 ## 関連 - 実体: [[Watts and Strogatz]]、[[Jon Kleinberg]] - source: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 6 The small-world model]] - ソース: [[@2010__CambridgeUP__Networks, Crowds, and Markets - Chapter 20 The Small-World Phenomenon]] ## 出典 - [[@2003__SIAMReview__The structure and function of complex networks - Chapter 6 The small-world model]]