giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Semih Salihoglu <se...@stanford.edu>
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.

semih


On Wed, Feb 12, 2014 at 7:54 AM, Claudio Martella <
claudio.martella@gmail.com> 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 user@giraph.apache.org, AFAIK
> user-help@ does not exist.
>
>
> On Wed, Feb 12, 2014 at 3:34 PM, Apostolos Koutras <
> koutras.apostolos@gmail.com> 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 https://github.com/koutras/gb
>> 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 myVertex.java
>>        Overriding the Serialization functions for my implementation
>> according to
>>        BrachaTouegDeadlockVertexValue.
>>
>>
>>
>> 2) overriding the message that a node is passing to another with
>> myMessage.java
>>      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
>
>

Mime
View raw message