20

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?

5

3 Answers 3

13

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.

2
  • Thanks, I'll have a look at all the algorithms you suggested. Jan 19, 2012 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, 2013 at 10:14
10

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.

5

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.

1
  • 1
    After reading up a bit, I found this, here and I think you should have a look. Jan 19, 2012 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.