Networks are often made up of several layers that exhibit diverse degrees of interdependencies. An interdependent network consists of a set of graphs G that are interconnected through a weighted interconnection matrix B, where the weight of each intergraph link is a non-negative real number p. Various dynamical processes, such as synchronization, cascading failures in power grids, and diffusion processes, are described by the Laplacian matrix Q characterizing the whole system. For the case in which the multilayer graph is a multiplex, where the number of nodes in each layer is the same and the interconnection matrix B=pI, I being the identity matrix, it has been shown that there exists a structural transition at some critical coupling p∗. This transition is such that dynamical processes are separated into two regimes: if p>p∗, the network acts as a whole; whereas when p<p∗, the network operates as if the graphs encoding the layers were isolated. In this paper, we extend and generalize the structural transition threshold p∗ to a regular interconnection matrix B (constant row and column sum). Specifically, we provide upper and lower bounds for the transition threshold p∗ in interdependent networks with a regular interconnection matrix B and derive the exact transition threshold for special scenarios using the formalism of quotient graphs. Additionally, we discuss the physical meaning of the transition threshold p∗ in terms of the minimum cut and show, through a counterexample, that the structural transition does not always exist. Our results are one step forward on the characterization of more realistic multilayer networks and might be relevant for systems that deviate from the topological constraints imposed by multiplex networks.

Network robustness plays a critical role in the proper functioning of modern society. It is common practice to use spectral metrics, to quantify the robustness of networks. In this paper we compare eight different spectral metrics that quantify network robustness. Four of the metrics are derived from the adjacency matrix, the others follow from the Laplacian spectrum. We found that the metrics can give inconsistent indications, when comparing the robustness of different synthetic networks. Then, we calculate and compare the spectral metrics for a number of real-world networks, where inconsistencies still occur, but to a lesser extent. Finally, we indicate how the concept of the R^∗-value, a weighted sum of robustness metrics, can be used to resolve the found inconsistencies.

Metros (heavy rail transit systems) are integral parts of urban transportation systems. Failures in their operations can have serious impacts on urban mobility, and measuring their robustness is therefore critical. Moreover, as physical networks, metros can be viewed as topological entities, and as such they possess measurable network properties. In this article, by using network science and graph theory, we investigate ten theoretical and four numerical robustness metrics and their performance in quantifying the robustness of 33 metro networks under random failures or targeted attacks. We find that the ten theoretical metrics capture two distinct aspects of robustness of metro networks. First, several metrics place an emphasis on alternative paths. Second, other metrics place an emphasis on the length of the paths. To account for all aspects, we standardize all ten indicators and plot them on radar diagrams to assess the overall robustness for metro networks. Overall, we find that Tokyo and Rome are the most robust networks. Rome benefits from short transferring and Tokyo has a significant number of transfer stations, both in the city center and in the peripheral area of the city, promoting both a higher number of alternative paths and overall relatively short path-lengths.

Kemeny's constant and its relation to the effective graph resistance has been established for regular graphs by Palacios et al. [1]. Based on the Moore–Penrose pseudo-inverse of the Laplacian matrix, we derive a new closed-form formula and deduce upper and lower bounds for the Kemeny constant. Furthermore, we generalize the relation between the Kemeny constant and the effective graph resistance for a general connected, undirected graph.