Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
