Robust Classification of Salient Links in Complex Networks (Nature Communications 2012)

問題

重み付きネットワーク（というより重み付き完全グラフ＝行列）から重要なリンクを抽出したい．

• 重み付きネットワーク：輸送関係，生物，社会
  • おもみ：金の流れ，飛行機発着，通勤，共著論文本数，……
• (復習) 重みの分布：$P(w) \sim w^{-1-\alpha}, 1 < \alpha \leq 2$．

素朴な方法

• 最小全域木 → ツリーしかできない
• しきい値 → パラメータ設定

Link Salience (提案手法)

アイディア：リンクを，SPTに含まれる頻度に応じて分類 → ほぼ 0 のものとほぼ 1 のものになぜか二分される

アルゴリズム

• 距離 effective distance $d_{ij} = 1/w_{ij}$．
• 辺の salience
  • 各頂点から SPT を計算，SPT に入ったら +1 する．
  • これを全頂点からやって N で割る.

やってみると，なんと，0 近くのものばっかりと 1 近くのものばっかりになる（→ しきい値の設定が簡単）

結果

• 結果のグラフは high-salience skeleton (HSS) と呼ぶ．
  • HSS 中の次数分布はべき則
  • 元のグラフが asortative でも disassortative になる
• betweeness と salience の違い
  • 小さなネットワークでの例：結構違う
  • 実ネットワーク：相関なし．数式的にゆるめの bound はできる．
  • 例えば，leaf にくっついている辺は，salience は 1 だが，betweeness は 1/n．
• weight との関係
  • betweeness はベキ則がある，salience はない．

なぜ bimodal に？

あまりちゃんとした理由付けはなし