giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Semih Salihoglu <>
Subject Re: Completing betweeness on giraph
Date Thu, 13 Feb 2014 05:56:55 GMT
Hi Apostolos,

What exactly is not working probably when overriding messages and vertex
values? I haven't used Giraph in a while but these seem like minor
configuration issues.

About the algorithm: You're right it's possible to do bc in  Giraph but as
Claudio said and unless I misunderstood your approach,  what you propose
doesn't seem to scale to large graphs, say with 1B vertices. Running 1B
SSSPs in a row wouldn't be feasible. But yes, it's doable and correct but
it wouldn't be scalable.


On Wed, Feb 12, 2014 at 7:54 AM, Claudio Martella <> wrote:

> i don't think the point is whether following your approach, which is a
> concatenation of SSSP, this is possible, but whether given the the sizes of
> graphs your approach is actually feasible.
> About your questions, you have to implement a type for your Vertex Value
> and one for the Message, and make sure they implement Writable correctly,
> to ensure serializability.
> P.S.= you should post (and subscribe) to, AFAIK
> user-help@ does not exist.
> On Wed, Feb 12, 2014 at 3:34 PM, Apostolos Koutras <
>> wrote:
>> Hi fellow developer Semih Salihoglu,
>> In the past day, I am struggling on completing calculating Betweeness for
>> a graph.
>> Browsing in some forums, some stated that this cannot be done.
>> This point of view is simply put WRONG!.
>> I have uploaded my work in
>> where everyone with an interest can browse and provide insight, as I have
>> been developing
>> for about 12 straight hours and I have not the right experience yet.
>> The main algorithm is based on SimpleShortestPathsComputation  for the
>> main algorithm (brande's algorithm) but I needed to store extra values in
>> each node, and as an effect override
>> the message also.
>> The trick I've thought about for the algorithm to work is provide the
>> input of nodes in ascending
>> value, starting from 1 to number of nodes, and as such, to complete a bfs
>> each time I have to
>> wait for number of nodes supersteps each time. This can easily be done by
>>  mod(superstep,nodes_num).
>> After the end of that phase I do some calculations in each node, and I
>> clear the distance value,
>> in order to continue running the SimpleShortestPaths algorithm but with
>> the next vertex
>> as a source in ascending order.
>>  I was also based
>> on BrachaTouegDeadlockComputation for overriding message and vertex value,
>> (message is based on BrachaTouegDeadlockMessage and vertex value on
>>  BrachaTouegDeadlockVertexValue located in utils
>> on respect.)
>> The things I had found difficulty so far is not the algorithm by itself
>> that is the brande's algorithm,
>> but integrating the following things.
>>  1) overriding the value of vertex with mine using
>>        Overriding the Serialization functions for my implementation
>> according to
>>        BrachaTouegDeadlockVertexValue.
>> 2) overriding the message that a node is passing to another with
>>      I've added the accessors that I wanted but I dont now what to do
>> with readFields, and write,
>>      that the BrachaTouegDeadlockMessage has, for my implementation
>> Any help on the above matters is very appreciated. Thank you all, and
>> sorry for the long post
>> So this CAN be done! If this algorithm is effective is another topic of
>> conversation.
>> Thanks for your time, and once again sorry for the long post
> --
>    Claudio Martella

View raw message