Disconnected components with multilevel

[graphdrawer]

Hi developers,

Using Gephi I've noticed the way it handles disconnected components is very efficient.

I argue that component is not laid out separately but it seems to me that for each node a force is computed and then integrated.

I understand clearly the way this model work for a layout like Fruchterman Reingold (excluded from the gravity function, which is not documented nor mathematical explained), but for a multilevel method, how can you coarsen the graph separately?

Yifan Hu's paper treats connected graphs and graph coarsening is also a connected component method.

I know that another software like GraphViz, first separates the layouts and then pack them with a polyomino packing approach.

@inproceedings{729558,
author = {Freivalds, Karlis and Dogrus\"{o}z, Ugur and Kikusts, Paulis},
title = {Disconnected Graph Layout and the Polyomino Packing Approach},
year = {2002},
}

but in general the 2D packing approach is NP-hard, so my question remains:

"How to handle disconnected components in a multilevel method?"
"How is the gravity function (if any) introduced?"

Thank you all!

[heldersuzuki]

Hi graphdrawer,

There are two kind of forces in Yifan Hu's algorithm, one is edge driven force (e.g. edges are springs) and another node driven (e.g. electrical repulsion between nodes).

The node driven force doesn't depend on graph connectedness, so you don't have to worry about it.
If you have N nodes then there are roughly n^2/2 force vectors. Since it's not efficient to calculate all those O(n^2) forces, the implementation uses Barnes Hut's N-body method to estimate the resulting force on each node, it takes O(n log n) to estimate the resulting node driven force on each node.

The "gravity function" is a kind of an electrical repulsion and the method works for this kind of field as well, the idea is that if you have a bunch of masses, the resulting force is roughly the same as if you just consider a point located in the center of mass with the sum of the masses.
If you have other kinds of force fields it might be a trickier to calculate the "center of mass" in that force field, but it'll still work.

The graph coarsening implemented is the simplest one and just combines random pair of connected nodes, the original Yifan Hu's method proposes some other fancier methods.

I hope it helps!
Helder

[graphdrawer]

Yes, thank you, it helped.

I've also looked at the source of the code and it clarified my ideas a lot.

A last question remains, what do you specifically mean with autostabilize function?

From the numerical analysis point of view, what you do is a gradient descent minimization of the "potential" function generated from the conservative forces but with a fixed integration step (with some variables hard-coded as SPEED_DIVISOR in FruchtermanReingold).
Why don't implement a smarter integration-step computation approach?

I mean quadratic or cubic step-length interpolation, I suggest the good "Nocedal, Wright - Numerical optimization" book for details (can be a little tricky)

Again, many thanks!

[heldersuzuki]

Hi graphdrawer,

I apologize for the delay, I've been quite busy lately.

Indeed the implementation could use a much smarter numeric integration method.
As you see there are lots of low hanging fruits for improvements

Thanks, Helder