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 checksout 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 Significance Network theory has been exploited in the last decades to deepen our comprehension of complex systems. However, realworld 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. 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. 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 W ðαÞ ij , where we use Latin letters to indicate vertices ði; j = 1; 2; . . . ; NÞ and Greek letters for indices indicating layers ðα = 1; 2; . . . ; LÞ. 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 D αβ ðiÞ to quantify the cost to switch from layer α to layer β for a walker placed in a vertex i. Therefore, it is useful to distinguish between the strength of a vertex i with respect to its connections with other vertices j ð j = 1; 2; . . . ; NÞ in the same layer α, and the strength S i;α = P β D αβ ðiÞ of the same vertex with respect to connections to its counterparts in different layers. For the sake of simplicity, in the following we consider that the cost to switch between any pair of layers is D αβ ðiÞ = D X for all vertices. 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) P αα ii , the probability of staying for one time step in the same vertex i and in the same layer α; (ii) P αα ij , the probability of staying in the same layer α while moving from vertex i to a vertex j ≠ i in its neighborhood; (iii) P αβ ii , the probability of staying in the same vertex while switching to its counterpart from layer α to layer β ≠ α; (iv) P αβ ij , the probability of moving from vertex i to vertex j ≠ i while switching from layer α to layer β ≠ α, in the same time step. Within such prescriptions, the master equation describing the probability of finding the walker in vertex j and in layer β at time t + Δt is given by where the terms account for transitions (i)-(iv) described above. We indicate with p α the row vector with N components p i;α with respect to layer α, and we introduce the supravector P ≡ ðp 1 ; p 2 ; . . . ; p L Þ with NL components. Moreover, in the special case with Δt = 1 we have _ PðtÞ = Pðt + 1Þ − PðtÞ. Therefore, Eq. 1 can be written in a more compact form as _ PðtÞ = −PðtÞL, hereafter referred to as the random-walker equation. In this equation, L is the NL × NL normalized supra-Laplacian matrix, whose structure is similar, although not identical, to the supra-Laplacian matrix recently proposed in ref. 3 to model the diffusion process in a multiplex network (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 Fig. 1 . Example of the navigation on an interconnected network. Path (dotted red line) of a random walker exploiting the multiplex topology to find a way around to jump between disconnected components. In this example the walker is not allowed to switch between layer 1 and layer 3 in one time step. 2 of 6 | www.pnas.org/cgi/doi/10.1073/pnas.1318469111 De Domenico et al. intra-and interlayer connections. To quantify the efficiency of the random walk in exploring the multiplex network, we focus on the coverage ρðtÞ, defined as the average fraction of distinct vertices visited at least once in a time less than or equal to 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 where P j ð0Þ indicates the supravector of probabilities at time t = 0 (assuming that the walker started in vertex j), the matrix P accounts for the probability to reach each vertex through any path of length 1; 2; . . . or t + 1, and E † i is a supracanonical vector allowing one to compact the notation. Eq. 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 P, i.e., the topological structure of each layer, the strength of interlayer connections, and the exploration strategy defined by random-walk transition rules. All these factors critically determine the time scale to cover the network. From the eigendecomposition of the supra-Laplacian, the alternative representation can be obtained (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} os-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 10 4 time steps. Therefore, we estimate the average fraction of visited vertices from the random-walk ensemble as a function of time. In Fig. 2 we show the comparison between the coverage obtained from detailed Monte Carlo simulations and the predictions given by Eqs. 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. 3I 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. 3II) . 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 rðϕÞ of the system to a fraction ϕ of random failures is defined by rðϕÞ = hρ ϕ ðτÞi=ρ 0 ðτÞ, where ρ ϕ ðtÞ is the coverage at time t of the network Fig. 2. Theoretical description of the navigability of a multiplex against simulation. Coverage versus time obtained from Monte Carlo simulations and our theoretical predictions given by Eqs. 2 and 3. A two-layer multiplex with D X = D 11 = D 22 = 1 is considered. Fig. 3. Multilayer network of public transport of London. (I) Tube, overground, and DLR define three layers of the multiplex transportation network. Each station, individuated by a geographical position, represents a vertex, whereas the existence of a real connection between two stations defines the presence of an edge. (II) Aggregate network corresponding to the weighted projection of the multiplex to a single-layer graph, where the information about the type of transport is lost. De Domenico et al. PNAS Early Edition | 3 of 6 APPLIED PHYSICAL SCIENCES subjected to ϕ 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. 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 Fig. 4. Resilience of the public transport network of London to random failures. (I) Theoretical expectations (solid lines) reproduce with great accuracy the resilience (points) obtained from simulations for each transportation layer and the whole interconnected system ðD X = 10 −1 Þ, assuming random-walk-based navigation. (II) The same as I but assuming shortestpath-based navigation and empirical data. Table 1. Real disruptions in London transportation network Line From To Freq., % Affected, % Theory, % RW, % SP, % DLR Beckton Canningtown 2.56 2.44 94.41 93.10 94.85 Piccadilly Actontown Arnosgrove 0.04 6.77 88.49 86.51 90.85 Northern Highbarnet Stockwell 0.08 5.96 86.11 82.55 84.49 Northern Charingcross Highbarnet 0.25 4.61 90.67 87.99 91.32 Representative partial line disruptions "From"-"To" stations are considered. The rate of occurrence "Freq." is reported together with the fraction of stations indirectly "Affected." The resilience obtained from Monte Carlo simulations (random walk, RW, and shortest-path, SP) are reported together with our theoretical expectation. See full table in SI Appendix. 4 of 6 | www.pnas.org/cgi/doi/10.1073/pnas.1318469111 De Domenico et al. 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. 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Þ, defined as the average fraction of distinct vertices visited at least once in a time less than or equal to t, regardless of the layer, assuming that walks started from any other vertex in the network. Let p i ðtÞ = P α p i,α ðtÞ be the probability to find the walker in vertex i at time t regardless of the layer. We introduce the supravector E i ≡ ðe i ,e i , . . . ,e i Þ, e i being the ith canonical vector, to obtain p i ðt + 1Þ = PðtÞPE † i . The probability to not find the walker in vertex i after t time steps, assumed that it started in vertex j, is given by δ i,j ðtÞ = ∐ t τ=1 ½1 − p i ðt − τÞ½1 − p j ð0Þ. Moreover, the recursive equation δ i ðt + 1Þ = δ i ðtÞ½1 − p i ðt + 1Þ leads to _ δ i,j ðtÞ = −δ i,j ðtÞPðtÞPE † i : [4] The solution of Eq. 4 is given by where P j ð0Þ ≡ ðe j ,0, . . . ,0Þ explicitly indicates that at time t = 0 the walker started in vertex j and in the first layer, without loss of generality. The matrix P has a clear meaning: it accounts for the probability to reach each vertex through any walk of length 1,2, . . . or t + 1. Moreover, δ i,j ð0Þ = 0 for j = i (i.e., the random walker starts in vertex 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 1 − δ i,j ðtÞ, obtaining Eq. 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 PðtÞ = P j ð0Þe −Lt , L being the normalized supra-Laplacian matrix. From eigendecomposition of the normalized supra-Laplacian, we obtain where each supramatrix V ℓ is obtained from products of eigenvectors. By substituting this expression into Eq. 4 for the dynamical evolution of δ i,j ðtÞ, we obtain _ δ i,j ðtÞ δ i,j ðtÞ = − X NL ℓ=1 e −λℓ t C i,j ðℓÞ, where C i,j ðℓÞ = P j ð0ÞV ℓ PE † i are constants depending on the vertex, the transition matrix, the eigendecomposition, and the initial conditions. Let us recall that the coverage is defined by double averaging the probability 1 − δ i,j ðtÞ over all vertices. Hence, another expression for the coverage versus time, alternative to Eq. 2, is given by After enough time, i.e., λ 2 t 1, the sum in the above exponentials is dominated by the term with ℓ = 2 and, additionally, e −λ2 t 1, leading to Eq. 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 Λ 0 and Λ + indicate the sets of all null and positive eigenvalues of the normalized supra-Laplacian, respectively.
Their stochastic model relates to De Domenico et al.'s model of random walks on multiplex structures REF .
Navigability of interconnected networks under random failures
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Computer Science Medicine