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 ssc.open@googlemail.com
 designates 209.85.214.52 as permitted sender)
Message-ID: <5111666C.8070406@apache.org>
Date: Tue, 05 Feb 2013 21:07:08 +0100
From: Sebastian Schelter <ssc@apache.org>
Reply-To: ssc@apache.org
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:17.0) Gecko/20130106 Thunderbird/17.0.2
MIME-Version: 1.0
To: user@giraph.apache.org
Subject: Re: Trying to implement program to find betweenness centrality in
 giraph
References: 
 <CAGJnLiuhcwSVmot+op0m4ae5SQf=aMwDTcOBdyYiwdRKPMePTw@mail.gmail.com>
In-Reply-To: 
 <CAGJnLiuhcwSVmot+op0m4ae5SQf=aMwDTcOBdyYiwdRKPMePTw@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

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