## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# Navigability of interconnected networks under random failures

Edited* by H. Eugene Stanley, Boston University, Boston, MA, and approved April 28, 2014 (received for review September 30, 2013)

## 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.

## Abstract

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.

**N**etwork theory has been revealed to be a perfect instrument to model the structure of complex systems and the dynamical process in which they are involved. However, the classical approach does not take into account the possibility that agents can be networked in different ways, and with different intensity, on multiple layers simultaneously. As an example, in the case of social sciences the same user might choose to subscribe to two or more online social networks and to build different social relationships with different users on each social platform (e.g., LinkedIn for the network of professional contacts, Facebook for the network of friends, etc.). Another example is represented by transportation networks in a city: the network of bus stops, the first layer, is different from the tube network, the second layer, but people make use of both by combining paths to move from one place to another within the city. The cases where one vertex is not present in the full multiplex can be accounted for by including it as an isolated vertex in the layers where it is missing, without altering either topological or dynamical properties of the interconnected network.

The existence of such multiple connections on different layers invites a generalization of the theory of complex networks to cope with multilayer interconnected networked systems. More specifically, very recent studies focused on a particular type of multilayer network, the multiplex, where each agent participates in different layers simultaneously, like our previous example in the case of online social networks. Indeed, the actors (vertices) in every layer are the same and are indeed vectors of multiplex states that can self-interact, at variance with interdependent networks which are conceived as interconnected communities within a single, larger network (1, 2).

The emergent physics of dynamical processes on top of multiplex networks has still to be discovered and formalized. Recently, it has been shown that diffusion processes in multiplex can have an enhanced-diffusive behavior (3), meaning that the time scales associated with diffusion in the whole multiplex can be shorter than those associated with the individual layers. This phenomenon is strictly related to the particular setup of the multiplex, and has no counterpart in classical “monoplex” networks.

Moreover, it has been recently shown that any real-world interconnected system is potentially at risk for abrupt changes in its structure, which may manifest new dynamical properties (4). However, diffusion processes describe states of vertices in terms of continuous variables that can be differentiated, whereas real diffusive processes in networks are better represented by a finite number of discrete visits (e.g., communication in online social networks, people commuting in transportation networks, etc.). A natural way to represent these processes in physics, and in particular in networks, is by considering random walkers (5⇓⇓⇓⇓–10), whose exploration of the full networked system is akin to a diffusion process (11) and might help, for instance, to uncover community structures on multiple layers (12), to infer gene regulatory pathways (13), to identify genes associated with hereditary disorders in protein–protein interaction networks (14), or to model first-passage time in complex disordered media (15).

The implications of the study of random walks, however, go beyond the scope of physics, and are useful in other disciplines such as financial time series analysis (16), genetics (17, 18), evolution (19), social sciences (20), contagion processes (21⇓–23), and to rank websites in the world wide web by importance and quality (24), to cite a few.

Here we focus on this specific type of dynamical process on interconnected networks, i.e., random walks. We estimate analytically the coverage of multilayer interconnected networks for several types of random walks. This estimation allows us to quantify the differences in navigability, and its resilience to random failures, of multilayer networks with respect to the navigability of the individual layers.

At variance with other navigation problems in science and technology, only local information of network is required, i.e., any source vertex does not possess the knowledge of the entire topology. It has been shown that the design and development of optimal navigation can be achieved exploiting shortest paths, either with local knowledge and the presence of long-range connections in a lattice network (25) or by imposing cost constraints, regardless of the available (global or local) information (26). However, in the presence of random failures it is not possible to have real-time information about the subsequent congestion. Moreover, the catastrophic cascade of failures, which might follow because of the interdependence of transport systems (27), is likely to propagate along shortest paths affecting the vertices with highest betweenness (28). Random walks represent a good choice to overcome this problem, and a good proxy to the real scenario. The coverage of random walks is a rich concept of interest in many phenomena, from ecology to physics (29, 30), as it provides a quantitative measure of the territory explored by a diffusing particle. For instance, its generalization to the number of distinct sites visited by several agents randomly walking simultaneously allowed a range of important problems to be solved, as in mathematical ecology (31).

We illustrate an application to the real-world problem of traveling efficiently in a transportation network. In particular, we consider the public transport of London, where each layer corresponds to a different type of rail network, and we show how neglecting to account for the cost of switching between layers of a multiplex can lead to an underestimation or an overestimation of navigability and exploration performances, as well as to its resilience. We corroborate our findings by performing data-driven simulations, considering the empirical distribution of check-ins and check-outs in the transportation system and assuming passengers traveling along fastest paths connecting two stations. Moreover, we simulate real disruptions, according to “no service” status reported by the Transport for London system. We show that the resilience of the whole interconnected structure under random failures, quantified by assuming a random-walk strategy, successfully captures the resilience calculated using empirical data and fastest-path strategies, providing a good approximation to the real resilience. The overall results show quantifiable dependences between the dynamical process and the underlying topology that are of utmost importance in the design of searching–routing–exploring strategies in real interconnected networks.

## Results

### Modeling Multilayer Relationships of Networked Systems.

A multiplex network is a multilayer graph where vertices belong to several different layers (i.e., monoplex networks) simultaneously, and they are connected by means of a specific set of edges in each layer. The weighted intralayer connection between two vertices *i* and *j* in the layer *α* of the multiplex is indicated by

Because of the peculiar interconnected structure, it is possible to move from one layer to another one, provided that such layers are connected with each other. We show in Fig. 1 a representative example of a multiplex topology, where each layer is connected bidirectionally to the other layers. The interlayer connections among the layers present in the multiplex define a networked system at a macroscopic level. To account for this network of layers, representing a fundamental characteristic of the multiplex, we introduce here the matrix *α* to layer *β* for a walker placed in a vertex *i*.

Therefore, it is useful to distinguish between the strength *i* with respect to its connections with other vertices *α*, and the strength

### Navigation on an Interconnected Network.

At a microscopic level, we can reduce the problem of describing the walk dynamics between vertices and layers per time unit to the definition of four fundamental transition rules accounting for all possibilities. In fact, we have (*i*) *i* and in the same layer *α*; (*ii*) *α* while moving from vertex *i* to a vertex *iii*) *α* to layer *iv*) *i* to vertex *α* to layer *j* and in layer *β* at time *i*)–(*iv*) described above. We indicate with *N* components *α*, and we introduce the supravector **1** can be written in a more compact form as *SI Appendix*).

The structure of the random-walk equation is the same regardless of the transition rules adopted to describe any particular case of interest. See *SI Appendix* for further details about the navigation strategies considered in this study, the transition rules, and the occupation probability.

### Exploration Efficiency of an Interconnected Network.

In the following we will consider only multiplex networks with undirected intra- and interlayer connections. To quantify the efficiency of the random walk in exploring the multiplex network, we focus on the coverage *t*, regardless of the layer, assuming that walks started from any other vertex in the network. We find that a good approximation to the coverage (*Materials and Methods*) is given by*j*), the matrix **2** can be solved numerically to obtain the correct coverage at each time step. It is worth noting that Eq. **2** shows how the exploration of a multiplex network is influenced by different factors encoded in the matrix *Materials and Methods*). To validate our theoretical predictions, we consider different two-layer multiplex topologies, where each layer can be a Barabási–Albert (BA) network (32), an Erdős–Rényi (33) or a Watt–Strogatz graph (34). For each multiplex topology random-walk rules and interlayer weights are fixed, and from each vertex we simulate the propagation of 100 random walkers for **2** and **3**, for three different interconnected topologies. The theoretical curves approximate the simulations quite well, with small differences only for the case of BA + BA topology, the multiplex with highest heterogeneity among the shown scenarios. In *SI Appendix* we show additional representative examples demonstrating that the multiplex topology and the navigation strategy have an evident impact on the walk process, delaying or accelerating the exploration of the network with respect to a navigation in a monoplex random network. This is a genuine effect of the multilayer structure whose control might help to build multilayer structures or strategies enhancing or reducing the navigability of the network.

### Application to the Public Transport of London.

The study of the navigability performance on cities is a large area of study; see, for instance, refs. 35 and 36 and references therein. In particular, a recent study (37) presents a remarkable analysis of the path optimization processes behind the transportation facilities in a large city like London. In fact, with more than 10 million inhabitants, London requires an efficient transportation network allowing people to move easily and quickly through the city. Here, we assume a more abstract scenario to get insight about the fundamental interrelations between the dynamical process and the underlying topology of the transportation network in London. We consider three different layers of such a network, namely the tube, the overground, and the docklands light railway (see *Materials and Methods* for further detail about the dataset). Each station represents a vertex, whereas real connections between stations are considered as weighted links (see Fig. 3*I* for a schematic illustration). We also show the corresponding aggregate network, obtained by the weighted projection of the multiplex to a single-layer graph, where the information about the type of transport is lost (Fig. 3*II*). Only a few stations exist simultaneously on more than one transportation layer.

We capitalize on the presented theoretical framework to investigate the navigability resilience of interconnected networks to random failures, focusing on the particular case of the public transport of London. A failure here is considered as the inoperability of a station in a certain transportation layer (e.g., because of an accident, a traffic jam, or catastrophe). Such an event can happen randomly on the system and can affect one or more stations at the same time. A measure of the operability of the full system in response to unexpected failures can be inferred from the coverage of the respective networks after such events. This is what we call the navigability resilience. The resilience *ϕ* of random failures is defined by *ϕ* failures and the averages are calculated over several random realizations of the failures. The normalization guarantees a fair comparison between the resilience of the multiplex and the monoplex networks. When a vertex fails in a single transportation layer, it cannot be traversed by any path. However, if that vertex is part of an interconnected network it can still be reached on other layers. This intrinsic feature of multiplexes enhances the resilience of the system with respect to monoplexes, as shown in Fig. 4, *I* for the public transport of London. Eqs. **2** and **3** are used to predict the resilience obtained by extensive simulations, and results are reproduced with great accuracy.

To evaluate the resilience of the system in a more realistic scenario, we consider the empirical distribution of check-ins and check-outs in the public transport of London and we simulate passengers traveling along the shortest paths connecting two stations. We consider the adjacency matrices of each transportation system and we construct a weighted interconnected network where weights represent the cost to move between two connected stations. Here, the cost corresponds to the time required by an individual to travel along a connection, assuming that the involved modes of transport travel with an average speed of 33 km/h (38). Because the commutation time is not available, we assume it corresponds, on average, to the time an individual requires to walk 500 m with an average speed of 5 km/h. For each “shortest-path” walker, the starting and ending stations are sampled according to the data. When a destination is reached we consider it as a new starting station and a new target is sampled, iterating this procedure for 1 mo. As for the random-walk strategy, the coverage is given by the fraction of stations visited over time. In the case of random failures, the cost matrix is recalculated “on the fly” to simulate the behavior of individuals more realistically. We show in Fig. 4, *II* the resilience obtained in this case, in agreement with the estimation obtained assuming random-walk-based strategies. Our results show that resilience based on random-walk navigation provides an approximation to the empirical one.

For the sake of completeness, see *SI Appendix* for the topological resilience corresponding to the same multiplex, defined by the average fraction of vertices surviving in the giant connected component after random failures. The navigability, i.e., the dynamical resilience, is inherently smaller than the topological resilience of this multiplex network.

We also report the numerical resilience, and its theoretical expectation, in the case of real disruptions affecting the transportation network of London (Table 1 and *SI Appendix*). Our predictions are in excellent agreement with numerical simulations and, in the case of more realistic simulation, they always provide a good approximation of empirical resilience.

## Discussion

Our world is inherently networked and actors coexist in several different levels of relationships. People interacting during financial transactions and in real (or virtual) social systems, goods moving from one location to another by means of different modes of transport (e.g., air, rail, and road), and information flowing through different media (e.g., radio, satellite, and internet) represent important multilayer systems. Recently, progress has been made to include such levels in network analysis within the more general framework of interconnected networks (12, 39), accounting for the influence of their topologies and their interconnections to dynamical processes taking place on the networked system (3, 4). The lack of a systematic theory of random walkers on multilayer systems and their crucial role in the description of a wide variety of real-world systems, as resilience to random failures, has motivated our study. More specifically, we have investigated the behavior of different walks on interconnected networks and characterized their main statistical properties. We have identified in the coverage a suitable proxy for the exploration efficiency of the network, providing an accurate theoretical and analytical description. Our results have shown how the exploration of a multiplex is influenced by different factors. On one hand, the topological structure of each layer and the strength of interlayer connections determine the “topological reachability” of vertices, where more peripherals agents are more difficult to be visited because of their poorly influential position in the network. On the other hand, the exploration strategy defined by random-walk transition rules determine the “dynamical reachability” of vertices, where agents are more difficult to be visited because their position in the network is not privileged with respect to the flow of information. All such factors critically determine the time scale to cover the network.

To show the potential of the developed framework, we have considered an application to the public transport of London, focusing on three different transportation layers, i.e., tube, overground, and docklands light railway. We have investigated the resilience of this interconnected transport network to random failures, a study of importance to design and protect critical infrastructures. We have shown, theoretically and by means of extensive simulations, how the whole system is more resilient to random failures than its individual layers separately. Indeed, interconnected networks introduce additional dimensions that can help to find paths from apparently isolated parts of single layers, enhancing the resilience to random failures, and we provide a way to quantify this.

The results can be used to design optimal searching strategies (in the line of the findings in ref. 40), for instance, to characterize the cyclic structure of the multiplex (41), to infer gene regulatory pathways (13), to coarse grain the network structure (42), to assess the PageRank in these topologies (43), or to identify genes associated with hereditary disorders in protein–protein interaction networks (14), providing a step for further development of searching and navigability strategies in real interconnected systems.

## Materials and Methods

### Derivation of the Coverage: Transition Matrix.

To quantify the efficiency of the random walk in exploring the multiplex network, we focus on the coverage *t*, regardless of the layer, assuming that walks started from any other vertex in the network.

Let *i* at time *t* regardless of the layer. We introduce the supravector *i*th canonical vector, to obtain *i* after *t* time steps, assumed that it started in vertex *j*, is given by

The solution of Eq. **4** is given by

where *j* and in the first layer, without loss of generality. The matrix *i* and the probability of not finding it in the same vertex must be zero) and 1 otherwise. Therefore, a good approximation to the coverage is given by double averaging over all vertices the probability **2**, which can be solved numerically to obtain the correct coverage at each time step.

### Derivation of the Coverage: Eigendecomposition.

The time evolution of the supravector of probabilities **P** for a walker starting from vertex *j* is also given by

where each supramatrix **4** for the dynamical evolution of

where **2**, is given by

After enough time, i.e., **3**. Note that for normalized supra-Laplacian matrices with more than one null eigenvalue, the more general version of Eq. **3** is given by

where

### Overview of the Dataset.

The list of tube, overground, and docklands light railway (DLR) stations, their positions, and their coordinates have been obtained from publicly available information in the official website dedicated to the transport of London (44) and in Wikipedia (www.wikipedia.org). The total number of stations is 369, among which there are 271 vertices with 312 connections considering all lines of the tube, 83 vertices with 83 connections in the overground, and 45 vertices with 46 connections in the DLR layer. Connections are undirected and weighted, where, in the case of the tube, the weight is given by the number of different underground lines connecting two stations. Check-ins and check-outs have been obtained from a 5% sample of all Oyster card journeys performed in a week during November 2009 on bus, tube, DLR, and London overground, available from ref. 44. The empirical distributions adopted in our simulations refer to the probability of observing a check-out in a certain station conditional to the probability that a passenger started his or her journey in another one. For details about the collection of data concerning the “no service” status in this transportation network, see *SI Appendix*.

## Acknowledgments

The authors acknowledge Mason A. Porter and H. Rozenfeld for valuable suggestions and useful comments. This work has been supported by Ministerio de Economía y Competitividad through Grant FIS2012-38266; European Comission FET-Proactive Projects PLEXMATH (Grant 317614) and MULTIPLEX (317532), and the Generalitat de Catalunya 2009-SGR-838. A.A. also acknowledges partial financial support from the ICREA Academia and the James S. McDonnell Foundation.

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. E-mail: alexandre.arenas{at}urv.cat.

Author contributions: M.D.D., A.S.-R., S.G., and A.A. designed research, performed research, contributed new reagents/analytic tools, analyzed data, and wrote the paper.

The authors declare no conflict of interest.

↵*This Direct Submission article had a prearranged editor.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1318469111/-/DCSupplemental.

## References

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- Mucha PJ,
- Richardson T,
- Macon K,
- Porter MA,
- Onnela JP

- ↵
- Tu Z,
- Wang L,
- Arbeitman MN,
- Chen T,
- Sun F

- ↵
- ↵
- ↵
- Stanley HE,
- et al.

- ↵
- ↵
- ↵
- van Nimwegen E,
- Crutchfield JP,
- Huynen M

- ↵
- ↵
- Daley D,
- Kendall DG

- ↵
- Daniels H

*Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability*(Univ of California Press, Berkeley, CA), Vol 4, pp 281–293. - ↵
- Maki DP,
- Thompson M

- ↵
- Brin S,
- Page L

*Computer Networks and ISDN Systems*30:107-117. - ↵
- ↵
- ↵
- ↵
- ↵
- Skellam JG

- ↵
- ↵
- ↵
- Barabási AL,
- Albert R

- ↵
- Erdős P,
- Rényi A

- ↵
- ↵
- ↵
- ↵
- Yeung CH,
- Saad D,
- Wong KY

- ↵London Councils (2013) Transport for London: Key facts. Available at http://www.londoncouncils.gov.uk/londonfacts/default.htm?category=12. Accessed January 2013.
- ↵
- Szell M,
- Lambiotte R,
- Thurner S

- ↵
- ↵
- ↵
- ↵
- Fortunato S,
- Boguñá M,
- Flammini A,
- Menczer F

- ↵London Councils (2010) Transport for London. Available at www.tfl.gov.uk/. Accessed August 1, 2010.

## Citation Manager Formats

## Sign up for Article Alerts

## Article Classifications

- Physical Sciences
- Applied Physical Sciences