スモールワールドネットワーク

スモールワールドネットワークは、高いクラスタリング係数と低い距離を特徴とするグラフです。ソーシャルネットワークの例では、高いクラスタリングは、1人の友人2人が友人である可能性が高いことを意味します。一方、距離が短いということは、2人の間に社会的つながりの連鎖が短いことを意味します（この効果は6次の隔たりとして知られています）。^[1]具体的には、スモールワールドネットワークは、ランダムに選択された2つのノード間の典型的な距離L（必要なステップ数）が、ネットワーク内のノード数Nの対数に比例して増加するネットワークとして定義されます。つまり、次のようになります。^[2]

${\displaystyle L\propto \log N}$

一方、グローバルクラスタリング係数は小さくありません。

ソーシャルネットワークの文脈では、これは見知らぬ人同士が知り合いの短い連鎖で結びつくというスモールワールド現象につながります。ソーシャルネットワーク、Wikipediaなどのウィキ、遺伝子ネットワーク、さらにはインターネットの基礎となるアーキテクチャなど、多くの実証グラフがスモールワールド効果を示しています。これは、現代のコンピュータハードウェアの多くのネットワークオンチップアーキテクチャのインスピレーションとなっています。^[3]

スモールワールドネットワークの特定のカテゴリは、1998 年にDuncan WattsとSteven Strogatzによってランダムグラフのクラスとして特定されました。 ^[4]彼らは、グラフは 2 つの独立した構造的特徴、つまりクラスタリング係数と平均ノード間距離(平均最短経路長とも呼ばれる) に従って分類できることに注目しました。Erdős –Rényi (ER) モデルに従って構築された純粋なランダムグラフは、小さな平均最短経路長 (通常はノード数の対数として変化) と小さなクラスタリング係数を示します。Watts と Strogatz は、実際には多くの現実世界のネットワークの平均最短経路長は短いが、クラスタリング係数はランダムな偶然によって予想されるよりも大幅に高いことを測定しました。その後、Watts と Strogatz は、(i) 平均最短経路長が小さく、(ii) クラスタリング係数が大きい、現在Watts and Strogatz モデルと呼ばれている新しいグラフモデルを提案しました。ワッツ・ストロガッツモデルにおける「大きな世界」（格子など）と小さな世界との間のクロスオーバーは、1999年にバルテルミーとアマラルによって初めて説明されました。^[5]この研究に続いて、正確な結果を含む多くの研究が行われました（バラットとワイグト、1999年、ドロゴフツェフとメンデス、バーンプティスとマレー、2010年）。

スモールワールド ネットワークには、クリークやニアクリークが含まれる傾向があります。ニアクリークとは、ネットワーク内のほぼすべての 2 つのノード間が接続しているサブネットワークのことです。これは、クラスタリング係数が高いという定義特性から生じます。次に、ほとんどのノード ペアは、少なくとも 1 つの短いパスで接続されます。これは、平均最短パス長が短いという定義特性から生じます。スモールワールド ネットワークには、他のいくつかの特性も関連付けられることがよくあります。通常、ハブ、つまりネットワーク内の接続数が多いノード (高次ノードと呼ばれる)が過剰に存在します。これらのハブは、他のエッジ間の短いパス長を仲介する共通の接続として機能します。類推すると、航空便のスモールワールド ネットワークの平均パス長は短くなります (つまり、任意の 2 つの都市間では、3 回以下のフライトを利用する必要があります)。これは、多くのフライトがハブ都市を経由しているためです。この特性は、多くの場合、ネットワーク内の特定の数の接続を持つノードの割合 (ネットワークの次数分布) を考慮して分析されます。予想よりも多くのハブを持つネットワークでは、高次数のノードの割合が多くなり、その結果、次数分布は高次数値で豊かになります。これは、口語的にはファットテール分布として知られています。非常に異なるトポロジのグラフは、上記の 2 つの定義要件を満たす限り、スモールワールド ネットワークとして適格です。

ネットワークのスモールワールド性は、与えられたネットワークのクラスタリングとパス長を平均して同じ次数のエルデシュ・レーニモデルと比較することによって計算される小さな係数によって定量化されている。 ^{[6] [7]}${\displaystyle \sigma }$

${\displaystyle \sigma ={\frac {\frac {C}{C_{r}}}{\frac {L}{L_{r}}}}}$

（および）の場合、ネットワークはスモールワールドです。ただし、この指標はネットワークのサイズに大きく影響されるため、パフォーマンスが低下することが知られています。^{[8] [9]}${\displaystyle \sigma >1}$${\textstyle C\gg C_{r}}$${\textstyle L\approx {L_{r}}}$

ネットワークのスモールワールド性を定量化する別の方法は、スモールワールドネットワークの本来の定義を利用して、与えられたネットワークのクラスタリングを同等の格子ネットワークと比較し、そのパスの長さを同等のランダムネットワークと比較するものである。スモールワールド指標（）は次のように定義される^[8]${\displaystyle \omega }$

${\displaystyle \omega ={\frac {L_{r}}{L}}-{\frac {C}{C_{\ell }}}}$

特性パス長Lとクラスタリング係数Cはテストするネットワークから計算され、C _{ℓ は}同等の格子ネットワークのクラスタリング係数であり、L _{r は}同等のランダム ネットワークの特性パス長です。

スモールワールド性を定量化するもう一つの方法は、ネットワークのクラスタリングとパス長を、同等の格子ネットワークとランダムネットワークの特性と比較して正規化することである。スモールワールド指数（SWI）は次のように定義される^[9]

${\displaystyle {\text{SWI}}={\frac {L-L_{\ell }}{L_{r}-L_{\ell }}}\times {\frac {C-C_{r}}{C_{\ell }-C_{r}}}}$

ω ′ と SWI はどちらも0 から 1 の範囲をとり、スモールワールド性の側面を捉えていることが示されている。しかし、理想的なスモールワールド性の概念は若干異なる。与えられた制約セット (サイズ、密度、次数分布など) に対して、ω ′ = 1 となるネットワークが存在するため、ω は与えられた制約を持つネットワークが可能な限りスモールワールド的である程度を捉えることを目指す。対照的に、 SWI = 1 となるネットワークは存在しない可能性があるので、 SWI は与えられた制約を持つネットワークがC ≈ C _ℓおよびL ≈ L _rとなるネットワークの理論的なスモールワールド理想に近づく程度を捉えることを目指す。^[9]

スモールワールド特性は、ナビゲーションメニュー付きのウェブサイト、食物網、電力網、代謝産物処理ネットワーク、脳ニューロンのネットワーク、有権者ネットワーク、電話通話グラフ、空港ネットワークなど、多くの現実世界の現象に見られます。^[10] 文化ネットワーク^[11]や単語共起ネットワーク^[12]もスモールワールドネットワークであることが示されています。

接続されたタンパク質のネットワークは、次数分布に従うべき乗則などのスモールワールド特性を持っています。^[13]同様に、ノードが遺伝子であり、1つの遺伝子が他の遺伝子に対してアップレギュレーションまたはダウンレギュレーションの遺伝的影響を及ぼす場合にリンクされる転写ネットワークは、スモールワールドネットワーク特性を持っています。 ^[14]

別の例として、人々の間の「 6次の隔たり」という有名な理論は、談話の領域は、ある時点で生きている人々の集合であると暗黙のうちに想定しています。アルバート・アインシュタインとアレクサンダー大王の間の隔たりの数は、ほぼ確実に30を超えており^[15]、このネットワークはスモールワールド特性を持っていません。同様に制約されたネットワークは、「一緒に学校に通った」ネットワークです。2人が10年の差で同じ大学に通っていた場合、学生団体の中に共通の知り合いがいる可能性は低いです。

同様に、メッセージが通過しなければならない中継局の数も、必ずしも少ないわけではありませんでした。郵便が手や馬で運ばれていた時代には、発信元と宛先の間で手紙が渡される回数は、今日よりもはるかに多かったでしょう。視覚電信の時代 (1800～1850 年頃) にメッセージが渡される回数は、2 つの局が見通し線で接続されているという要件によって決まりました。

暗黙の仮定は、検討されなければ、グラフに関する文献においてスモールワールドネットワークの発見に有利な偏りを生じさせる可能性があります（出版バイアスから生じるファイルドロワー効果の例）。

Albert-László Barabásiなどの一部の研究者は、生物系におけるスモールワールドネットワークの普及は、そのような構造の進化上の利点を反映している可能性があると仮説を立てています。 1 つの可能性は、スモールワールドネットワークが他のネットワーク構造よりも摂動に対して堅牢であるということです。 これが事実であれば、突然変異やウイルス感染による損傷を受けやすい生物系に利点がもたらされることになります。

べき乗法則に従う次数分布を持つスモールワールドネットワークでは、ランダムにノードを削除しても、平均最短経路長が劇的に増加すること（またはクラスタリング係数が劇的に減少すること）はめったにありません。これは、ノード間の最短経路のほとんどがハブを通過するため、周辺ノードが削除されても、他の周辺ノード間の通過を妨げる可能性は低いという事実に起因します。スモールワールドネットワークでは、周辺ノードの割合がハブの割合よりもはるかに高いため、重要なノードが削除される確率は非常に低くなります。たとえば、アイダホ州サンバレーの小さな空港が閉鎖されたとしても、米国を旅行する他の乗客がそれぞれの目的地に到着するために利用しなければならない平均フライト数は増加しません。ただし、ランダムなノードの削除が偶然ハブに当たると、平均経路長が劇的に増加する可能性があります。これは、シカゴのオヘア空港などの北部のハブ空港が雪のために閉鎖され、多くの人が追加のフライトに乗らなければならないときに毎年見られます。

対照的に、すべてのノードがほぼ同じ数の接続を持つランダム ネットワークでは、ランダム ノードを削除すると、削除されたほぼすべてのノードの平均最短パス長がわずかながら大幅に増加する可能性があります。この意味で、ランダム ネットワークはランダムな摂動に対して脆弱ですが、スモール ワールド ネットワークは堅牢です。ただし、スモール ワールド ネットワークはハブを標的とした攻撃に対して脆弱ですが、ランダム ネットワークは壊滅的な障害の標的にはなりません。

スモールワールドネットワークを構築する主なメカニズムは、ワッツ・ストロガッツメカニズムです。

スモールワールドネットワークは時間遅延を導入することもでき、^[16]適切な条件下ではフラクタルだけでなくカオス^{[17]も生成し、またはダイナミクスネットワークではカオスに遷移します。 [18]}

ワッツ・ストロガッツ機構の発表後すぐに、マシャギと同僚らは、望ましい次数分布とスモールワールド特性を維持しながら、高次相関を示すネットワークモデルを生成するアプローチを開発した。これらのアプローチはエッジデュアル変換に基づいており、これらのシステムの研究のために解析的に解けるスモールワールドネットワークモデルを生成するために使用できる。^[19]

次数直径グラフは、ネットワーク内の各頂点の近傍数が制限され、ネットワーク内の任意の頂点から他の任意の頂点までの距離（ネットワークの直径）が最小化されるように構築されます。このようなスモールワールドネットワークの構築は、ムーア境界に近い順序のグラフを見つける取り組みの一環として行われます。

スモールワールドネットワークをゼロから構築する別の方法は、Barmpoutisら^[20]で紹介されており、平均距離が非常に小さく、平均クラスタリングが非常に大きいネットワークが構築されています。一定の複雑度の高速アルゴリズムと、結果として得られるグラフの堅牢性の測定値が示されています。各ネットワークの用途に応じて、このような「超スモールワールド」ネットワークから始めて、いくつかのエッジを再配線するか、このような小さなネットワークをいくつかサブグラフとして使用して、より大きなグラフを作成することができます。

スモールワールド特性は、二重段階の進化のプロセスを通じて、ソーシャル ネットワークやその他の現実世界のシステムで自然に発生することがあります。これは、時間的または空間的な制約により頂点間の接続の追加が制限される場合に特によく見られます。このメカニズムでは、通常、段階間の定期的なシフトが行われ、接続は「グローバル」段階中に追加され、「ローカル」段階中に強化または削除されます。

スモールワールドネットワークは、新しいリンクの追加を制限する制約により、スケールフリークラスから、接続分布がべき乗則に従って急激にカットオフするブロードスケールクラスに変化する可能性がある。^[21]十分に強い制約の場合、スケールフリーネットワークは、接続分布が急速に減衰する特徴を持つ単一スケールネットワークになることもできる。^[21]また、スケールフリーネットワークは超小型であり、距離がに従ってスケールされることが解析的に示された。^[22]${\displaystyle L\propto \log \log N}$

社会運動グループにとってのスモールワールドネットワーキングの利点は、高度に接続されたノードを使用するフィルタリング装置による変化への抵抗と、ネットワークを接続するために必要なリンクの数を最小限に抑えながら情報を中継する効率性の向上です。^[23]

スモールワールドネットワークモデルは、ウィリアム・フィネガンによる社会学的議論で代表されるアフィニティグループ理論に直接適用できる。アフィニティグループとは、小規模で半独立した社会運動グループであり、より大きな目標や機能に献身している。ノードレベルではほとんど無関係であるが、接続性の高い少数のメンバーが接続ノードとして機能し、ネットワークを通じてさまざまなグループを結びつける。このスモールワールドモデルは、警察の行動に対する抗議組織戦術として極めて効果的であることが証明されている。^[24]クレイ・シャーキーは、スモールワールドネットワーキングによって作られた社会的ネットワークが大きくなればなるほど、ネットワーク内の接続性の高いノードの価値が高くなると主張している。^[23]同じことがアフィニティグループモデルにも言え、各グループ内の少数の人々が外部のグループとつながっていることで、大量の動員と適応が可能になった。この実際的な例は、ウィリアム・フィネガンが1999年のシアトルWTO抗議運動に関連して概説したアフィニティグループを通じたスモールワールドネットワーキングである。

地質学や地球物理学で研究されている多くのネットワークは、スモールワールドネットワークの特徴を持っていることが示されています。断層系や多孔質物質で定義されたネットワークは、これらの特徴を示しています。^[25] 南カリフォルニア地域の地震ネットワークは、スモールワールドネットワークである可能性があります。^[26]上記の例は非常に異なる空間スケールで発生しており、地球科学における現象の スケール不変性を 示しています。

スモールワールドネットワークは、大規模データベースに格納された情報の有用性を推定するために使用されてきました。この尺度は、スモールワールドデータ変換尺度と呼ばれています。^{[27] [28]}データベースリンクがスモールワールドネットワークに一致するほど、ユーザーが将来情報を抽出できる可能性が高くなります。この有用性は通常、同じリポジトリに格納できる情報量を犠牲にして得られます。

Freenetピアツーピアネットワークはシミュレーションでスモールワールドネットワークを形成することが示されており^{[29] 、ネットワークの拡大}に応じて効率を拡張しながら情報を保存および取得することができます。

HNSWのような近傍探索ソリューションは、スモールワールドネットワークを使用して、大規模なアイテムコーパス内の情報を効率的に見つけます。^{[30] [31]}

脳内の解剖学的接続^[32] と皮質ニューロンの同期ネットワーク^[33]はどちらもスモールワールドトポロジーを示しています。

脳内の構造的・機能的接続性も、短い経路長と高いクラスタリングというスモールワールドトポロジーを反映していることがわかっています。^[34]このネットワーク構造は、種を超えた哺乳類の皮質や、人間の大規模な画像研究でも発見されています。^[35]コネクトミクスとネットワーク神経科学の進歩により、ニューラルネットワークのスモールワールド性が効率的なコミュニケーションと関連していることがわかりました。^[36]

ニューラルネットワークでは、ノード間の短い経路長とネットワークハブでの高度なクラスタリングにより、エネルギーコストを最小限に抑えながら脳領域間の効率的な通信がサポートされます。^[36]脳は常に新しい情報を処理して適応しており、スモールワールドネットワークモデルはニューラルネットワークの強力な通信要求をサポートします。^[37]ノードの高度なクラスタリングにより、機能的に関連することが多いローカルネットワークが形成されます。これらのハブ間の短い経路長は、効率的なグローバル通信をサポートします。^[38]このバランスにより、グローバルネットワークの効率が実現されると同時に、ローカルサブシステムがグローバルネットワークから分離されるため、脳は混乱に対処し、恒常性を維持できるようになります。^[39]スモールワールドネットワーク構造の喪失は、認知の変化と精神障害のリスク増加を示すことがわかっています。^[9]

脳全体の機能的・構造的接続性を特徴付けるだけでなく、視覚系などの特定の神経系はスモールワールドネットワークの特性を示す。^[6]

ニューロンのスモールワールドネットワークは短期記憶を示すことができる。サラ・ソラ^{[40] [41]が開発したコンピュータモデルには、}記憶の保存に重要だと考えられる2つの安定状態（双安定性と呼ばれる）があった。活性化パルスはニューロン間の通信活動の自己持続ループを生成した。2番目のパルスはこの活動を終了させた。パルスはシステムを安定状態、つまりフロー（「記憶」を記録する）とスタシス（それを保持する）の間で切り替えた。スモールワールドニューロンネットワークは、発作を理解するためのモデルとしても使用されている。^[42]

• Barabasi-Albert モデル – スケールフリー ネットワーク生成アルゴリズム
• 複雑ネットワークとしての気候 – 気候科学への洞察を生み出す概念モデル
• 二段階進化 – 複雑適応システム内で自己組織化を促進するプロセス
• ダンバー数 – 社会学と人類学で重要な認知限界の提案
• エルデシュ数 – 数学者ポール・エルデシュとのつながりの近さ
• Erdős-Rényi (ER) モデル – ランダム グラフを生成するための 2 つの密接に関連したモデル
• ローカルワールド進化ネットワークモデル
• パーコレーション理論 – ランダムグラフ内の連結クラスターの挙動に関する数学理論
• ネットワーク科学 - 学問分野 - ネットワークの数学的理論
• スケールフリーネットワーク – 次数分布がべき乗法則に従うネットワーク
• ケビン・ベーコンの6次の関係 - 隔たりの度合いに関する社交ゲーム
• スモールワールド実験 – ソーシャルネットワークの平均経路長を調べる実験
• ソーシャルネットワーク – 社会的行為者の集合体から構成される社会構造
• ワッツ・ストロガッツモデル – ランダムなスモールワールドグラフを生成する方法
• チップ上のネットワーク - 集積回路上の電子通信サブシステム -スモールワールドネットワークをモデルにしたチップ上のシステム
• ザカリーの空手クラブ

• 動的近接ネットワーク (Seth J. Chandler 著、Wolfram デモンストレーション プロジェクト)。
• Scholarpedia の Small-World Networks のエントリ (Mason A. Porter 著)