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

成長しないスケールフリー・ネットワーク

コンフィグモデル

  • モデル
    • 任意の次数分布を決める.
    • 頂点の次数を最初に生成(スポーク)し,等確率で接続する.
  • 生成原理を説明する気は無い
  • 平均場近似,次数列を保ったまま繋ぎ変えることにより実データの性質を検証
  • 性質
    • 直径 $L$
      • $2 < \gamma < 3$ → $L \propto \log \log N$
      • $\gamma = 3$ → $L \propto \frac{\log N}{\log \log N}$
      • $\gamma > 3$ → $L \propto \log N$
      • $\gamma \le 3$ の時,ウルトラ・スモールワールド
    • クラスタ係数 $C$:小さい
  • 特に,全次数を $k_0$ 一定にするグラフを,レギューラー・ランダム・グラフ
    • 次数が全く散らばっていないので,次数のばらつき 0 の実験ができる

一般の次数分布をもつ木

  • モデル
    • 任意の次数分布を決める
    • 「親 → 子を適当な個数生成,それらが親に」を繰り返す
  • ゴルトン・ワトソン過程
  • 平均次数
    • 2 のとき,臨界木と呼ばれ,フラクタル性という特別な性質を持つ
    • <2 のとき,超小さくて面白くない

Goh モデル

  • モデル
    • 各頂点 $i$ の重み $w_i = i^{-\alpha}$
    • 重みに比例した確率で頂点を 2 つ選び辺を張ることを繰り返す
  • 次数分布 $\gamma = 1+\frac1{\alpha}$
    • $\alpha$ が大きいほど重みがきつく効き高い次数が出現する

Chung-Lu モデル

  • モデル
    • 重みの積 $w_{i}w_{j}$ に比例した確率で辺を張る
  • 次数分布:Goh モデルと同様に重み付ければ同様
  • 直径:コンフィグモデルと同様
  • 隣接行列の固有値べき則

Christian さんの論文で使われていたやつだなあ