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


So you basically have a similarity matrix, more than a graph. Performing classic clustering (by opposition to graph partitioning), through an algorithm such as $k$-medoids makes sense, in this situation (except clustering algorithms generally use distance or dissimilarity instead of similarity).

If you want to use a graph partitioning approach, and need to build a sparser graph, have a look at this article describing several methods for this purpose: (von Luxburg 2007), section 2.2.

Did you produce the similarity matrix yourself based on some description of your nodes?

  • $\begingroup$ I have a .txt file where each line is in the form: source:dest:weight. The graph in non directed. The bigger the weight is the more similar the nodes are. I said I had a graph cause I'm working with networkx. I built the data set by myself parsing infos from the web $\endgroup$ – viral Mar 10 '17 at 13:11
  • $\begingroup$ Ok, then you can have a look at the paper I mentioned, it proposes methods to build graphs containing only a part of the possible edges. $\endgroup$ – Vincent Labatut Mar 10 '17 at 13:23
  • $\begingroup$ K-means does expect a n x p coordinate matrix, not a distance matrix! $\endgroup$ – Anony-Mousse Mar 10 '17 at 21:52
  • $\begingroup$ @Anony-Mousse you're right, sorry. I was thinking about $k$-medoids. And since viral has the node positions, (s)he can apply whichever. $\endgroup$ – Vincent Labatut Mar 11 '17 at 16:04
  • $\begingroup$ Why do you assume he has positions?it's a social network, similarity is likely not position based. $\endgroup$ – Anony-Mousse Mar 11 '17 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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