giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gianluca Righetto <gianl...@menttis.com>
Subject Re: GSoC 2014 - Strongly Connected Components
Date Sun, 16 Mar 2014 19:44:30 GMT
Thanks for the link Aapo!
Even though there are probably some differences in the actual implementation of a GraphChi
algorithm with a Giraph one, this is going to be helpful. Also, I would like to investigate
a potential improvement for the algorithm in that paper which basically consists of removing
as many vertices as possible in the Trimming phase (in some cases, as soon as you remove a
vertex, there might appear other vertices that could be removed). If this proves correct,
I'd be glad to share more thoughts with you so you could do the same for GraphChi (assuming
you haven't tried this yet).

Thanks again!
Gianluca Righetto

Am 16.03.2014 um 15:52 schrieb Aapo Kyrola:

> Hi Gianluca,
> 
> for reference, or comparison, you might want to check GraphChi's implementation of SCC
(based on the same Salihoglu et. al. paper):
> https://github.com/GraphChi/graphchi-cpp/blob/master/example_apps/stronglyconnectedcomponents.cpp
> 
> it is a bit sketchy, but works...
> 
> Aapo
> 
> On Mar 14, 2014, at 1:26 PM, Gianluca Righetto <gianluca@menttis.com> wrote:
> 
>> Hello everyone,
>> 
>> I've been working with Giraph for some time now and I'd like to make some contributions
back to the project through Google Summer of Code.
>> I wrote a project proposal to implement an algorithm for finding Strongly Connected
Components in a graph, based on recently published research papers. The main idea of the algorithm
is to find clusters (or groups) in the graph and it's arguably more insightful than the currently
available Connected Components algorithm.
>> So, if there's any Apache member interested in mentoring this project, please, feel
free to contact me.
>> And any kind of feedback will be greatly appreciated.
>> 
>> You can find the document in Google Drive here: http://goo.gl/1fqqui
>> 
>> Thanks,
>> Gianluca Righetto
> 
> Aapo Kyrola
> Ph.D. student, http://www.cs.cmu.edu/~akyrola
> GraphChi: Big Data - small machine: http://graphchi.org
> twitter: @kyrpov
> 


Mime
View raw message