Mapping the Structure of Directed Networks: Beyond the "Bow-tie" Diagram

Abstract

We reveal a hierarchical, multilayer organization of finite components -- i.e., tendrils and tubes -- around the giant connected components in directed networks and propose efficient algorithms allowing one to uncover the entire organization of key real-world directed networks, such as the World Wide Web, the neural network of \emph{Caenorhabditis elegans}, and others. With increasing damage, the giant components decrease in size while the number and size of tendril layers increase, enhancing the susceptibility of the networks to damage.

arXiv comment5 pages, 4 figures

References in corpus (7)

• The structure and function of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Percolation on sparse networks
• Giant strongly connected component of directed networks
• Percolation in Directed Scale-Free Networks
• Generalized percolation in random directed networks

Cited by in corpus (14)

• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Network structural origin of instabilities in large complex systems
• Sensitivity of directed networks to the addition and pruning of edges and vertices
• Linear stability analysis for large dynamical systems on directed random graphs
• Dynamical Mean-Field Theory of Complex Systems on Sparse Directed Networks
• Large order fluctuations, switching, and control in complex networks
• Extended-range percolation in complex networks
• Generalized $k$-core pruning process on directed networks
• Generating functions for message-passing on weighted networks: directed bond percolation and SIR epidemics
• On the accuracy of message-passing approaches to percolation in complex networks
• Simple estimation of hierarchical positions and uncertainty in networks of asymmetric interactions
• Connected components in networks with higher-order interactions
• Bipartitioning of directed and mixed random graphs
• Topological Components in a Community Currency Network