You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@giraph.apache.org by Aapo Kyrola <ak...@cs.cmu.edu> on 2013/02/05 21:34:27 UTC
GreenMarl
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 <ja...@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 <ss...@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..
>> >
>
Re: GreenMarl
Posted by Claudio Martella <cl...@gmail.com>.
Or a bunch of GraphChi nodes in a PowerGraph cluster... ;)
On Tue, Feb 5, 2013 at 11:07 PM, Sebastian Schelter <ss...@apache.org> wrote:
> Hi Aapo,
>
> No worries. I think the future lies in easy to use languages or
> paradigms that can be compiled to or ran in the system of the users
> choice. For some people and problems this might be GraphChi on a single
> machine, for others it might Giraph on a cluster. Might be good to have
> you and the giraph community exchange ideas from time to time :)
>
> Best,
> Sebastian
>
>
>
>
> On 05.02.2013 23:03, Aapo Kyrola wrote:
> >
> > 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 <ak...@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 <ja...@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 <ss...@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
> >
> >
>
>
--
Claudio Martella
claudio.martella@gmail.com
Re: GreenMarl
Posted by Sebastian Schelter <ss...@apache.org>.
Hi Aapo,
No worries. I think the future lies in easy to use languages or
paradigms that can be compiled to or ran in the system of the users
choice. For some people and problems this might be GraphChi on a single
machine, for others it might Giraph on a cluster. Might be good to have
you and the giraph community exchange ideas from time to time :)
Best,
Sebastian
On 05.02.2013 23:03, Aapo Kyrola wrote:
>
> 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 <ak...@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 <ja...@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 <ss...@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
>
>
Re: GreenMarl
Posted by Aapo Kyrola <ak...@cs.cmu.edu>.
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 <ak...@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 <ja...@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 <ss...@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