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
- Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: Untangling the Hairballs of Multi-Centered, Small-World Online Social Media Networks, Journal of Graph Algorithms and Applications, 19(2):595-618, 2015.
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.
A set of 50 synthetic hairball networks with a hidden group structure: