Spectral Counting of Triangles in Power-Law Networks via Element-Wise ... - todo314 @ ウィキ

Spectral Counting of Triangles in Power-Law Networks via Element-Wise Sparsification

概要

• 三角形の個数を早く求めたい
• 辺を確率1-pで削除
  • 残った辺に重み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を割り振る
  • いい感じらしい
• 提案手法の正当化

1. べき則
   • 少しの固有値しか寄与しない
   • 三乗だからさらに強い傾向が
   • Lanczosの収束が速い

実験

• 精度がめっちゃ振動しているけど，あまり沢山の固有値を見なくていいのは確か
  • せいぜい数十個
• ナイーブなのに比べて数百倍速くなったよ
• pの値による違いが謎

まとめ

• 2つを組み合わせてみましたーってだけっぽい
• 固有値がデカイ順に出てくるならば，その時点での精度が保証できるなあ
  • 弱そう

ASONAM スペクトラルグラフ理論 三角形 疎化

2014-03-26 23:04:44 (Wed)