TY - GEN
T1 - The distance backbone of directed networks
AU - Costa, Felipe Xavier
AU - Correia, Rion Brattig
AU - Rocha, Luis M.
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023/1/26
Y1 - 2023/1/26
N2 - In weighted graphs the shortest path between two nodes is often reached through an indirect path, out of all possible connections, leading to structural redundancies which play key roles in the dynamics and evolution of complex networks. We have previously developed a parameter-free, algebraically-principled methodology to uncover such redundancy and reveal the distance backbone of weighted graphs, which has been shown to be important in transmission dynamics, inference of important paths, and quantifying the robustness of networks. However, the method was developed for undirected graphs. Here we expand this methodology to weighted directed graphs and study the redundancy and robustness found in nine networks ranging from social, biomedical, and technical systems. We found that similarly to undirected graphs, directed graphs in general also contain a large amount of redundancy, as measured by the size of their (directed) distance backbone. Our methodology adds an additional tool to the principled sparsification of complex networks and the measure of their robustness.
AB - In weighted graphs the shortest path between two nodes is often reached through an indirect path, out of all possible connections, leading to structural redundancies which play key roles in the dynamics and evolution of complex networks. We have previously developed a parameter-free, algebraically-principled methodology to uncover such redundancy and reveal the distance backbone of weighted graphs, which has been shown to be important in transmission dynamics, inference of important paths, and quantifying the robustness of networks. However, the method was developed for undirected graphs. Here we expand this methodology to weighted directed graphs and study the redundancy and robustness found in nine networks ranging from social, biomedical, and technical systems. We found that similarly to undirected graphs, directed graphs in general also contain a large amount of redundancy, as measured by the size of their (directed) distance backbone. Our methodology adds an additional tool to the principled sparsification of complex networks and the measure of their robustness.
KW - Directed networks
KW - Network backbones
KW - Redundancy
KW - Shortest path
KW - Sparsification
KW - Weighted graphs
UR - http://www.scopus.com/inward/record.url?scp=85149896456&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-21131-7_11
DO - 10.1007/978-3-031-21131-7_11
M3 - Conference contribution
C2 - 37916070
AN - SCOPUS:85149896456
SN - 9783031211300
SN - 9783031211331
VL - 2
T3 - Studies in Computational Intelligence
SP - 135
EP - 147
BT - Complex networks and their applications XI
A2 - Cherifi, Hocine
A2 - Mantegna, Rosario Nunzio
A2 - Rocha, Luis M.
A2 - Cherifi, Chantal
A2 - Micciche, Salvatore
PB - Springer Science and Business Media Deutschland GmbH
T2 - 11th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2022
Y2 - 8 November 2022 through 10 November 2022
ER -