Graph measures that express closeness or distance between
nodes can be employed for graph nodes clustering using metric clustering
algorithms. There are numerous measures applicable to this task, and
which one performs better is an open question.We study the performance
of 25 graph measures on generated graphs with different parameters.
While usually measure comparisons are limited to general measure ranking
on a particular dataset, we aim to explore the performance of various
measures depending on graph features. Using an LFR graph generator,
we create a dataset of 11780 graphs covering the whole LFR parameter
space. For each graph, we assess the quality of clustering with k-means
algorithm for each considered measure. Based on this, we determine the
best measure for each area of the parameter space. We find that the
parameter space consists of distinct zones where one particular measure
is the best. We analyze the geometry of the resulting zones and describe
it with simple criteria. Given particular graph parameters, this allows us
to recommend a particular measure to use for clustering.