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

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 に?

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