giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sebastian Schelter <...@apache.org>
Subject Re: About Giraph Design
Date Mon, 28 Oct 2013 16:29:07 GMT
You could implement the LineRank algorithm, which was proposed as a
scalable substitute for betweeness centrality:

http://www.cs.cmu.edu/~ukang/papers/CentralitySDM2011.pdf

--sebastian

On 28.10.2013 17:09, Jyoti Yadav wrote:
> Thanks Sebastian for your reply.
> If we want to implement Betweenness Centrality algo then what should we do?
> 
> Regards
> Jyoti
> 
> 
> On Mon, Oct 28, 2013 at 6:10 PM, Sebastian Schelter <ssc@apache.org> wrote:
> 
>> Hi Jyoti,
>>
>> All-Pairs-Shortest-Path is a problem with a solution quadratic in the
>> number of vertices of the input graph. For a reasonably large graph, you
>> cannot even store the result.
>>
>> For most algorithms that map well to systems like Giraph the amount of
>> messages per iteration is linear in the number of edges of the graph and
>> the number of iterations necessary is small by default or bound by the
>> diameter of the graph.
>>
>> --sebastian
>>
>>
>> On 28.10.2013 05:09, Jyoti Yadav wrote:
>>> Hi..
>>> one doubt is disturbing me..Would anyone suggest an idea?
>>>
>>> Is GIRAPH is designed for solving problems like AllPairShortestPath ?
>>>
>>> Thanks in advance.
>>>
>>> Jyoti
>>>
>>
>>
> 


Mime
View raw message