# Backbone Layout

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

# 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 structural measures of embeddedness.

More detailed background information is provided in

 (a) drawing based on complete network (b) drawing based on quadrilateral Simmelian backbone

### 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 $O(|E| \triangle(G))$ for a graph G = (V,E) where $\triangle(G)$ is the maximum degree of a vertex $v\in V$.

The final layout based on the extracted backbone needs O( | V | 2) 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: