マルコフクラスタリングアルゴリズム

Question

私はマルコフクラスタリングアルゴリズムの詳細を以下の例を通じて取り組んできました：

http://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf

私は、アルゴリズムを正確に表現しているが、私は同じ結果を得ていないのですように感じますこのガイドは、少なくとも、その入力のためになっていた。

：私は多分私はちょうど小さな事実を見逃しているか、これだけのためにどこかに小さな微調整を必要とするが、私はを含むいくつかのバリエーションを試してみましたかどうかわからないのです http://jsfiddle.net/methodin/CtGJ9/

：

現在のコードはです

1. が原稿ガイドがそれを必要としなかったので、公式MCLさdが、（正規の取り外し精度に基づいて、等価性チェック
3. を膨張/拡張スワップ

これらのすべてが同じ結果を返しました。ノードはそれ自体にのみ影響します。私もVBで同様のアルゴリズムの実装を見つけた

： http://mcl.codeplex.com/SourceControl/changeset/changes/17748#MCL%2fMCL%2fMatrix.vb

そして、私のコードは、その番号（600 - 例えば距離）を除いて一致しているようです。

これは、拡張機能

// Take the (power)th power of the matrix effectively multiplying it with 
// itself pow times 
this.matrixExpand = function(matrix, pow) { 
    var resultMatrix = []; 
    for(var row=0;row<matrix.length;row++) { 
     resultMatrix[row] = []; 
     for(var col=0;col<matrix.length;col++) { 
      var result = 0; 
      for(var c=0;c<matrix.length;c++) 
       result += matrix[row][c] * matrix[c][col]; 
      resultMatrix[row][col] = result; 
     } 
    } 
    return resultMatrix; 
}; 

であり、これはインフレ機能

// Applies a power of X to each item in the matrix 
this.matrixInflate = function(matrix, pow) { 
    for(var row=0;row<matrix.length;row++) 
     for(var col=0;col<matrix.length;col++) 
      matrix[row][col] = Math.pow(matrix[row][col], pow); 
}; 

そして最後に、メインパススルー機能行列のクローンを作成するcurrentMatrix.sliceを使用し

// Girvan–Newman algorithm 
this.getMarkovCluster = function(power, inflation) { 
    var lastMatrix = []; 

    var currentMatrix = this.getAssociatedMatrix(); 
    this.print(currentMatrix);   
    this.normalize(currentMatrix); 

    currentMatrix = this.matrixExpand(currentMatrix, power);  
    this.matrixInflate(currentMatrix, inflation);        
    this.normalize(currentMatrix); 

    while(!this.equals(currentMatrix,lastMatrix)) { 
     lastMatrix = currentMatrix.slice(0); 

     currentMatrix = this.matrixExpand(currentMatrix, power);     
     this.matrixInflate(currentMatrix, inflation);   
     this.normalize(currentMatrix);    
    } 
    return currentMatrix; 
}; 

Answer 1

あなたの実装は正しいです。この例は間違っています。

「定常状態に達するまでステップ5と6を繰り返す（収束）」スライドの3つの結果マトリックスは、インフレを実行するだけの結果です。

アルゴリズムに関するいくつかの点を明確にする。

1. 拡大膨張。
2. 精度は重要な要素です。方程式は数学的に収束することはありません。行列の一部の項目が無限小数ではなくゼロになる原因となるCPU上の浮動小数点演算の精度が制限されています。事実、公式の実装では、カットオフ値を使用して、コンバージェンスを高速化し、アルゴリズムの時間の複雑さを改善するために、列ごとに特定の量の項目を削除します。元の論文では、著者はこれの効果を分析し、カットオフが実際にインフレパラメータのわずかな増加と同じ結果を与えると結論付けた。
3. 正規化は、再びそのガイドの式を読み取り、膨張工程の不可欠な部分です。あなたのコードについて

。

1. array.sliceは浅いコピーを作成しますが、matrixExpandに新しい配列を作成するため、これは重要ではありません。
2. matrixExpandの実装は、POW変数を無視し、常に2

すべての要素が同じであると解釈され、すべてのものは最初の行であるが予想される結果のパワーを行いますクラスタ。

Answer 2

です疑わしいと思われる。それは浅いクローンであり、あなたが突然変異しているので、それは問題を引き起こすかもしれません。

パワーポイントのプレゼンテーションの正規化ステップの一部として丸めの言葉がないので、ラウンドの使用も少し奇妙に見えます。