You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@giraph.apache.org by Claudio Martella <cl...@gmail.com> on 2012/08/24 14:31:05 UTC
k-way graph partitioning
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.martella@gmail.com
Re: k-way graph partitioning
Posted by Claudio Martella <cl...@gmail.com>.
Mhm, no i didn't know about it.
I'm going to read it right now, thanks!
On Fri, Aug 24, 2012 at 2:45 PM, Aapo Kyrola <ak...@cs.cmu.edu> wrote:
> 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.
>
>
>
>
--
Claudio Martella
claudio.martella@gmail.com
Re: k-way graph partitioning
Posted by Aapo Kyrola <ak...@cs.cmu.edu>.
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.