You can do an approximate betweenness centrality, by picking a random set of nodes, say 10, and doing shortest paths from them. We had done something similar in GPS (another open-source Pregel I work on for my thesis). It's described in this tech report (http://ppl.stanford.edu/papers/tr_gm_gps.pdf). But as Claudio says all pairs shortest paths would be infeasible in Giraph.
On Tue, Feb 5, 2013 at 11:38 AM, Claudio Martella < claudio.marte...@gmail.com> wrote: > Hi Prandeep, > > unfortunately giraph is probably not the right tool to compute all pairs > shortest paths. Giraph is a good tool if you want to compute single source > shortest paths, following BFS. I do not know a good way to solve the all > pairs problem without a memory explosion (where every vertex keeps a map > with all the other N-1 vertices). I hope I'm short-seeing, and there's a > solution to your problem. > > > On Tue, Feb 5, 2013 at 8:23 PM, pradeep kumar <pradeep0...@gmail.com>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.. >> >> -- >> Pradeep >> > > > > -- > Claudio Martella > claudio.marte...@gmail.com >
