Partitioning of access graph


I have a dataset of users and records, with a binary link between the users and their accessed records. I've tried clustering this dataset using both k-Means and Hierarchical clustering, but have failed to produce any satisfying results.
I've recently tried using Metis to partition a graph containing records as vertices and links to other records with common accessing users as edges. E.g if user 1 and 2 has accessed record 1 and 2, this produces an edge between record 1 and 2, with a weight of 2.

To decide on the optimal number of partitions, I've partitioned the graph into [2..300] partitions, and graphed the resulting edge cut. At ~25 partitions, a "knee" could be observed, similar to that used when optimizing the k-Means clustering algorithm.

Is there any reason why I should not use graph partitioning for this type of problem, and is there any better way on deciding the optimal number of partitions?

Best regards,
Øystein Blixhavn

RE: Have you tried using Cluto to

Have you tried using Cluto to perform this type of clustering? It was designed for this type of data.
As far as automatically determining the number of clusters, I have no great solution other than what you are doing...


RE: Thank you, I will have a look

Thank you, I will have a look at Cluto.