Thank you everyone!

I would love to see a comparison of force directed layouts
(specifically LinLog) and label propagation.

I searched but alas nothing -- they seem to be oddly similar?

The current, serial LinLog implementation --
http://code.google.com/p/linloglayout/ -- uses Barnes-Hut simulation
-- n*log(n):

http://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation

I guess the root question is -- do you think it's reasonable to use
giraph for Barnes-Hut simulation?




On Tue, Mar 6, 2012 at 11:34 AM, Claudio Martella
<claudio.marte...@gmail.com> wrote:
> Hi,
>
> I'm not definitely familiar with the algorithm or implementation of
> LinLog, I've been just a user. It should be doable with Giraph if you
> can express it in terms of message-passing between vertices and
> without a dependency on a global view of the graph (except for the
> convergence criteria, such as total energy).
>
> Please consider that Giraph's data model is based on a directed graph,
> this should be a quite "interesting" constraint for you, if your
> implementation is going to modify energy associated with edges (you'd
> have two views over the undirected edge, one in each endpoint).
>
> In general, a good way of doing community analysis would be to look at
> algorithms that belong to the family of label-propagation clustering
> algorithms.
>
>
> Hope this helps,
> Claudio
>
> On Tue, Mar 6, 2012 at 3:28 PM, Timmy Wilson <tim...@smarttypes.org> wrote:
>> Hi giraph community,
>>
>> I'm interested in using giraph for distributed n-body simulation.
>>
>> Initially, i'm interested in force directed layouts -- ie, graph drawing:
>>
>> http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)
>>
>> I'm interested specifically in Dr. Andreas Noack's LinLog energy model
>> -- which performs well w/ community detection:
>>
>> http://www.informatik.tu-cottbus.de/~an/GD/linlog.html
>>
>> I have a few examples of a serial implementation here:
>>
>> http://www.smarttypes.org/
>>
>> The model maximizes the distance between all nodes while minimizing
>> the distance between connected nodes.
>>
>> Without getting into too much detail, i'm curious if anyone has
>> considered using giraph for force directed graph embedding (yet
>> another name for it)?
>>
>> I'm also considering something like http://www.mcs.anl.gov/petsc/ or
>> http://www.cs.cmu.edu/~scandal/alg/nbody.html -- which have fast
>> n-body simulation implementations (Barnes-Hut + Fast Multipole).
>>
>> That said, i think giraph may be a good fit -- curious what the
>> community thinks?
>>
>>
>> Thanks,
>> Timmy Wilson
>> Cleveland, OH
>
>
>
> --
>    Claudio Martella
>    claudio.marte...@gmail.com

Reply via email to