Cluster Graph (K-means) module

Description

This module clusters the reactions of a network obtained with this program (it doesn't work on SBML models directly, but it will be implemented in the next version of the program). The output is a file containing the information about the clusters and the visualization of the clusters in the network with the nodes in different colors.

This module clusters vertices of a Graph based on their ranks as calculated by VoltageScorer. This algorithm is based on, but not identical with, the method described in the paper below. The primary difference is that Wu and Huberman assume a priori that the clusters are of approximately the same size, and therefore use a more complex method than k-means (which is used here) for determining cluster membership based on co-occurrence data.

VoltageScorer assigns scores to vertices according to their 'voltage' in an approximate solution to the Kirchoff equations. This is accomplished by tying "source" vertices to specified positive voltages, "sink" vertices to 0 V, and iteratively updating the voltage of each other vertex to the (weighted) average of the voltages of its neighbors.

The algorithm proceeds as follows:

See Also: "'Finding communities in linear time: a physics approach', Fang Wu and Bernardo Huberman, http://www.hpl.hp.com/research/idl/papers/linear/"

Method parameters

Number of clusters
Number of clusters to be returned.