Markov Clustering

markovCluster.js

function round(n) {
    return Math.round(n*100) / 100;
}

// Represents an edge from source to sink with capacity
var Edge = function(source, sink, capacity) {
    this.source = source;
    this.sink = sink;
    this.capacity = capacity;
};

// Main class to manage the network
var Graph = function() {
    this.edges = {};
    this.nodes = [];
    this.nodeMap = {};
    
    // Add a node to the graph
    this.addNode = function(node) {
        this.nodes.push(node);
        this.nodeMap[node] = this.nodes.length-1;
        this.edges[node] = [];
    };

    // Add an edge from source to sink with capacity
    this.addEdge = function(source, sink, capacity) {
        // Create the two edges = one being the reverse of the other    
        var edge = new Edge(source, sink, capacity);
        this.edges[source].push(edge);
    };
    
    // Does edge from source to sink exist?
    this.edgeExists = function(source, sink) {
        if(this.edges[source] !== undefined) 
            for(var i=0;i<this.edges[source].length;i++)
                if(this.edges[source][i].sink == sink)
                    return this.edges[source][i];
        return null;
    };
    
    // Turn the set of nodes and edges to a matrix with the value being
    // the capacity between the nodes
    this.getAssociatedMatrix = function() {
        var matrix = [];
        for(var i=0;i<this.nodes.length;i++) {
            var row = [];
            for(var j=0;j<this.nodes.length;j++) {
                var edge = this.edgeExists(this.nodes[j], this.nodes[i]);
                if(i == j) edge = {capacity:1};
                row.push(edge != null ? edge.capacity : 0);
            }
            matrix.push(row);
        }
        return matrix;
    };
        
    // Normalizes a given matrix
    this.normalize = function(matrix) {
        // Find the sum of each column
        var sums = [];
        for(var col=0;col<matrix.length;col++) {
            var sum = 0;
            for(var row=0;row<matrix.length;row++)
                sum += matrix[row][col];
            sums[col] = sum;
        }

        // For every value in the matrix divide by the sum
        for(var col=0;col<matrix.length;col++) 
            for(var row=0;row<matrix.length;row++)
                matrix[row][col] = round(matrix[row][col] / sums[col]);
    };
    
    // Prints the matrix
    this.print = function(matrix) {
        for(var i=0;i<matrix.length;i++) {
            for(var j=0;j<matrix[i].length;j++) {
                document.write((j==0?'':',')+matrix[i][j]);
            }
            document.write('<br>');
        }
    };
        
    // 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);
    };
    
    // Are the two matrices equal?
    this.equals = function(a,b) {
        for(var i=0;i<a.length;i++) 
            for(var j=0;j<a[i].length;j++) 
                if(b[i] === undefined || b[i][j] === undefined || a[i][j] - b[i][j] > 0.1) return false;
        return true;
    };
    
    // 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);
        
        var c = 0;
        while(!this.equals(currentMatrix,lastMatrix)) {
            lastMatrix = currentMatrix.slice(0);

            currentMatrix = this.matrixExpand(currentMatrix, power);                
            this.matrixInflate(currentMatrix, inflation);         
            this.normalize(currentMatrix);            
                       
            if(++c > 500) break; //JIC, fiddle fail
        }
        return currentMatrix;
    };
};

var g = new Graph();

g.addNode('a');
g.addNode('b');
g.addNode('c');
g.addNode('d');

g.addEdge('a','b',1);
g.addEdge('b','a',1);
g.addEdge('a','c',1);
g.addEdge('c','a',1);
g.addEdge('a','d',1);
g.addEdge('d','a',1);
g.addEdge('a','b',1);
g.addEdge('b','d',1);
g.addEdge('d','b',1);

var result = g.getMarkovCluster(2,2);
g.print(result);