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!
HelderStatistics:Posted by heldersuzuki — 04 Oct 2010 17:06
]]>