Markov Clustering Algoritmo

Question

ho lavorato attraverso il seguente esempio dei dettagli dell'algoritmo Markov Clustering:

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

Mi sento come se avessi accuratamente rappresentato l'algoritmo, ma io non sto ottenendo gli stessi risultati che questa guida, almeno, stava ottenendo quell'input.

codice attuale e ': http://jsfiddle.net/methodin/CtGJ9/

Non sono sicuro se forse ho appena perso un piccolo fatto o solo bisogno di un piccolo ritocco da qualche parte per questo, ma ho provato un paio di varianti, tra cui:

1. Scambiare l'inflazione/espansione
2. Controllo per l'uguaglianza sulla base di una precisione
3. Rimozione della normalizzazione (dal momento che la guida originale non ha richiesto, anche se la MCL d ufficiale ocumentation afferma di normalizzare la matrice su ogni passaggio)

Tutti questi hanno restituito lo stesso risultato - il nodo influenza solo se stesso.

Ho anche trovato un'implementazione algoritmo simile in VB: http://mcl.codeplex.com/SourceControl/changeset/changes/17748#MCL%2fMCL%2fMatrix.vb

E il mio codice sembra combaciare con l'eccezione di loro numerazione (600 - distanza, per esempio).

Questa è la funzione di espansione

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

E questa è la funzione di gonfiaggio

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

Infine la funzione principale passante

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

L'implementazione è corretta. L'esempio è semplicemente sbagliato.

Le tre matrici dei risultati nella diapositiva "Ripeti passaggi 5 e 6 fino a raggiungere uno stato stazionario (convergenza)" sono il risultato di SOLO l'inflazione in corso.

Per chiarire alcuni punti sull'algoritmo.

1. Espansione quindi inflazione.
2. La precisione è un fattore importante. Le equazioni non possono mai portare alla convergenza matematicamente. È la precisione limitata delle operazioni in virgola mobile su cpus che fanno sì che alcuni elementi nella matrice diventino zero anziché numeri infinitamente piccoli.Infatti l'implementazione ufficiale utilizza un valore di cutoff per eliminare una certa quantità di elementi per colonna per accelerare la convergenza e migliorare la complessità temporale dell'algoritmo. Nella tesi originale l'autore ha analizzato l'effetto di ciò e ha concluso che il cutoff dà lo stesso risultato in pratica come un leggero aumento del parametro di inflazione.
3. La normalizzazione è una parte integrante della fase di inflazione, leggere nuovamente l'equazione in quella guida.

Per quanto riguarda il codice.

1. array.slice crea una copia superficiale ma questo non è importante nel tuo caso poiché si crea una nuova matrice in matrixExpand.
2. L'implementazione del matrixExpand ignora variabile pow, e sempre fa una potenza di 2.

Il risultato dove ci sono tutti quelli della prima fila è atteso, che viene interpretata come tutti gli elementi sono nella stessa grappolo.

Answer 2

Utilizzo currentMatrix.slice clonare una matrice sembra sospetto. È un clone superficiale, e dal momento che stai mutando, potrebbe significare guai.

Anche l'uso del round sembra un po 'strano, poiché non si fa menzione dell'arrotondamento come parte della fase di normalizzazione in quella presentazione in powerpoint.