Navigability of interconnected networks under random failures

By Manlio De Domenico, Albert Solé-Ribalta, Sergio Gómez, Alex Arenas. 2013

427 citations recorded by the source corpus.

Significance Network theory has been exploited in the last decades to deepen our comprehension of complex systems. However, real-world complex systems exhibit multiple levels of relationships and require modeling by interconnected networks, characterizing interactions on several levels simultaneously. Questions such as “what is the efficiency of exploration of a city using the multiple transportation layers, like subway and bus?” and “what is its resilience to failures?” have to be answered using the multiplex framework. Here, we introduce fundamental mechanisms to perform such exploration, using random walks on multilayer networks, and we show how the topological structure, together with the navigation strategy, influences the efficiency in exploring the whole structure. Assessing the navigability of interconnected networks (transporting information, people, or goods) under eventual random failures is of utmost importance to design and protect critical infrastructures. Random walks are a good proxy to determine this navigability, specifically the coverage time of random walks, which is a measure of the dynamical functionality of the network. Here, we introduce the theoretical tools required to describe random walks in interconnected networks accounting for structure and dynamics inherent to real systems. We develop an analytical approach for the covering time of random walks in interconnected networks and compare it with extensive Monte Carlo simulations. Generally speaking, interconnected networks are more resilient to random failures than their individual layers per se, and we are able to quantify this effect. As an application––which we illustrate by considering the public transport of London––we show how the efficiency in exploring the multiplex critically depends on layers’ topology, interconnection strengths, and walk strategy. Our findings are corroborated by data-driven simulations, where the empirical distribution of check-ins and checks-out is considered and passengers travel along fastest paths in a network affected by real disruptions. These findings are fundamental for further development of searching and navigability strategies in real interconnected systems.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Ranking in interconnected multilayer networks reveals versatile nodes (2013, background): “5, a random walk on a multilayer network induces nontrivial effects because the presence of inter-layer connections affects its navigation of a networked system [36].”
Human mobility: Models and applications (2017, background): “This leads to new features such as congestion [209], change in the navigability of the network subject to disruptions [210,211], produces new dynamic regimes that are absent in monolayers [212] and abrupt reactions to minimal topological changes [213].”
Multilayer Analysis and Visualization of Networks (2014, background): “For example, there have been numerous studies to attempt to understand how interdependencies [47,48], other multilayer structures [44–46,49–53], dynamics [54–58] and control [59] can improve understanding of complex interacting systems.”
Random walks and diffusion on networks (2016, methodology): “By considering RWs on multilayer and temporal networks, one can also generalize such notions of centrality [240, 251, 280–285].”
Multilayer networks (2013, methodology): “‘super-adjacency matrices’) [69,136,137], which have the advantage over tensors of being able to represent missing nodes in a convenient way.”