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