Navigability of complex networks (Nature Physics 2008)

  • hidden distance を取りれたモデル
  • 手法概要
    • 頂点間の hidden distance
    • hidden distance に基づいたスケールフリーなネットワーク(power law, cluster coefficient)
    • hidden distance に関する greedy search
  • ネットワーク生成
    • hidden distance が小さいと結ばれやすい → large cluster coefficient
    • 円周上に点をランダムに配置 → 円周上の距離が hidden distance
    • 次数の期待値に対応する隠れ変数も生成
    • (1 + 距離/κκ')^-α に比例した確率で辺生成
      • アルファが大きいと,クラスター性が強まる
  • 実験
    • クラスタ係数が大きくて,次数の分布が大きいと,良い
    • 実ネットワークでの移動:次数の低い頂点→次数の高い頂点→次数の低い頂点
    • そういうネットワーク作ると似たような移動をする