giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Aapo Kyrola <akyr...@cs.cmu.edu>
Subject Re: GreenMarl
Date Tue, 05 Feb 2013 22:03:20 GMT

Apologies about posting this email to the group  -it  was meant directly to Jan.

Aapo

On Feb 5, 2013, at 12:34 PM, Aapo Kyrola <akyrola@cs.cmu.edu> wrote:

> Hi Lugt,
> 
> Have you considered a Graphchi code generator for GreenMarl? I like the BFS abstraction!
> 
> Aapo 
> 
> 
> Sent from my iPhone
> 
> On Feb 5, 2013, at 12:19 PM, Jan van der Lugt <janlugt@gmail.com> wrote:
> 
>> Green-Marl comes with an implementation of betweenness centrality and allows you
to compile it to Giraph code:
>> https://github.com/stanford-ppl/Green-Marl
>> 
>> The BC algorithm:
>> https://github.com/stanford-ppl/Green-Marl/blob/master/apps/src/bc_random.gm
>> 
>> On Tue, Feb 5, 2013 at 8:07 PM, Sebastian Schelter <ssc@apache.org> wrote:
>> Hello Pradeep,
>> 
>> the standard betweeness and closeness measures do not scale to large
>> graphs per se, as they require computation of all shortest paths, where
>> even the result is quadratic in the number of vertices and therefore
>> intractable.
>> 
>> U Kang has done some interesting work on finding scalable substitutes
>> for these measures:
>> 
>> "Centralities in large graphs"
>> http://www.cs.cmu.edu/~ukang/papers/CentralitySDM2011.pdf
>> 
>> These algorithms should be relatively simple to implement in Giraph, we
>> had some students prototype them in a university course last year.
>> 
>> Best,
>> Sebastian
>> 
>> 
>> On 05.02.2013 20:23, pradeep kumar wrote:
>> > Hi all,
>> >
>> > Actually we are working on finding centrality for nodes in a graph
>> > (betweenness , closeness and in-out) so far we have just implemented for
>> > in-out and currently working on implementation of brandes alg for finding
>> > betweenness centrality which requires finding shortest path for each node
>> > to every node.
>> >
>> > Actually right now problem we are facing is passing all-nodes list at
>> > beginning for computation of shortest paths.
>> >
>> > 1) Is their a method availabe to achieve this. we are using giraph 1.0..(we
>> > couldnt find method for support in file library)
>> >
>> > 2) Is it possible compute shortest path for node to every other in single
>> > superstep
>> >
>> > 3) or can we use master compute for such computation
>> >
>> > And is there any other way we can compute betweeness for nodes efficiently
>> > in giraph..
>> >
>> > Any suggestion..and..Thanks for help in advance..
>> >
>> 
>> 

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