The simple answer is “it depends on your data and the question that you are posing about your data”. Furthermore, "it may depend on who is your audience".
I understand that you split the literature in two groups that do not "talk" very much with each other (different periodicals, books, conferences...).
First approach: the classical and conventional approaches used in Machine Learning/Statistics.
Many possible different solutions, but as far as I know, the most popular ones are based on similarity metrics such as Euclidean distance, Cosine...
Second approach: more common among people that belongs to the field of Networks/Complex Networks/Social Networks. Some possibilities are here.
Most solutions are based in two different concepts: (1) Modularity (2)
Surprise (you do not need actually to evaluate the distance here - are you thinking about something else?):
Let me try to defend my assertion “it depends on your data and the question that you are posing about your data” through examples:
1) Imagine that you have a network of airports in some country and the only data that you have is the flow from one airport to the other and the intention of your work is to identify “clusters” or “communities” among these possible collection of airports (for business proposals you want to know whether the average person that lives in the north of USA travels in her/his neighborhood or not) For me the most natural approach in this case would be the second approach. Note that there is no “natural similarity (distance)” to be associated with two airports in this network. We can build (I actually did something very related to this - although the focus was not to find exactly community structure), but maybe you understand what I am trying to say: 10 people in the same room may build a different metric and some of them may not make any sense for you or for me. Anyway, it may not be natural to everyone, but we can build a similarity function and we can use the first approach.
2) Your example… Imagine now that you have a some data and a clear similarity function. I would try a method of the first approach. Because you have all you need at hand and it is more natural.
However, the things are not so simple. There are some cases that both approaches may be natural. In the end, you will need to “sell” the technique you used for someone (your boss, your advicer, yourself). It will be much easier if you use the technique your community is more used to applying in similar situations.
If you are like me and you do not like the answer that I am giving to you, I would try to build simulate data (monte carlo simulation) that try to cover all the aspects of your data and compare the methods. However, is it possible to "model" all the aspects of the data? What is the generator process of the data? This is another difficult question.
I have not finished yet.
You compared two big fields of clustering/community detection.
Minor differences in your data or the similarity distance that you used will return different clusters. Let me give another example:
3) As far as I know when people use the K-means usually consider the Euclidean Distance. However, if you go to the field of Natural Language Processing people prefer to use the cosine similarity because in this field they use the cos similarity among vectors of TF-IDF, that makes much more sense than the Euclidean distance in this case. Although there is a relation between the Euclidean Distance and cos similarity, you have to change the algorithm. In this case, you have to use the Spherical K-means.