Heat Kernel Based Community Detection - todo314 @ ウィキ

Heat Kernel Based Community Detection

• Kyle Kloster, David F. Gleich
• KDD 2014

概要

• 頂点を含むコミュニティを定数時間で出力
• 熱方程式をシミュレート
• PageRankを使ったPushアルゴリズムを熱核にしたよ
• 熱核
  • 熱方程式に対する基本解

拡散過程によるコミュニティ抽出

• 良いコミュニティ≒コンダクタンスが小さい
• 種の頂点から遷移行列に従い拡散
• 定常分布になる前に止めないと駄目
• ⇨スコアベクトルf: 各ステップkでの重みに適当な重み付けc_kをする
• ↑が大きい頂点を順にコミュニティに追加
• 追加していく途中で一番良い物を出力
• 熱核とPageRankの関係
  • 熱核はすぐ収束するので種のすぐ周りだけで良くて，PageRankより早くて良さそう

熱核の定数時間計算アルゴリズム

• 非ゼロの要素が定数個のベクトルで近似できる
• Push: 重みを確定させて，次のステップに拡散する，みたいな
• 上手く閾値を選び，閾値以上の要素だけにPush

実験

• ground truthと比較
• 色々と問題がありそうだが…

KDD コミュニティ検出 熱核

2014/11/20