Difference between revisions of "Backbone Layout"
Line 32: | Line 32: | ||
The final layout based on the extracted backbone needs <math>O(|V|^2)</math> time and memory, which does not scale for very large graphs. | The final layout based on the extracted backbone needs <math>O(|V|^2)</math> time and memory, which does not scale for very large graphs. | ||
+ | |||
+ | === Example Data === | ||
+ | A set of 50 synthetic hairball networks with a hidden group structure: | ||
+ | * [[Hairball_Graphs_(data)| '''Dataset Description''']] | ||
+ | * Download: [[Media:Hairball-Graphs-PPM500.zip|'''Hairball-Graphs-PPM500.zip''']] (11 MB) |
Revision as of 12:57, 28 August 2014
Backbone Layout
Method
Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs.
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities.
Strong ties are identified using a measure of embeddedness which is based on a weighted accumulation of triangles in quadrangles.
More detailed background information is provided in
- Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: Untangling Hairballs: From 3 to 14 Degrees of Separation, Proc. 22nd Intl. Symp. Graph Drawing (GD 2014), to appear.
Complexity
The computation of the embeddedness together with the backbone extraction scales well for large networks with, e.g., millions of edges and nodes.
The asymptotic runtime is for a graph where is the maximum degree of a vertex .
The final layout based on the extracted backbone needs time and memory, which does not scale for very large graphs.
Example Data
A set of 50 synthetic hairball networks with a hidden group structure:
- Dataset Description
- Download: Hairball-Graphs-PPM500.zip (11 MB)