Mailing-List: contact user-help@giraph.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@giraph.apache.org
Received-SPF: pass (nike.apache.org: domain of semihsalihoglu@gmail.com
 designates 209.85.210.171 as permitted sender)
MIME-Version: 1.0
Sender: semihsalihoglu@gmail.com
In-Reply-To: 
 <CAFJOoJfWd=DBr9qJMvK6k4OaZFqit3rLCvtEas8ZyQ8bjPmeoA@mail.gmail.com>
References: 
 <CAGJnLiuhcwSVmot+op0m4ae5SQf=aMwDTcOBdyYiwdRKPMePTw@mail.gmail.com>
 <CAFJOoJfWd=DBr9qJMvK6k4OaZFqit3rLCvtEas8ZyQ8bjPmeoA@mail.gmail.com>
From: Semih Salihoglu <semih@stanford.edu>
Date: Tue, 5 Feb 2013 12:03:25 -0800
Message-ID: 
 <CAJy6w2er0Yb_xBBaqLrzHOfp--HH5Oirg+rGjQzbFqFjdAx6vw@mail.gmail.com>
Subject: Re: Trying to implement program to find betweenness centrality in
 giraph
To: user@giraph.apache.org
Content-Type: multipart/alternative; boundary=14dae9340d15fec95d04d4ffb4ad

--14dae9340d15fec95d04d4ffb4ad
Content-Type: text/plain; charset=ISO-8859-1

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
>

--14dae9340d15fec95d04d4ffb4ad
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

You can do an approximate betweenness centrality, by picking a random set o=
f 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&#39=
;s described in this tech report (<a href=3D"http://ppl.stanford.edu/papers=
/tr_gm_gps.pdf">http://ppl.stanford.edu/papers/tr_gm_gps.pdf</a>). But as C=
laudio says all pairs shortest paths would be infeasible in Giraph.<br>

<br><div class=3D"gmail_quote">On Tue, Feb 5, 2013 at 11:38 AM, Claudio Mar=
tella <span dir=3D"ltr">&lt;<a href=3D"mailto:claudio.martella@gmail.com" t=
arget=3D"_blank">claudio.martella@gmail.com</a>&gt;</span> wrote:<br><block=
quote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc=
 solid;padding-left:1ex">

<div dir=3D"ltr">Hi Prandeep,<div><br></div><div>unfortunately giraph is pr=
obably 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 BF=
S. 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&#39;m short-seeing, and there&#39;s a solution to your problem.<=
/div>


</div><div class=3D"gmail_extra"><div><div class=3D"h5"><br><br><div class=
=3D"gmail_quote">On Tue, Feb 5, 2013 at 8:23 PM, pradeep kumar <span dir=3D=
"ltr">&lt;<a href=3D"mailto:pradeep0802@gmail.com" target=3D"_blank">pradee=
p0802@gmail.com</a>&gt;</span> wrote:<br>


<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr">Hi all,<div><br></div><div>=
Actually we are working on finding centrality for nodes in a graph (between=
ness , closeness and in-out) so far we have just implemented for in-out=A0a=
nd currently working on implementation of brandes alg for finding betweenne=
ss centrality which requires finding shortest path for each node to every n=
ode.</div>


<div><br></div><div>Actually right now problem we are facing is passing all=
-nodes list at beginning for computation of shortest paths.</div><div><br><=
/div><div>1) Is their a method availabe to achieve this. we are using girap=
h 1.0..(we couldnt find method for support in file library)</div>


<div><br></div><div>2) Is it possible compute shortest path for node to eve=
ry other in single superstep=A0</div><div><br></div><div>3) or can we use m=
aster compute for such computation</div><div><br>
</div><div>And is there any other way we can compute betweeness for nodes e=
fficiently in giraph..</div><div><br></div><div>Any suggestion..and..Thanks=
 for help in advance..</div><span><font color=3D"#888888"><div>

<br></div><div>-- <br>
Pradeep<br>
</div></font></span></div>
</blockquote></div><br><br clear=3D"all"><div><br></div></div></div><span c=
lass=3D"HOEnZb"><font color=3D"#888888">-- <br> =A0 =A0Claudio Martella<br>=
 =A0 =A0<a href=3D"mailto:claudio.martella@gmail.com" target=3D"_blank">cla=
udio.martella@gmail.com</a>=A0 =A0
</font></span></div>
</blockquote></div><br>

--14dae9340d15fec95d04d4ffb4ad--