# Efficient graph clustering algorithm

I'm looking for an efficient algorithm to find clusters on a large graph (It has approximately 5000 vertices and 10000 edges).

So far I am using the Girvan–Newman algorithm implemented in the JUNG java library but it is quite slow when I try to remove a lot of edges.

Can you suggest me a better alternative for large graphs?

I personally suggest Markov clustering. I have used it several times in the past with good results.

Affinity propagation is another viable option, but it seems less consistent than Markov clustering.

There are various other options, but these two are good out of the box and well suited to the specific problem of clustering graphs (which you can view as sparse matrices). The distance measure you are using is also a consideration. Your life will be easier if you are using a proper metric.

I found this paper while looking for performance benchmarks, it is a good survey of the subject.

• Thanks, I'll have a look at all the algorithms you suggested. – mariosangiorgio Jan 19 '12 at 22:46
• Correction: these algorithms need as input weights that reflect similarity, not distance. The metric property (triangle inequality) does not come into it. It can be useful to transform weights so they fall in a natural range, e.g. for (Pearson) correlations as described here (micans.org/mcl/man/clmprotocols.html#array), and for BLAST E-values as described here (micans.org/mcl/man/clmprotocols.html#blast). – micans Sep 24 '13 at 10:14

## Hierarchical Clustering

This was recommended to me by a friend. According to Wikipedia:

In this method one defines a similarity measure quantifying some (usually topological) type of similarity between node pairs. Commonly used measures include the cosine similarity, the Jaccard index, and the Hamming distance between rows of the adjacency matrix. Then one groups similar nodes into communities according to this measure. There are several common schemes for performing the grouping, the two simplest being single-linkage clustering, in which two groups are considered separate communities if and only if all pairs of nodes in different groups have similarity lower than a given threshold, and complete linkage clustering, in which all nodes within every group have similarity greater than threshold.

## Markov Cluster

This is what I use in your situation. It is a very useful algorithm. I found a link to a nice PDF about the Algorithm. It is a great algorithm, and, for lack of a better term, extremely "powerful". Try it out and see.

For your problem here, I think you should think of a way to map vertices-edges to a set of coordinates for each vertex. I am not sure if there is a better way to do this. But, I think you could start off by representing each vertex as a dimension and then, the edge value to a particular vertex would become the value you need to work with for that particular dimension. After that you could do a simple Euclid distance and work with that.

• After reading up a bit, I found this, here and I think you should have a look. – viki.omega9 Jan 19 '12 at 10:53