Solved – Clustering a fully connected graph

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.

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


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

  2. Spectral clustering

  3. Affinity propagation

  4. K-medoids with affinity

Similar Posts:

Rate this post

Leave a Comment