Graclus

From CLAB

graclus is a fast graph clustering software that computes normalized cut and ratio association for a given undirected graph without any eigenvector computation. This is possible because of the mathematical equivalence between general cut or association objectives (including normalized cut and ratio association) and the weighted kernel k-means objective. One important implication of this equivalence is that we can run a k-means type of iterative algorithm to minimize general cut or association objectives. Therefore unlike spectral methods, our algorithm totally avoids time-consuming eigenvector computation. We have embedded the weighted kernel k-means algorithm in a multilevel framework to develop very fast software for graph clustering.

[edit] Availability

biobase.ist.unomaha.edu (1.2)

phylogeny.ist.unomaha.edu (1.2)

klab.ist.unomaha.edu (1.2)

[edit] Installation

In a ubuntu box, do the following to install graclus:

1. Download and extract graclus.tar.gz
2. chown -R root.root graclus1.2
3. cd graclus1.2
4. make
5. mkdir /usr/local/graclus/ ; cp graclus /usr/local/graclus
6. chown 755 /usr/local/graclus/graclus
7. Make sure /usr/local/graclus is included in the environmental variable PATH.

Notes:

1. 64-bit compile gives segmentation fault and thus it is recommended to do a 32-bit compile. --Mshafiullah 15:40, 18 August 2009 (CDT)
2. The Matlab interface has not been compiled as it requires an installation of MATLAB. --Mshafiullah 15:42, 18 August 2009 (CDT)