Markov Cluster Algorithm (MCL)

複雑系

Stein van Dongenの博士論文("Graph clustering by flow simulation")をぱらぱらと読んでいます。この論文のテーマは有向グラフをクラスタリングすることです。"Markov Clustering"の名称の由来は、グラフからクラスターを発見するのに、グラフ上のランダムウォークを利用したときに、グラフ上の遷移をMarkov過程としてモデルできるからです。グラフ上のランダムウォークとは、適当にノードを選択し、そこからエッジを無作為に選んで隣接するノードに向う移動を繰り返すことです。ランダムウォークを無限に繰り返したときに各ノードを訪問する遷移確率を利用してグラフからクラスターを発見するようです。

MCLの計算量はO(Nk2)です。ここでNはノード数、kはノードの平均次数。たぶん、O(Nk)の項は行列積を一回計算するのに必要な計算量で残ったO(k)は???MCLを収束させるにはグラフの直径に比例する成分が出てきそうなものだけど。。。もし、これが本当なら、かなり高速です。

グラフクラスタリングの研究で障害となるのは、クラスタリングの結果を比較することが困難なことです。van Dongen はあらかじめクラスタリングがわかっているグラフを生成し、それをクラスタリングした結果と定量的に比較する方法を試みています。*1

隣接行列のインデックスを入れ替えて、各クラスターに属するノードの番号が連続するようにすると隣接行列を可視化してクラスタリングの様子を簡単に確認できるそうです。このアイデアは面白いです。そういえば、CCFinderのクラスタリング結果の図も似た感じでした。

以上がイントロ

  1. Introduction (はじめに)
  2. Cluster analysis (データ解析とパターン認識の分野での位置づけ)
  3. Graph clustering (クラスター解析の分野での位置づけ)
  4. Notation and definitions (基本的な定義)
  5. The graph clustering paradigm (クラスタリングアルゴリズムの紹介：主に組合せ論的アプローチと確率的なアルゴリズム)
  6. Basic MCL theory (アルゴリズム)
  7. Structure theory for the MCL process (アルゴリズムに対する理論的な解析)
  8. The relationship between λ2(G) and cluster structure (スペクトル構造とクラスター構造の関係についての議論)
  9. Comparing different graph clusterings (重みつきグラフへの対応。分割仕方の指標も与えている)
  10. Clustering characteristics of the MCL algorithm (クラスタリング結果に関する理論的な解析)
  11. Scaling the MCL algorithm (高速化手法)
  12. Randomly generated test graphs (クラスタリングの評価手法の提案)

ちょっと感想

グラフ上のランダムウォークと聞けば、Googleの心臓部である PageRank*2を思い出す人も多いでしょう。"Inside PageRank"*3 という魅力的なタイトルに騙されて読んだ人も多いかもしれませんが、この論文でPageRankがランダムウォークであることが述べられています。ただし、このままでは、ウェブサーファがウェブの袋小路に至ったときには、移動が止まってしまい、ある意味で世の中で一番つまらないページにサーファが滞留してしまうことを避けるため、無作為に選んだウェブページに移動するとしています。これは sink ノードに無作為に選んだノードへのリンクを張ることで実現できます。

van Dongenの博士論文には、PageRank やそれと類似の Kleinberg の HITS アルゴリズムは引用されていません。また、PageRank の論文は、さらにそれ以前の計量社会学で知られている Bonacich の中心性*4に言及していません。MCLとPageRankはほぼ同時期の研究だから仕方ないかもしれないけれども、あちこちで独立再発見をしまくっているという感じです。分野間の壁とはいわれるけれど、MCLとPageRankはどちらも計算機科学だからなぁ。。。

どこぞの社会学の学生がGoogleでボナチッチがほとんどヒットしないとボヤいていたのが笑えます。Google の陰謀かとも思えるのですが、たぶん検索をしたときにスペルミスしたんでしょう。

*1:この方法で、ぼくらのクラスタリングとNewmanのアルゴリズムを比較してみるか。

*2:Page, Lawrence; Brin, Sergey; Motwani, Rajeev; Winograd, Terry. The PageRank Citation Ranking: Bringing Order to the Web, Nov. 1999.

*3:Bianchini, M., Gori, M., and Scarselli, F. 2005. Inside PageRank. ACM Trans. Inter. Tech. 5, 1 (Feb. 2005), 92-128.

*4:Bonacich, P.(1972), "Factoring and Weighting Approaches to Clique Identification," Journal of Mathematical Sociology, Vol.2, pp.113-120.