Simas Tiago, Correia Rion Brattig, Rocha Luis M
Departamento de Engenharia Informtáica e Sistemas de Informação, Universidade Lusófona, Lisboa, Portugal.
Center for Social and Biomedical Complexity, Luddy School of Informatics, Computing & Engineering, Indiana University, Bloomington IN, USA, Instituto Gulbenkian de Ciência, Oeiras, Portugal and CAPES Foundation, Ministry of Education of Brazil, Brasília, DF, Brazil.
J Complex Netw. 2021 Dec;9(6). doi: 10.1093/comnet/cnab021. Epub 2021 Oct 20.
Redundancy needs more precise characterization as it is a major factor in the evolution and robustness of networks of multivariate interactions. We investigate the complexity of such interactions by inferring a connection transitivity that includes all possible measures of path length for weighted graphs. The result, without breaking the graph into smaller components, is a distance backbone subgraph sufficient to compute all shortest paths. This is important for understanding the dynamics of spread and communication phenomena in real-world networks. The general methodology we formally derive yields a principled graph reduction technique and provides a finer characterization of the triangular geometry of all edges-those that contribute to shortest paths and those that do not but are involved in other network phenomena. We demonstrate that the distance backbone is very small in large networks across domains ranging from air traffic to the human brain connectome, revealing that network robustness to attacks and failures seems to stem from surprisingly vast amounts of redundancy.
冗余需要更精确的描述，因为它是多变量相互作用网络的进化和稳健性的一个主要因素。我们通过推断一种连接传递性来研究这种相互作用的复杂性，这种传递性包括加权图中路径长度的所有可能度量。结果是，在不将图分解为较小组件的情况下，得到一个距离主干子图，足以计算所有最短路径。这对于理解现实世界网络中传播和通信现象的动态很重要。我们正式推导的一般方法产生了一种有原则的图约简技术，并对所有边的三角形几何结构进行了更精细的描述——那些对最短路径有贡献的边和那些没有贡献但参与其他网络现象的边。我们证明，在从空中交通到人类大脑连接组等跨领域的大型网络中，距离主干非常小，这表明网络对攻击和故障的稳健性似乎源于惊人数量的冗余。
