Documentation of 'medusa.georgios.enhanced_mcl.My_MarkovClustering' Java class
My_MarkovClustering
Skip navigation links
medusa.georgios.enhanced_mcl

Class My_MarkovClustering


  • public class My_MarkovClustering
extends java.lang.Object
    My_MarkovClustering implements the Markov clustering (MCL) algorithm for graphs, using a HashMap-based sparse representation of a Markov matrix, i.e., an adjacency matrix m that is normalised to one. Elements in a column / node can be interpreted as decision probabilities of a random walker being at that node. Note: whereas we explain the algorithms with columns, the actual implementation works with rows because the used sparse matrix has row-major format.

    The basic idea underlying the MCL algorithm is that dense regions in sparse graphs correspond with regions in which the number of k-length paths is relatively large, for small k in N, which corresponds to multiplying probabilities in the matrix appropriately. Random walks of length k have higher probability (product) for paths with beginning and ending in the same dense region than for other paths.

    The algorithm starts by creating a Markov matrix from the graph, for which first the adjacency matrix is added diagonal elements to include self-loops for all nodes, i.e., probabilities that the random walker stays at a particular node. After this initialisation, the algorithm works by alternating two operations, expansion and inflation, iteratively recomputing the set of transition probabilities. The expansion step corresponds to matrix multiplication (on stochastic matrices), the inflation step corresponds with a parametrized inflation operator Gamma_r, which acts column-wise on (column) stochastic matrices (here, we use row-wise operation, which is analogous).

    The inflation operator transforms a stochastic matrix into another one by raising each element to a positive power p and re-normalising columns to keep the matrix stochastic. The effect is that larger probabilities in each column are emphasised and smaller ones deemphasised. On the other side, the matrix multiplication in the expansion step creates new non-zero elements, i.e., edges. The algorithm converges very fast, and the result is an idempotent Markov matrix, M = M * M, which represents a hard clustering of the graph into components.

    Expansion and inflation have two opposing effects: While expansion flattens the stochastic distributions in the columns and thus causes paths of a random walker to become more evenly spread, inflation contracts them to favoured paths.

    Description is based on the introduction of Stijn van Dongen's thesis Graph Clustering by Flow Simulation (2000); for a mathematical treatment of the algorithm and the associated MCL process, see there.

    • Constructor Detail

      • My_MarkovClustering

        public My_MarkovClustering()

      • My_MarkovClustering

        public My_MarkovClustering(java.lang.String filename)

      • My_MarkovClustering

        public My_MarkovClustering(java.util.ArrayList<java.lang.String> list)

    • Method Detail

      • main

        public static void main(java.lang.String[] args)
        test the MCL algorithm with the matrix loaded from the file in the argument. If no argument is given, the default file for the matrix T(G3 + I) from van Dongen (2000), page 50.
        Parameters:
        args -

      • show_clusters

        public void show_clusters()
        run the MCL process.
        Parameters:
        a - matrix
        maxResidual - maximum difference between row elements and row square sum (measure of idempotence)
        pGamma - inflation exponent for Gamma operator
        loopGain - values for cycles
        maxZero - maximum value considered zero for pruning operations

      • getNumberOfClusters

        public int getNumberOfClusters()

      • Save_To_File

        public java.lang.String Save_To_File(java.lang.String filename,
                                     boolean storeFile)

      • getReport

        public java.lang.String getReport()

      • setReport

        public void setReport(java.lang.String str)

      • run

        public SparseMatrix run(SparseMatrix a,
                        double maxResidual,
                        double pGamma,
                        double loopGain,
                        double maxZero)

      • inflate

        public double inflate(SparseMatrix m,
                      double p,
                      double zeromax)
        inflate stochastic matrix by Hadamard (elementwise) exponentiation, pruning and normalisation :

        result = Gamma ( m, p ) = normalise ( prune ( m .^ p ) ).

        By convention, normalisation is done along rows (SparseMatrix has row-major representation)

        Parameters:
        m - matrix (mutable)
        p - exponent as a double
        zeromax - below which elements are pruned from the sparse matrix
        Returns:
        residuum value, m is modified.

      • expand

        public SparseMatrix expand(SparseMatrix m)
        expand stochastic quadratic matrix by sqaring it with itself: result = m * m. Here normalisation is rowwise.
        Parameters:
        matrix -
        Returns:
        new matrix (pointer != argument)
Skip navigation links

DMelt 3.0 © DataMelt by jWork.ORG

You see the box below because you did not login.