「Heat Kernel Based Community Detection」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* Heat Kernel Based Community Detection
- Kyle Kloster, David F. Gleich
- KDD 2014
* 概要
- 頂点を含むコミュニティを定数時間で出力
- 熱方程式をシミュレート
- PageRankを使ったPushアルゴリズムを熱核にしたよ
- 熱核
-- 熱方程式に対する基本解
* 拡散過程によるコミュニティ抽出
- 良いコミュニティ≒コンダクタンスが小さい
- 種の頂点から遷移行列に従い拡散
- 定常分布になる前に止めないと駄目
- ⇨スコアベクトルf: 各ステップkでの重みに適当な重み付けc_kをする
- ↑が大きい頂点を順にコミュニティに追加
- 追加していく途中で一番良い物を出力
- 熱核とPageRankの関係
-- 熱核はすぐ収束するので種のすぐ周りだけで良くて，PageRankより早くて良さそう
* 熱核の定数時間計算アルゴリズム
- 非ゼロの要素が定数個のベクトルで近似できる
- Push: 重みを確定させて，次のステップに拡散する，みたいな
- 上手く閾値を選び，閾値以上の要素だけにPush
* 実験
- ground truthと比較
-
* Heat Kernel Based Community Detection
- Kyle Kloster, David F. Gleich
- KDD 2014
* 概要
- 頂点を含むコミュニティを定数時間で出力
- 熱方程式をシミュレート
- PageRankを使ったPushアルゴリズムを熱核にしたよ
- 熱核
-- 熱方程式に対する基本解
* 拡散過程によるコミュニティ抽出
- 良いコミュニティ≒コンダクタンスが小さい
- 種の頂点から遷移行列に従い拡散
- 定常分布になる前に止めないと駄目
- ⇨スコアベクトルf: 各ステップkでの重みに適当な重み付けc_kをする
- ↑が大きい頂点を順にコミュニティに追加
- 追加していく途中で一番良い物を出力
- 熱核とPageRankの関係
-- 熱核はすぐ収束するので種のすぐ周りだけで良くて，PageRankより早くて良さそう
* 熱核の定数時間計算アルゴリズム
- 非ゼロの要素が定数個のベクトルで近似できる
- Push: 重みを確定させて，次のステップに拡散する，みたいな
- 上手く閾値を選び，閾値以上の要素だけにPush
* 実験
- ground truthと比較
- 色々と問題がありそうだが…
&tags()
2014/11/20
