Fast Influence-based Coarsening for Large Networks - todo314 @ ウィキ

Fast Influence-based Coarsening for Large Networks

• Manish Purohit, B. Aditya Prakash, Chanhyun Kang, Yao Zhang, V.S. Subrahmanian
• KDD 2014

概要

• 情報拡散の特徴を保ったままグラフを小さくしたい，近似したい
• 頂点対を「縮約」
  • アイデア：ほとんどの辺は無意味
• 問題を定式化
• スコア付けがGOODで，ほぼ線形時間
• 90%削減も（頂点数を）

問題定義

• 入力: G=(V,E,w)，α
• 出力: H=(V',E',w')
  • |V'|=(1-α)|V|
  • HはGを伝播の特徴の意味で近似する

今回使う特徴

• 隣接行列の固有値
  • 感染症モデルの関係
• より具体的に問題：
  • グラフは強連結
  • 固有値が出来るだけ変化しないように併合する辺E'を選ぶ

縮約

• x-e-d-b-a
  • 確率は全部0.5
• (a,b)を縮約する
• x-e-d-c
  • 「cの活性化=a/bの活性化」と考える
• aを活性化 w.p. 0.5 … d-b-aの時dも活性化 w.p. 0.25
• bを活性化 w.p. 0.5 … d-bの時dも活性化 w.p. 0.5
• 平均取って0.375
• 各頂点対併合について，↑みたいな事を考えて，辺確率を更新
• 全パターン網羅して書いてる

提案手法

• 各辺をその辺の併合による固有値の変化とする
  • これの計算が大変
  • Noveltyはここを全辺一括しての効率的な計算
• 変化の小さい辺を頂点数が目標に達するまで順に縮約
• 計算時間 $$ \mathcal{O} (m \ln m + \alpha n \Delta) $$

影響最大化

• とりあえず普通に解く
• コンポーネントが選ばれていたら，無作為に選ぶ
  • コンポーネント中を無作為に活性化する意味の縮約なので，その意味では妥当

実験

• |V|≦2M, |E|≦31M

効果

• α vs. 固有値
  • 無作為に縮約するのに比べて固有値が保存されている→やった！
  • GCPは上手く解ける

効率

• αにもnにも線形

応用: 影響最大化

• 90%頂点を削除
• 辺確率: {0.02} or {0.1, 0.01, 0.001}
• 解の質
  • 90%以上削除しても提案手法/PMIAの比はほぼ1
  • シードのコンポーネントからの選び方も割りとどれでもいい
• 効率
  • 最大で300倍高速化
• 応用: 拡散の特徴（略）

まとめ（つっこみ）

• 元は，SIRとかSISだから，辺毎の確率のようなパラメタとか，ミクロな視点での伝播は考えてなさそう
• 強連結な仮定があっさりと流されていないか？
• 固有値が絶対的(?)な基準
  • あくまで伝播の特徴を近似するものでは？
• 近似保証無いのか
  • SDMのベストペーパーのアレっぽい（こっちは応用で評価されたんだろうが）
• 頂点数は減らしているが辺数は？
• 実験でPMIA/提案手法がダメ
  • PMIAが仮にランダムなシードを返す
• KDDの割に全体的に雑な印象を持った

KDD 影響最大化 情報拡散 疎化

2015/09/09 0:46