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 (辺削除)
-
NetGel (点削除)
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
最終更新:2016年05月12日 22:29