# 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.

Try:

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?

• 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 – viral Mar 10 '17 at 13:11
• 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. – Vincent Labatut Mar 10 '17 at 13:23
• K-means does expect a n x p coordinate matrix, not a distance matrix! – Anony-Mousse Mar 10 '17 at 21:52
• @Anony-Mousse you're right, sorry. I was thinking about $k$-medoids. And since viral has the node positions, (s)he can apply whichever. – Vincent Labatut Mar 11 '17 at 16:04
• Why do you assume he has positions?it's a social network, similarity is likely not position based. – Anony-Mousse Mar 11 '17 at 21:06