Hello list, I'm looking for a nice k-way graph partitioning algorithm (where with nice I mean that fits easily to the pregel paradigm). The pregel paper has a semi-clustering algorithm with a maxClusters parameter. My understanding of this algorithms is that it requires quite a lot of data to flow around the vertices, as each vertex may pass around the clusters (which consist of the list of vertices belonging to them) etc. It looks quite I/O expensive to me.
I remember from the GPS team, that a k-means-based graph partitioning algorithm was on the works. Do you have anything ready that I could work with with giraph? The requirements of the algorithm should be to have k partitions, and a fair balance (it doesn't necessary have to be |V| / k, but the more balanced, the better). Thanks! Best, Claudio -- Claudio Martella claudio.marte...@gmail.com