giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Semih Salihoglu <se...@stanford.edu>
Subject Re: Trying to implement program to find betweenness centrality in giraph
Date Tue, 05 Feb 2013 20:03:25 GMT
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.martella@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 <pradeep0802@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.martella@gmail.com
>

Mime
View raw message