Claudio, do you know this tech-report from Microsoft about streaming graph partitioning: http://research.microsoft.com/apps/pubs/default.aspx?id=155926
The partitioning quality is not of course as good as with Metis, but much much faster and more feasible (Metis requires huge amount of memory on big graphs).. Aapo Kyrola Ph.D. student, http://www.cs.cmu.edu/~akyrola GraphChi: Big Data - small machine: http://graphchi.org On Aug 24, 2012, at 8:31 AM, Claudio Martella wrote: > 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.
