The distance backbone of directed networks

Area of Science:

• Network Science
• Graph Theory
• Complex Systems

Background:

• Complex networks exhibit structural redundancies crucial for dynamics and evolution.
• Previous methods for uncovering redundancy were limited to undirected graphs.
• The distance backbone concept is vital for understanding network transmission, path inference, and robustness.

Purpose of the Study:

• To extend a parameter-free methodology for uncovering redundancy to weighted directed graphs.
• To analyze redundancy and robustness in diverse real-world directed networks.
• To provide a tool for principled network sparsification and robustness measurement.

Main Methods:

• Algebraically-principled methodology adapted for weighted directed graphs.
• Analysis of nine diverse networks (social, biomedical, technical).
• Quantification of redundancy using the size of the directed distance backbone.

Main Results:

• The extended methodology effectively identifies structural redundancy in directed graphs.
• Directed graphs, like undirected ones, generally possess substantial redundancy.
• The size of the directed distance backbone serves as a robust measure of redundancy.

Conclusions:

• The developed methodology is applicable to weighted directed complex networks.
• Structural redundancy is a common feature in directed networks, impacting their properties.
• This work enhances tools for network analysis, sparsification, and robustness assessment.