馬爾可夫聚類算法

Question

我經歷過的馬爾可夫聚類算法的細節下面的示例工作：

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

我覺得我已經準確地代表的算法，但我沒有得到相同的結果至少，本指南正在爲此提供意見。

當前的代碼是： http://jsfiddle.net/methodin/CtGJ9/

我不知道，也許我剛纔錯過了一個小的事實，或者只需要一個小的調整，地方對於這一點，但我已經嘗試了一些變化，包括：

1. 交換通貨膨脹/擴展
2. 基於精密
3. 卸下正常化（因爲原來的引導並不需要它檢查平等，雖然官方MCL d ocumentation狀態以在每次通過時對矩陣進行歸一化）

所有這些都返回了相同的結果 - 節點隻影響自身。

我甚至發現，在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); 
}; 

最後主中繼功能

// 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直到達到穩定狀態（收斂）」幻燈片的三個結果矩陣是僅執行通貨膨脹的結果。

澄清有關算法的一些觀點。

1. 展開然後膨脹。
2. 精度是一個重要因素。方程式絕不會導致數學上的收斂。它在cpus上的浮點運算精度有限，導致矩陣中的某些項目變爲零而不是無限小的數字。實際上，官方實現使用臨界值來消除每列中的一定數量的項目，以加速收斂並提高算法的時間複雜度。在原始論文中，作者分析了這種影響，並得出結論：在實踐中，截止值與通脹參數略有增加的結果相同。
3. 標準化是通脹步驟的一個組成部分，再次閱讀該指南中的等式。

關於你的代碼。

1. array.slice創建一個淺拷貝，但這並不重要，因爲你在matrixExpand中創建了一個新的數組。
2. 你實現matrixExpand的忽略戰俘變量，始終不2.

那裏有第一行中的所有的人預計的結果，這被解釋爲所有元素力量都在同簇。

Answer 2

使用currentMatrix.slice克隆一個矩陣看起來很可疑。這是一個淺層克隆，而且由於你在變異，這可能會帶來麻煩。

圓的使用也看起來有點奇怪，因爲沒有提到四捨五入作爲該powerpoint演示文稿中規範化步驟的一部分。