Solved – Clustering a fully connected graph

Question

I've a graph representing a social network ( 597 nodes, 177906 edges). Each edge has a weight saying how much two nodes are similar. I'd like to apply some clustering algorithm to this network but I think I need to cut some edge. Is there a commonly used threshold to do this?
Can you suggest any particular algorithm? I was suggested to use K-means but I think it badly fit to my data space.

Answer 1

600 nodes is tiny, so you shouldn't have scalability problems.

Try:

1. Hierarchical agglomerative clustering (implement it for similarity, not distance!)

2. Spectral clustering

3. Affinity propagation

4. K-medoids with affinity