continuous / interactive YifanHu layout

[claudiomartella]

Dear all,

i'm working with a graph that is extracted from a 2D plane. Technically it's called a proximity graph. I plot a bunch of vertices onto a 2D plane (let's call this an "absolute graph", because vertices have (X,Y) coordinates on the plane), I extract a new (proximity) graph connecting two vertices if they are close to each other within a given threshold. If i know take this graph, I shuffle it onto a new 2D plane and run YifanHu on it, I obtain a visualization of the (proximity) graph that is resembling the original (absolute) one ("it unfolds it", basically it's the whole idea behind the ForceAtlas2 layout run on the grid, in the video).
Now, the graph I'm working with is dynamic, meaning that the vertices in the original (absolute) graph move in space over time. As a result, the edges in my proximity graph change over time as well, to reflect these movements in the (absolute) graph. I'd expect the movement of these vertices to show up also in my YifanHu-embedded graph, as a result of the new edges created and the old ones being destroyed, and a layout algorithm working in the background.
Coming to my problem, I'd like a layout similar to ForceAtlas2 that continuously updates the visualization, but that has the characteristics of YifanHu (the ForceAtlas2 layout algorithm doesn't have a good visualization for my type of graph, e.g. the vertices with high degree should not experience high repulsion if they are connected together, actually the opposite).

Any idea of a layout algorithm that can help with my task?

Thanks in advance.

[seinecle]

Hi,

I was just not sure to understand how Force Atlas did not suit your needs? It draws closer the nodes that are connected: why is it a problem?

Best,

Clement

[claudiomartella]

the problem is the repulsion force between nodes with high degree introduced by force atlas. force atlas pushes hubs towards the periphery of the graph, which in my case is actually the opposite.

[seinecle]

I might well be wrong but I don't think that nodes with high degree are pushed to the periphery with Force Atlas. Why would they?

[claudiomartella]

because it was designed for small world graphs. it would avoid cluster to overlap, it would put space between them and make the graph more readable.
quoting the submitted paper on forceatlas2:
"C. Repulsion by degree
We designed ForceAtlas2 to interpret web graphs and social networks. A common feature of
these networks is the presence of many “leaves” (nodes that have only one neighbor). This is
due to the power-law distribution of degrees that characterizes many real-world data. The forest
of “leaves” surrounding the few highly connected nodes is one of the principal sources of visual
cluttering. To improve the readibility of these graphs, we modified the repulsion force.
The idea is to bring poorly connected nodes closer to very connected nodes. Our solution is
to tweak the repulsion force so that poorly connected nodes and very connected nodes repulse
less. As a consequence they will end up being closer in the balanced state. Our
repulsion force Fr is proportional to the produce of the degrees plus one (deg + 1) of the two
nodes. The coefficient kr is defined by the settings."

[seinecle]

Hi,

Coming back to your question. You are indeed correct, thanks for enlighting me on this. Maybe that it is possible to fork Force Atlas's plugin and adapt it to your case?

The formula for the repulsion is described in the paper at the bottom of p. 6. I believe it is implemented on line 143 of this file:
https://github.com/gephi/gephi/blob/mas ... .java#L143

which reads:

Code: Select all

@Override
        public void apply(Node n1, Node n2) {
            NodeData n1Data = n1.getNodeData();
            ForceAtlas2LayoutData n1Layout = n1Data.getLayoutData();
            NodeData n2Data = n2.getNodeData();
            ForceAtlas2LayoutData n2Layout = n2Data.getLayoutData();

            // Get the distance
            double xDist = n1Data.x() - n2Data.x();
            double yDist = n1Data.y() - n2Data.y();
            double distance = (float) Math.sqrt(xDist * xDist + yDist * yDist);

            if (distance > 0) {
                // NB: factor = force / distance
    => here!       double factor = coefficient * n1Layout.mass * n2Layout.mass / distance / distance;

                n1Layout.dx += xDist * factor;
                n1Layout.dy += yDist * factor;

                n2Layout.dx -= xDist * factor;
                n2Layout.dy -= yDist * factor;
            }
        }

If "mass" means degree (did not check it...), modifying this single line might get your feature implemented. Of course it would be interesting to see how this modification plays on the other parameters of the algo...

Best,

Clement