I have a few datasets of "interactions" between pairs of elements like so:

element1 element2 1
element2 element3 1
element4 element5 1
element505535 element4 2

where the value in the 3rd column is the "strength" of interaction. Almost all of these strengths are "1." A strength of 1 means that this interaction was observed one time. A strength of 2 means 2x, etc. I have actually gone one step further and normalized all of my datasets by the total # of interactions observed in the dataset so that datasets interaction values can be compared.

There are 5-6 million interactions listed in each file and each dataset is obviously under-sampled since there are ~500k elements (making a square matrix of ~250 trillion positions).

I would like to cluster these datasets so that I can make statements about which types of elements tend to cluster with which other types elements. Obviously, robusticity of clustering will be a factor—but this is partially ameliorated by the fact that I will make biological replicates of the data.

I have tried a few different "naive" clustering approaches just to see what I could do easily with the data. I fully realize that these are problematic ways of clustering, either because they are not robust or because they rely on the data being very undersampled, but here is what I've done:

  1. Clustering elements together as long as there is at least one interaction between each element in the cluster and at least one other element in the cluster. When I do this, all the elements end up in a single cluster. This was important to do because it tells me that there are no pairs of elements that are totally isolated from the rest of the group.

  2. Finding "superclusters"—that is, clusters where every member of the cluster interacts with every other member of the cluster (e.g. a triangle for a cluster of 3 and a box with an X in the middle for a cluster of 4, etc). This yields almost exclusively clusters with 2 and 3 elements after about 10% of the data has been analyzed (this is still running).

I would love to be able to do some sort of hierarchical clustering using my "interaction strength" values as the distance measure between each pair of elements (unobserved interactions have a strength of 0). Does anyone know of a way to do HC on this sort of large, sparse data—or know of a clustering method that might be more appropriate? I've used R up until now.

  • $\begingroup$ we have developed a very efficient and parallel clustering algorithm, if you are interested, please let me know $\endgroup$ Commented Apr 22, 2014 at 11:46

1 Answer 1


Does this happen to be protein interaction data? Regardless, there are many algorithms you can try. I am the author of mcl, a clustering algorithm fairly often used in bioinformatics. You could easily try it, after installing, by given it the data in exaxctly the format you describe; the command line would be "mcl yourdata --abc" (the abc option tells mcl to expect this particular format). You need not and cannot specify the number of clusters, as cluster structure arises from the process computed by mcl in an emergent fashion. Protein interaction data can be quite voluminous and noisy -- and other data sources as well of course. Especially the presence of nodes of very high-degree (say with hundreds to thousands of neighbours) may obscure cluster structure. In such a scenario, in the absence of weights, it can be really worthwhile to try to reduce the input graph by e.g. a k-NN transform taking into account the two-step graph incidence relation. mcl also provides means to do this, as well a tool that lists various graph traits under a series of ever more stringent transformations, so that it is possible to choose such a transformation in an informed manner. As for hierarchical clustering, it is possible to achieve clusterings at different levels of granularity by varying mcl's so-called inflation parameter. You could for example supply three values (e.g. 1.4, 2, and 5) to obtain clustering at different levels of granularity. It is also possible to arrange clusterings thus obtained into a strictly hierarchical data structure.

  • $\begingroup$ My data is related to protein interaction data. We can talk about it more in detail (privately) if you are interested. I will look into MCL—thanks! $\endgroup$
    – Ron Gejman
    Commented May 6, 2011 at 15:13
  • $\begingroup$ Nice simulation on your website $\endgroup$
    – Zarbouzou
    Commented May 6, 2011 at 16:06
  • $\begingroup$ can this be used for document clustering where there are thousands of features and sparse data vectors. each word is represented as bag of words via TF-IDF value $\endgroup$ Commented Apr 4, 2016 at 23:07

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.