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 <[email protected]> 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 >
