giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jan van der Lugt <janl...@gmail.com>
Subject Re: Trying to implement program to find betweenness centrality in giraph
Date Tue, 05 Feb 2013 20:19:38 GMT
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..
> >
>
>

Mime
View raw message