Search

The effective graph resistance, also known as the Kirchhoff index, is metric that is used to quantify the robustness of a network. We show that the optimisation problem of minimizing the effective graph resistance of a graph by adding a fixed number of links, is NP-hard.

In this paper, we propose closed-form analytical expressions to determine the minimum number of driver nodes that is needed to control a specific class of networks. We consider swarm signaling networks with regular out-degree distribution where a fraction $p$ of the links is unavailable. We further apply our method to networks with bi-modal out-degree distributions. Our approximations are validated through intensive simulations. Results show that our approximations have high accuracy when compared with simulation results for both types of out-degree distribution.

Apart from the role the clustering coefficient plays in the definition of the small-world phenomena, it also has great relevance for practical problems involving networked dynamical systems. To study the impact of the clustering coefficient on dynamical processes taking place on networks, some authors have focused on the construction of graphs with tunable clustering coefficients. These constructions are usually realized through a stochastic process, either by growing a network through the preferential attachment procedure, or by applying a random rewiring process. In contrast, we consider here several families of static graphs whose clustering coefficients can be determined explicitly. The basis for these families is formed by the $k$-regular graphs on $N$ nodes, that belong to the family of so-called circulant graphs denoted by $C_{N,k}$. We show that the expression for the clustering coefficient of $C_{N,k}$ reported in literature, only holds for sufficiently large $N$. Next, we consider three generalizations of the circulant graphs, either by adding some pendant links to $C_{N,k}$, or by connecting, in two different ways, an additional node to some nodes of $C_{N,k}$. For all three generalizations, we derive explicit expressions for the clustering coefficient. Finally, we construct a family of pairs of generalized circulant graphs, with the same number of nodes and links, but with different clustering coefficients.

Networks are often made up of several layers that exhibit diverse degrees of interdependencies. A multilayer interdependent network consists of a set of graphs $G$ that are interconnected through a weighted interconnection matrix $ B $, where the weight of each inter-graph 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 $, being $ I $ 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

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 network topological entities, and as such they possess measurable network properties. In this paper, by using network science and graph theoretical concepts, we investigate both theoretical and experimental robustness metrics (i.e., the robustness indicator, the effective graph conductance, and the critical thresholds) and their performance in quantifying the robustness of metro networks under random failures or targeted attacks. We find that the theoretical metrics quantify different aspects of the robustness of metro networks. In particular, the robustness indicator captures the number of alternative paths and the effective graph conductance focuses on the length of each path. Moreover, the high positive correlation between the theoretical metrics and experimental metrics and the negative correlation within the theoretical metrics provide significant insights for planners to design more robust system while accommodating for transit specificities (e.g., alternative paths, fast transferring)., Comment: 13 pages, 4 figures, conference

Cascading failures are one of the main reasons for blackouts in electrical power grids. Stable power supply requires a robust design of the power grid topology. Currently, the impact of the grid structure on the grid robustness is mainly assessed by purely topological metrics, that fail to capture the fundamental properties of the electrical power grids such as power flow allocation according to Kirchhoff's laws. This paper deploys the effective graph resistance as a metric to relate the topology of a grid to its robustness against cascading failures. Specifically, the effective graph resistance is deployed as a metric for network expansions (by means of transmission line additions) of an existing power grid. Four strategies based on network properties are investigated to optimize the effective graph resistance, accordingly to improve the robustness, of a given power grid at a low computational complexity. Experimental results suggest the existence of Braess's paradox in power grids: bringing an additional line into the system occasionally results in decrease of the grid robustness. This paper further investigates the impact of the topology on the Braess's paradox, and identifies specific sub-structures whose existence results in Braess's paradox. Careful assessment of the design and expansion choices of grid topologies incorporating the insights provided by this paper optimizes the robustness of a power grid, while avoiding the Braess's paradox in the system., Comment: 7 pages, 13 figures conference

Cascading failures are one of the main reasons for blackouts in electric power transmission grids. The economic cost of such failures is in the order of tens of billion dollars annually. The loading level of power system is a key aspect to determine the amount of the damage caused by cascading failures. Existing studies show that the blackout size exhibits phase transitions as the loading level increases. This paper investigates the impact of the topology of a power grid on phase transitions in its robustness. Three spectral graph metrics are considered: spectral radius, effective graph resistance and algebraic connectivity. Experimental results from a model of cascading failures in power grids on the IEEE power systems demonstrate the applicability of these metrics to design/optimize a power grid topology for an enhanced phase transition behavior of the system.

Cascading failures are the typical reasons of black- outs in power grids. The grid topology plays an important role in determining the dynamics of cascading failures in power grids. Measures for vulnerability analysis are crucial to assure a higher level of robustness of power grids. Metrics from Complex Networks are widely used to investigate the grid vulnerability. Yet, these purely topological metrics fail to capture the real behaviour of power grids. This paper proposes a metric, the effective graph resistance, as a vulnerability measure to de- termine the critical components in a power grid. Differently than the existing purely topological measures, the effective graph resistance accounts for the electrical properties of power grids such as power flow allocation according to Kirchoff laws. To demonstrate the applicability of the effective graph resistance, a quantitative vulnerability assessment of the IEEE 118 buses power system is performed. The simulation results verify the effectiveness of the effective graph resistance to identify the critical transmission lines in a power grid.

Cascading failures are one of the main reasons for blackouts in power transmission grids. The topology of a power grid, together with its operative state determine, for the most part, the robustness of the power grid against cascading failures. Secure electrical power supply requires, together with careful operation, a robust design of the electrical power grid topology. This paper investigates the impact of a power grid topology on its robustness against cascading failures. Currently, the impact of the topology on a grid robustness is mainly assessed by using purely topological approaches that fail to capture the essence of electric power flow. This paper proposes a metric, the effective graph resistance, that relates the topology of a power grid to its robustness against cascading failures by deliberate attacks, while also taking the fundamental characteristics of the electric power grid into account such as power flow allocation according to Kirchoff Laws. Experimental verification shows that the proposed metric anticipates the grid robustness accurately. The proposed metric is used to optimize a grid topology for a higher level of robustness. To demonstrate its applicability, the metric is applied on the IEEE 118 bus power system to improve its robustness against cascading failures.

Power grids vulnerability is a key issue in society. A component failure may trigger cascades of failures across the grid and lead to a large blackout. Complex network approaches have shown a direction to study some of the problems faced by power grids. Within Complex Network Analysis structural vulnerabilities of power grids have been studied mostly using purely topological approaches, which assumes that flow of power is dictated by shortest paths. However, this fails to capture the real flow characteristics of power grids. We have proposed a flow redistribution mechanism that closely mimics the flow in power grids using the PTDF. With this mechanism we enhance existing cascading failure models to study the vulnerability of power grids. We apply the model to the European high-voltage grid to carry out a comparative study for a number of centrality measures. `Centrality' gives an indication of the criticality of network components. Our model offers a way to find those centrality measures that give the best indication of node vulnerability in the context of power grids, by considering not only the network topology but also the power flowing through the network. In addition, we use the model to determine the spare capacity that is needed to make the grid robust to targeted attacks. We also show a brief comparison of the end results with other power grid systems to generalise the result., Comment: Pre-Proceedings of CRITIS '12