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

Transport in Weighted Networks: Partition into Superhighways and Roads (PRL 2006)

重み付きネットワークから重要な辺だけを抜き出す問題.

  • weighted network,重み一様分布,小さいものほど重要
  • κ<2 になるまで,重みの大きい辺を削除 → largest component が IIC
    • inifinite incipent percolation cluster (IIC) = superhighway
    • κ=2 とはパーコレーション転移点
  • MST を作って, IIC に含まれない部分を road.

パーコレーション転移とは

  • 最大連結成分の大きさが $O(1)$ から $O(N^\alpha)$ になる間の瞬間
  • 大域的つながるはあるが,ノードの数が全体に比べて小さい

性質

  • 長い最短路は IIC いっぱい通る.
  • MST も.
  • 最大流の流量を増やしたければ,MST の辺を増やすというのよりも,IIC のを増やすというほうが向上する.(ただし実験設定が怪しい…)


現実のネットワークでの実験などは無し.