Ok, but why a bipartite graph? I can imagine you can have 2 or 3 coordinates associated with each vertices without actually having multiple vertex types.

## Advertising

On Wednesday, March 7, 2012, Timmy Wilson <tim...@smarttypes.org> wrote: >> while i'd expect from linlog something like an (x,y) coordinate. is >> that correct? > > (x,y,z) is also common -- i think of it as extreme dimension reduction > -- after which you're free to use your favorite gis tool -- > http://postgis.refractions.net/ -- you can also pull in tools from > statistical mechanics/thermodynamics > > Without complicating the algo for efficiency -- the essence of the > energy model is simple -- all nodes repulse each other -- connected > nodes attract each other -- this works for any type of graph -- i'm > using a weighted directed graph -- in which case the weighs influence > the attractive force > > It's all very continuous/natural -- living in a 3d world we've build a > lot of tools/methods to process this kind of information > > The problem is without efficiency methods like Barnes-Hut we have > Cartesian(x,y) or Cartesian(x,y,z) -- because every vertex influences > every other vertex > > An efficient giraph implementation would need 2 layers -- a bipartite > graph -- assuming (x,y,z) reduction -- we would need an Octree graph > interacting dynamically w/ our graph of interest > > > On Wed, Mar 7, 2012 at 5:00 AM, Claudio Martella > <claudio.marte...@gmail.com> wrote: >> My personal take is that they do have similar function (they "extract" >> communities), but they have a general different type of output. in >> label propagation you'd end up with an id for each vertex (the vertex >> id that is the centroid for the community each vertex belongs to), >> while i'd expect from linlog something like an (x,y) coordinate. is >> that correct? >> >> On Wed, Mar 7, 2012 at 2:45 AM, Timmy Wilson <tim...@smarttypes.org> wrote: >>> 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 > -- Claudio Martella claudio.marte...@gmail.com