Spectral Counting of Triangles in Power-Law Networks via Element-Wise Sparsification
概要
-
三角形の個数を早く求めたい
-
辺を確率1-pで削除
-
固有値で近似
-
何か速いよ!('(゚∀゚∩
提案手法
-
まず,隣接行列を低ランクに近似
-
高固有値だけ計算する
-
Lanczos methodというのを使い固有値を大きい順に求めていく
-
現在の固有値の三乗和に対する寄与がtot以下になったら打ち切り
Eigen Triangle
-
$$ \Delta(G) = \frac{1}{6}\sum_{i=1}^{n}\lambda_i^3 $$
-
でかい固有値だけ見れば大体良い
Achlioptas-McSherry Low Rank Approximation Algorithm
-
各辺を確率pで残して,重み1/pを割り振る
-
提案手法の正当化
-
べき則
-
少しの固有値しか寄与しない
-
三乗だからさらに強い傾向が
-
Lanczosの収束が速い
実験
-
精度がめっちゃ振動しているけど,あまり沢山の固有値を見なくていいのは確か
-
ナイーブなのに比べて数百倍速くなったよ
-
pの値による違いが謎
まとめ
-
2つを組み合わせてみましたーってだけっぽい
-
固有値がデカイ順に出てくるならば,その時点での精度が保証できるなあ
ASONAM スペクトラルグラフ理論 三角形 疎化
2014-03-26 23:04:44 (Wed)
最終更新:2014年03月26日 23:04