  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.
