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 janlugt@gmail.com designates
 209.85.223.177 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <5111666C.8070406@apache.org>
References: 
 <CAGJnLiuhcwSVmot+op0m4ae5SQf=aMwDTcOBdyYiwdRKPMePTw@mail.gmail.com>
	<5111666C.8070406@apache.org>
Date: Tue, 5 Feb 2013 20:19:38 +0000
Message-ID: 
 <CAMOYj4D-3_HZuMV3BQ0LH6n9TpkWERd9TGbdBvSWVabVpw12zw@mail.gmail.com>
Subject: Re: Trying to implement program to find betweenness centrality in
 giraph
From: Jan van der Lugt <janlugt@gmail.com>
To: user@giraph.apache.org, ssc@apache.org
Content-Type: multipart/alternative; boundary=e89a8f83ac2dd8f7db04d4ffed66

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

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..
> >
>
>

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

Green-Marl comes with an implementation of betweenness centrality and allow=
s you to compile it to Giraph code:<div><a href=3D"https://github.com/stanf=
ord-ppl/Green-Marl">https://github.com/stanford-ppl/Green-Marl</a></div><di=
v>
<br></div><div>The BC algorithm:</div><div><a href=3D"https://github.com/st=
anford-ppl/Green-Marl/blob/master/apps/src/bc_random.gm">https://github.com=
/stanford-ppl/Green-Marl/blob/master/apps/src/bc_random.gm</a><br><br><div =
class=3D"gmail_quote">
On Tue, Feb 5, 2013 at 8:07 PM, Sebastian Schelter <span dir=3D"ltr">&lt;<a=
 href=3D"mailto:ssc@apache.org" target=3D"_blank">ssc@apache.org</a>&gt;</s=
pan> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex=
;border-left:1px #ccc solid;padding-left:1ex">
Hello Pradeep,<br>
<br>
the standard betweeness and closeness measures do not scale to large<br>
graphs per se, as they require computation of all shortest paths, where<br>
even the result is quadratic in the number of vertices and therefore<br>
intractable.<br>
<br>
U Kang has done some interesting work on finding scalable substitutes<br>
for these measures:<br>
<br>
&quot;Centralities in large graphs&quot;<br>
<a href=3D"http://www.cs.cmu.edu/~ukang/papers/CentralitySDM2011.pdf" targe=
t=3D"_blank">http://www.cs.cmu.edu/~ukang/papers/CentralitySDM2011.pdf</a><=
br>
<br>
These algorithms should be relatively simple to implement in Giraph, we<br>
had some students prototype them in a university course last year.<br>
<br>
Best,<br>
Sebastian<br>
<div class=3D"HOEnZb"><div class=3D"h5"><br>
<br>
On <a href=3D"tel:05.02.2013%2020" value=3D"+31502201320">05.02.2013 20</a>=
:23, pradeep kumar wrote:<br>
&gt; Hi all,<br>
&gt;<br>
&gt; Actually we are working on finding centrality for nodes in a graph<br>
&gt; (betweenness , closeness and in-out) so far we have just implemented f=
or<br>
&gt; in-out and currently working on implementation of brandes alg for find=
ing<br>
&gt; betweenness centrality which requires finding shortest path for each n=
ode<br>
&gt; to every node.<br>
&gt;<br>
&gt; Actually right now problem we are facing is passing all-nodes list at<=
br>
&gt; beginning for computation of shortest paths.<br>
&gt;<br>
&gt; 1) Is their a method availabe to achieve this. we are using giraph 1.0=
..(we<br>
&gt; couldnt find method for support in file library)<br>
&gt;<br>
&gt; 2) Is it possible compute shortest path for node to every other in sin=
gle<br>
&gt; superstep<br>
&gt;<br>
&gt; 3) or can we use master compute for such computation<br>
&gt;<br>
&gt; And is there any other way we can compute betweeness for nodes efficie=
ntly<br>
&gt; in giraph..<br>
&gt;<br>
&gt; Any suggestion..and..Thanks for help in advance..<br>
&gt;<br>
<br>
</div></div></blockquote></div><br></div>

--e89a8f83ac2dd8f7db04d4ffed66--