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