giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Martella <>
Subject k-way graph partitioning
Date Fri, 24 Aug 2012 12:31:05 GMT
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).



   Claudio Martella

View raw message