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.

@en

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.

@en

Interconnection between telecommunication networks and other critical infrastructures is usually established through nodes that are spatially close, generating a geographical interdependency. Previous work has shown that in general, geographically interdependent networks are more robust with respect to cascading failures when the interconnection radius (r) is large. However, to obtain a more realistic model, the allocation of interlinks in geographically interdependent networks should consider other factors. In this paper, an enhanced interconnection model for geographically interdependent networks is presented. The model proposed introduces a new strategy for interconnecting nodes between two geographical networks by limiting the number of interlinks. Results have shown that the model yields promising results to maintain an acceptable level in network robustness under cascading failures with a decrease in the number of interlinks.@en

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.

@en

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.

@en

Various real-world networks interact with and depend on each other. The design of the interconnection between interacting networks is one of the main challenges to achieve a robust interdependent network. Due to cost considerations, network providers are inclined to interconnect nodes that are geographically close. Accordingly, we propose two topologies, the random geographic graph and the relative neighborhood graph, for the design of interconnection in interdependent networks that incorporates the geographic location of nodes. Differing from the one-to-one interconnection studied in the literature, one node in one network can depend on an arbitrary number of nodes in the other network. We derive the average number of interdependent links for the two topologies, which enables their comparison. For the two topologies, we evaluate the impact of the interconnection structure on the robustness of interdependent networks against cascading failures. The two topologies are assessed on the real-world coupled Italian Internet and the electric transmission network. Finally, we propose the derivative of the largest mutually connected component with respect to the fraction of failed nodes as a robustness metric. This robustness metric quantifies the damage of the network introduced by a small fraction of initial failures well before the critical fraction of failures at which the whole network collapses.@en

Failures of networks, such as power outages in power systems, congestions in transportation networks, paralyse our daily life and introduce a tremendous cascading effect on our society. Networks should be constructed and operated in a robust way against random failures or deliberate attacks. We study how to add a single link into an existing network such that the robustness of the network is maximally improved among all the possibilities. A graph metric, the effective graph resistance, is employed to quantify the robustness of the network. Though exhaustive search guarantees the optimal solution, the computational complexity is high and is not scalable with the increase of network size. We propose strategies that take into account the structural and spectral properties of networks and indicate links whose addition result in a high robustness level.@en

Topological characteristics of links of complex networks influence the dynamical processes executed on networks triggered by links, such as cascading failures triggered by links in power grids and epidemic spread due to link infection. The line graph transforms links in the original graph into nodes. In this paper, we investigate how graph metrics in the original graph are mapped into those for its line graph. In particular, we study the degree distribution and the assortativity of a graph and its line graph. Specifically, we show, both analytically and numerically, the degree distribution of the line graph of an Erdős–Rényi graph follows the same distribution as its original graph. We derive a formula for the assortativity of line graphs and indicate that the assortativity of a line graph is not linearly related to its original graph. Additionally, line graphs of various graphs, e.g. Erdős–Rényi graphs, scale-free graphs, show positive assortativity. In contrast, we find certain types of trees and non-trees whose line graphs have negative assortativity.@en

The orthogonal eigenvector matrix Z of the Laplacian matrix of a graph with N nodes is studied rather than its companion X of the adjacency matrix, because for the Laplacian matrix, the eigenvector matrix Z corresponds to the adjacency companion X of a regular graph, whose properties are easier. In particular, the column sum vector of Z (which we call the fundamental weight vector w) is, for a connected graph, proportional to the basic vector e_N = (0, 0, . . . , 1), so that more information about the speclics of the graph is contained in the row sum of Z (which we call the dual fundamental weight vector φ). Since little is known about Z (or X), we have tried to understand simple properties of Z such as the number of zeros, the sum of elements, the maximum and minimum element and properties of φ. For the particular class of Erdos-Rényi random graphs, we found that a product of a Gaussian and a super-Gaussian distribution approximates accurately the distribution of Φ_U, a uniformly at random chosen component of the dual fundamental weight vector of Z.@en

DNSSEC offers protection against spoofing of DNS data by providing origin authentication, ensuring data integrity and authentication of non-existence by using public-key cryptography. Although the relevance of securing a technology as crucial to the Internet as DNS is obvious, the DNSSEC implementation increases the complexity of the deployed DNS infrastructure, which may result in misconfiguration. In this article, we measure and analyze the misconfigurations for domains in six zones (.bg, .br, .co, .com, .nl and .se). Furthermore, we categorize these misconfigurations and provide an explanation for their possible causes. Finally, we evaluate the effects of misconfigurations on the reachability of a zone’s network. Our results show that, although progress has been made in the implementation of DNSSEC, over 4 % of evaluated domains show misconfigurations. The domains with the most frequently appearing misconfiguration are often hosted at a very limited set of hosting providers. Of these misconfigured domains, almost 75 % were unreachable from a DNSSEC-aware resolver. This illustrates that although the authorities of a domain may think their DNS is secured, it is in fact not. Worse still, misconfigured domains are at risk of being unreachable from the clients who care about and implement DNSSEC verification, while the publisher may remain unaware of the error and its consequences.@en