Gelling, and Melting, Large Graphs by Edge Manipulation

Gelling, and Melting, Large Graphs by Edge Manipulation

  • Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, Christos Faloutsos
  • CIKM 2012

概要

  • これまでは頂点を弄って拡散を操作していた
  • 今回は辺を追加/削除して拡散を増強/減退
  • アルゴリズム,解析,実験
  • ベストペーパー

動機付け

  • NetMelt問題
    • 辺を削除して感染を最小化したい
    • マルウェアの広がりとか
    • 問題: 既存手法は頂点に関してのみ
  • NetGel問題
    • 辺を追加して拡散を拡大したい
    • 問題: 候補が多すぎO(n^2)

問題定義

  • Faloutsos達の既存結果から結局固有値が大事
  • NetMelt (辺削除)
    • k辺を消して隣接行列の固有値を最小化
  • NetGel (点削除)
    • k辺を足して隣接行列の固有値を最大化

NetMeltの提案手法

  • とりあえずNP-complete
  • 辺毎の貢献の和にはならない
  • 代わりに左・右固有ベクトルを使ったスコアを各辺に与え,上位k辺を返す
  • 行列摂動理論から
    • (固有ギャップ)$$ = \lambda - \lambda_2 \geq 2\ sqrt{k} $$なら
    • (固有値の変化) = (推定スコアの和) + O(k)
      • O(k)はぼちぼちデカそうだけど,実験的にはまぁ大丈夫
  • 適当に貪欲するだけなので,O(mk+n)時間

NetGelの提案手法

  • 候補数 = Θ(n^2)
  • 頑張ると大部分は枝刈りできる
  • 辺$$ (i,j) $$のスコア = $$ u_i v_j $$
    • $$ \mathbf{u}, \mathbf{v} $$: 左, 右固有ベクトル
  • だから,高々上位k+d要素しかとっておかなくて良い
    • 多分もっとCLEVERにできるけど,十分なので重視してない
  • $$ O(m + nt + kt^2), t = \max(k,d^-,d^+) $$

実験

  • 目的関数値そのものの変化の比較,SISモデルでの比較,効率の比較
  • 特に目立った感じはない,普通の内容

まとめ

  • 割りと普通な感じなので,ベストペーパーになった理由がよく分からん
  • 問題定式化は今までの拡散に関する結果からだし,提案手法もほぼ自明だし,実験も驚きは無し

CIKM 情報拡散

2016/05/12

タグ:

CIKM 情報拡散
最終更新:2016年05月12日 22:29