My question: How to establish evidence of any clustering in data (compared to clustering from randomly generated data)? Are there established approaches? And does this approach outlined sound reasonable?

In some uses of cluster analysis, different numbers of clusters are specified and the output is compared (i.e., with fit statistics or cross-validation).

In some social network analyses, a technique is used with relational (network) data to first establish whether there are communities or "cliques" evidenced in network ties. Frank's KliqueFinder does this.

The approach is to randomly distribute ties to simulate a network without any clustering (using the same number of ties, i.e. if there are 100 ties across the network, then there will be 100 ties in the simulated data). Then, to apply the clustering algorithm, calculate an index for the degree of clustering, and then repeat some number of times, after which the index for the degree of clustering is compared to the sampling distribution of the index for the degree of clustering from the simulations.

Would this seem to be useful to provide evidence of clustering in non-network data? For instance, if there are three continuous variables each with independent means and standard deviations, could you randomly generate normally distributed data based on those statistics, apply a clustering algorithm, calculate some index of clustering, and compare the index of clustering from that from clustering the actual variables to the sampling distribution of the simulations' index of clustering?

Or, would the correlation between the variables need to be first incorporated into the generation of the simulated data?

I tried this approach (below), and while it worked, I'm concerned that the process is more complicated than just described for continuous variables.

evidence of clustering

  • $\begingroup$ I think that the definition of clustering evidence is remarkably flexible and open-ended therefore ambiguous. I would be really careful about evidence for the existence of a clustering in arbitrary dataset. Data might cluster beautifully with a trivial or (more commonly) a totally incomprehensible combination of the features included. That does not mean that the clustering is any helpful or provides any particular insights (ie. it exists), you may just cluster noise. (cont.) $\endgroup$
    – usεr11852
    Apr 22, 2017 at 23:47
  • $\begingroup$ Clustering is an annoyingly non-robust property so a simulation study relaying on perturbation seems almost destined to succeed on face value. The network structure almost certainly induces some structure on the underlying data so simply removing it and then saying "hey, clustering exists" seems a very low hurdle to pass. For example, why not just perturb some of the feature values under your existing network and then see if a cluster still exists. If it still does... bad luck. :D $\endgroup$
    – usεr11852
    Apr 22, 2017 at 23:52
  • 2
    $\begingroup$ In general, (+1) fun question but really you need to define the core aspects of it very careful so you can later on analytically explore them. $\endgroup$
    – usεr11852
    Apr 22, 2017 at 23:53

1 Answer 1


There are some statistics for this, such as Hopkins statistic of clustering tendency.

But as far as I can tell, this is rather a test against uniformity.

Unfortunately, data can be non-uniform, but not suitable for clustering. Because this test does not ensure there is more than one cluster.

Similar, in above example of randomizing a graph, what you test is how much the graph looks like it was randomized, but does this really capture "clusters"? Can there be non-clustered data that nevertheless looks very different than the simulation?

Because of this, these tests tend to massively overestimate the "evidence", because they use a too random baseline. As a control, you should generate various "non-clustered" data. On networks, you may want to consider various graph generation approaches, Barabasi-Albert etc.

What you'd really want to look for in vector data would be a test for multimodality, because a single Gaussian distribution is not what you'd call "clustered data" (in fact, a single Gaussian is the archetype of random data, isn't it?).

I'm not sure how that would work on a graph... but clearly, simply randomly rewiring the network is too extreme to evaluate clustering evidence.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.