title: Markov Clustering Algorithm
body: <p>I've been working through the following example of the details of the Markov Clustering algorithm:</p>
  
  <p><a href="http://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf" rel="noreferrer">http://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf</a></p>
  
  <p>I feel like I have accurately represented the algorithm but I am not getting the same results that this guide, at least, was getting for that input.</p>
  
  <p>Current code is at:
  <a href="http://jsfiddle.net/methodin/CtGJ9/" rel="noreferrer">http://jsfiddle.net/methodin/CtGJ9/</a></p>
  
  <p>I am not sure if perhaps I have just missed a small fact or just need a small tweak somewhere for this but I have tried a few variations including:</p>
  
  <ol>
  <li>Swapping the Inflation/Expansion</li>
  <li>Checking for equality based on a precision</li>
  <li>Removing the normalization (since the original guide did not require it, although the official MCL documentation states to normalize the matrix on every pass)</li>
  </ol>
  
  <p>All of these have returned the same result - the node only influences itself. </p>
  
  <p>I've even found a similar algorithm implementation in VB:
  <a href="http://mcl.codeplex.com/SourceControl/changeset/changes/17748#MCL%2fMCL%2fMatrix.vb" rel="noreferrer">http://mcl.codeplex.com/SourceControl/changeset/changes/17748#MCL%2fMCL%2fMatrix.vb</a></p>
  
  <p>And my code seems to match up with the exception of their numbering (600 - distance for instance). </p>
  
  <p>This is the expansion function</p>
  
  <pre><code>// 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&lt;matrix.length;row++) {
          resultMatrix[row] = [];
          for(var col=0;col&lt;matrix.length;col++) {
              var result = 0;
              for(var c=0;c&lt;matrix.length;c++)
                  result += matrix[row][c] * matrix[c][col];
              resultMatrix[row][col] = result;
          }
      }
      return resultMatrix;
  }; 
  </code></pre>
  
  <p>And this is the inflation function</p>
  
  <pre><code>// Applies a power of X to each item in the matrix
  this.matrixInflate = function(matrix, pow) {
      for(var row=0;row&lt;matrix.length;row++) 
          for(var col=0;col&lt;matrix.length;col++)
              matrix[row][col] = Math.pow(matrix[row][col], pow);
  };
  </code></pre>
  
  <p>And finally the main passthru function</p>
  
  <pre><code>// 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;
  };
  </code></pre>