Disconnected components with multilevel
Posted: 04 Oct 2010 11:50
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!
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!