読者です 読者をやめる 読者になる 読者になる

成長するスケールフリー・ネットワークのモデル

http://iwi.tc/wiki/index.php?%E6%9B%B8%E7%B1%8D%2F%E8%A4%87%E9%9B%91%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF%E2%80%95%E5%9F%BA%E7%A4%8E%E3%81%8B%E3%82%89%E5%BF%9C%E7%94%A8%E3%81%BE%E3%81%A7%2F06.%20%E6%88%90%E9%95%B7%E3%81%99%E3%82%8B%E3%82%B9%E3%82%B1%E3%83%BC%E3%83%AB%E3%83%95%E3%83%AA%E3%83%BC%E3%83%BB%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF

  • インターネット・航空網などは実際に成長している
  • スケールフリー:80 対 20 の法則,ロングテールの法則
BA モデル
  • 優先的選択 (preferential attachment)
  • $ p(k) \propto k^{-3} $
    • 連続近似(→微分方程式)の方法と,マスター方程式による方法
  • $ C = \frac{m-1}{8}\frac{\log^2 N}{N} $
Dorogovsev-Mendes-Samukhin モデル (BA モデルの拡張)
  • 優先的選択にゲタを履かせる (重み $k_i$ → $k_i + k_0$)
  • $ p(k) \propto k^{-3-\frac{k_0}m} $
    • $k_0$ が大きいほど,優先的選択の効果が小さい
  • $k_0=-m$ とすると,$\gamma=2$,これは枝に向きを導入すると自然 (WWW 等)
  • $\langle k \rangle$ を動かさずとも $\gamma$ が動かせるということ
頂点コピーモデル
  • モチベーション
    • 優先的選択は,全体の次数を知らなければならず現実的でない
    • WWW 等では,ページをコピーし一部を書き換えて作られているはずだ
  • コピーする頂点を選び,そこが指す枝を確率 α で一様に書き換え残りを残す
  • $ \gamma = \frac{2-\alpha}{1-\alpha} $
    • $\alpha$ が大きいと,頂点をあまりコピーせず,次数の散らばりが小さい
Holme-Kim モデル
  • クラスター係数が小さい点を克服する
  • 各頂点からの $m$ 本の辺,確率 $p$ で優先的選択,確率 $1-p$ で直前の近傍を選択
適応度モデル
  • 先に入った頂点が必ず次数が大きくなる,というのを解消し,後からの下克上を起こす
  • 各頂点に適応度を決め,次数にそれを掛けて重み付けて優先的選択
頂点非活性モデル
  • これも大きい $C$ を実現する.
  • $m$ 個の頂点が活性.新しく頂点を追加したあと,それらに辺を張り,頂点を 1 つ非活性にする.
    • 非活性にする確率には重みをつけ,次数が高いほど非活性されにくいようにする.
  • $L$ が大きくなるというデメリットがある
    • ただし,$L$ を小さくするのは簡単:ランダムに辺を少し付け替えても良いし,確率 $p$ でBA モデルの成長ステップをしても良い
階層的モデル
  • スケールフリー・ネットワークの一部を切りだすと,やはりスケールフリー・ネットワーク
  • 紹介されているものは 3 つとも決定的
    • バラバシの階層的モデル
    • ドロゴフツェフの階層的モデル
    • ラヴァスの階層的モデル