エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Markov Cluster Algorithm (MCL) - kwakita’s diary
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Markov Cluster Algorithm (MCL) - kwakita’s diary
Stein van Dongenの博士論文("Graph clustering by flow simulation")をぱらぱらと読んでいます。この論... Stein van Dongenの博士論文("Graph clustering by flow simulation")をぱらぱらと読んでいます。この論文のテーマは有向グラフをクラスタリングすることです。"Markov Clustering"の名称の由来は、グラフからクラスターを発見するのに、グラフ上のランダムウォークを利用したときに、グラフ上の遷移をMarkov過程としてモデルできるからです。グラフ上のランダムウォークとは、適当にノードを選択し、そこからエッジを無作為に選んで隣接するノードに向う移動を繰り返すことです。ランダムウォークを無限に繰り返したときに各ノードを訪問する遷移確率を利用してグラフからクラスターを発見するようです。 MCLの計算量はO(Nk2)です。ここでNはノード数、kはノードの平均次数。たぶん、O(Nk)の項は行列積を一回計算するのに必要な計算量で残ったO(k)は?