Markov algoritmo de clústeres de

Question

He estado trabajando a través del siguiente ejemplo de los detalles del algoritmo de Markov La agrupación:

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

Siento que he representado con precisión el algoritmo, pero no estoy obteniendo los mismos resultados que esta guía, al menos, estaba recibiendo esa información.

código actual está en: http://jsfiddle.net/methodin/CtGJ9/

No estoy seguro de si tal vez he acaba de perder una pequeña hecho o sólo hay un pequeño pellizco en algún lugar para esto, pero he intentado algunas variaciones, incluyendo:

1. Intercambio de la inflación/expansión
2. Comprobación de la igualdad sobre la base de una precisión
3. Extracción de la normalización (ya que la guía original no lo requiere, aunque el oficial d MCL estados de ocupación para normalizar la matriz en cada pasada)

Todos estos han arrojado el mismo resultado: el nodo solo influye en sí mismo.

incluso he encontrado una aplicación algoritmo similar en VB: http://mcl.codeplex.com/SourceControl/changeset/changes/17748#MCL%2fMCL%2fMatrix.vb

Y mi código parece coincidir con la excepción de su numeración (600 - distancia, por ejemplo).

Esta es la función de expansión

// 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; 
}; 

Y esta es la función de la inflación

// 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); 
}; 

Y, finalmente, la función principal de tránsito

// 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

Su implementación es correcta. El ejemplo es simplemente incorrecto

Las tres matrices de resultados en "Repita los pasos 5 y 6 hasta que se llegue a un estado estacionario (convergencia)" son los resultados de SÓLO realizar el inflado.

Para aclarar algunos puntos sobre el algoritmo.

1. Expantion then inflation.
2. La precisión es un factor importante. Las ecuaciones nunca pueden conducir a la convergencia matemáticamente. Es la precisión limitada de las operaciones de punto flotante en la CPU que hace que algunos elementos de la matriz se conviertan en cero en lugar de números infinitamente pequeños.De hecho, la implementación oficial utiliza un valor de corte para eliminar una cierta cantidad de elementos por columna para acelerar la convergencia y mejorar la complejidad del algoritmo en el tiempo. En la tesis original, el autor analizó el efecto de esto y concluyó que el corte da el mismo resultado en la práctica que un ligero aumento del parámetro de inflación.
3. La normalización es una parte integral del paso de inflación; vuelva a leer la ecuación en esa guía.

En cuanto a su código.

1. array.slice crea una copia poco profunda, pero esto no es importante en su caso ya que crea una nueva matriz en matrixExpand.
2. Su puesta en práctica de matrixExpand ignora la variable prisionero de guerra, y siempre tiene una potencia de 2.

El resultado donde hay todos los de la primera fila se espera, que se interpreta como todos los elementos están en la misma racimo.

Answer 2

Usando currentMatrix.slice para clonar una matriz parece sospechoso Es un clon superficial, y como estás mutando, eso puede ser un problema.

El uso de la ronda también parece un poco extraño, ya que no se menciona el redondeo como parte del paso de normalización en esa presentación de PowerPoint.