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 のを増やすというほうが向上する.(ただし実験設定が怪しい…)
現実のネットワークでの実験などは無し.