Upgrade to Pro — share decks privately, control downloads, hide ads and more …

3.8節 スモールワールド / Small Worlds

Yuki Iwanaga
February 27, 2023

3.8節 スモールワールド / Small Worlds

■3.8節
スモールワールド現象を,ランダム・ネットワークモデルの範囲内で説明できるかについて議論.

■教科書
Barabási, A.-L. (2019)『ネットワーク科学』池田裕一・井上寛康・谷澤俊弘監訳、京都大学ネットワーク社会研究会訳、共立出版
【英語版】http://networksciencebook.com/

Yuki Iwanaga

February 27, 2023
Tweet

More Decks by Yuki Iwanaga

Other Decks in Science

Transcript

  1. 平均次数 𝑘 のランダム・ネットワークで考える 𝑘 = 2 距離 1ステップ 2ステップ 3ステップ

    𝑑ステップ ノード数 𝑘 1 = 21= 2 𝑘 2 = 22= 4 𝑘 3 = 23= 8 𝑘 𝑑 = 2𝑑 𝑁(𝑑):起点となるノードから距離𝑑の位置までに含まれるノードの総数 𝑁 𝑑 ≈ 1 + 𝑘 + 𝑘 2 + ⋯ + 𝑘 𝑑 = 𝑘 𝑑+1 − 1 𝑘 − 1 (3.15)
  2. スモールワールド性の定式化 𝑁(𝑑) ≤ 𝑁より, 距離𝑑が無限に大きくなることはない. ネットワークの直径(最大距離)を𝑑𝑚𝑎𝑥 とすると 𝑁 𝑑𝑚𝑎𝑥 ≈

    𝑁 と近似できる. 式(3.15)において 𝑘 ≫ 1と仮定すれば, 𝑁 𝑑𝑚𝑎𝑥 = 𝑘 𝑑𝑚𝑎𝑥+1 − 1 𝑘 − 1 ≈ 𝑘 𝑑𝑚𝑎𝑥+1 𝑘 = 𝑘 𝑑𝑚𝑎𝑥 ∴ 𝑘 𝑑𝑚𝑎𝑥 ≈ 𝑁 両辺の対数をとって整理すると 𝑑𝑚𝑎𝑥 ≈ ln 𝑁 ln 𝑘 (3.18) (3.16) (3.17)
  3. スモールワールド性の定式化 𝑑𝑚𝑎𝑥 ≈ ln 𝑁 ln 𝑘 この式は無作為に選ばれた二つのノード間の平均距離についての良い近似となっている. • 最大距離𝑑𝑚𝑎𝑥

    は数少ない極端な経路の影響を強く受ける • 平均距離 𝑑 では, ノードのすべての組み合わせに関する平均をとるため, そのようなゆらぎの影響が抑えられる (3.18) スモールワールド性: 𝑑 がノード数𝑁と平均次数 𝑘 にどう依存するかを表す関係式で定義される 𝑑 ≈ ln 𝑁 ln 𝑘 (3.19)
  4. 式(3.19)の解釈 𝑑 ≈ ln 𝑁 ln 𝑘 (3.19) • 平均距離

    𝑑 は, 𝑁や𝑁のべきに比例するのではなく, ln 𝑁に比例 する • 分母のln 𝑘 はネットワークが密になるほど, ノード間距離が小 さくなることを表す • 一般にln 𝑁 ≪ 𝑁であるため, ランダム・ネットワークにおいては ノード間距離がネットワークの大きさに比べて何桁も小さい • スモールワールド性の「スモール(小さい)」という言葉は, ネットワーク内のノード間平均距離,あるいは直径がシステムの 大きさの対数に依存することを意味している(疑問1) • 同じサイズの規格格子の場合と比べて, ノード間距離が平均し て「短い」(疑問2) Barabási, A.-L. Network science (Cambridge University Press, 2016). http://barabasi.com/networksciencebook/.
  5. さまざまなスモールワールド性 19次の隔たり(1999年) • WWW内の二つの文書は平均して19回のクリックでたどり着ける • 有限サイズスケーリング(WWWのサンプルサイズを大きくするにつれて平均距離がどのよ うに増加するか測定)の結果から導いた下記の評価式から算出 𝑑 ≈ 0.35

    + 0.89 ln 𝑁 6次の隔たり(1967年):ミルグラムの郵便実験 友人に手紙を転送してもらうことを繰り返すことで、 遠く離れた人に手紙が届くかを実験したもの • 住所と名前が記されている手紙がある • その人を知っていれば直接送る • 知らなければ、ファーストネームで気軽に呼び合える仲の友人に手紙を転送する 実験の結果、平均して6人を介して目的の人に手紙が届いた。 Barabási, A.-L. Network science (Cambridge University Press, 2016). http://barabasi.com/networksciencebook/.
  6. 3.8節のまとめ スモールワールド性: 𝑑 がノード数𝑁と平均次数 𝑘 にどう依存するかを表す関係式で定義される 𝑑 ≈ ln 𝑁

    ln 𝑘 (3.19) ネットワーク科学における重要性 • スモールワールド現象は、ランダム・ネットワークモデルの範囲内で かなりの程度まで理解できる スモールワールド現象はランダム・ネットワークモデルによって合理的に説明することができる 唯一の性質である。(p105)