How to show that k-means fails.

[dlee138]

How exactly do we demonstrate that k-means fails using matlab? Would running k-means multiple times on the same adjacency matrix and showing that it clusters differently on different runs show that it fails (i.e. a graph that is sub-optimally split by k-means on certain runs).

[jtmatterer]

I think the idea is that the graph should "look" like it has certain clusters that are consistently undiscovered by k-means. What it means for a graph to look like it has clusters of vertices is intentionally vague. I can't think of a rigorous definition, can you?

[SandyaS72]

One definition is if you made the graph have distinct components that are each connected- so all the vertices in one component can be reached from each other somehow, but there are no edges between components. Then an intuitive clustering of the graph is by component- each component should be its own cluster.

[dlee138]

Thanks for the responses. For the HW assignment, I simply came up with my own definition of what was an "intuitive" clustering that makes sense. Basically, I wanted my graph to be split up in two components where each component consisted of 3 set of vertices that were all connected to each other (essentially forming a triangle).