Network Fragility: Dual Graph Insights into Link and Node Removal Using Effective Resistance

In this paper, we focus on network robustness in complex networks by identifying those links within a network graph G whose attack/removal would cause a severe network damage. More specifically, we investigate the role of the effective resistance matrix in identifying an order of links more vulnerable to attacks. In our previous works, we have both evaluated a strategy of link removals based on the ranking provided by the Hadamard product matrix between the adjacency matrix of G and the effective resistance matrix, and a strategy of node removals based on the ranking of the diagonal elements of the pseudoinverse of the Laplacian matrix associated to G. Now, through a real-world networking scenario of an Internet backbone, we start considering the line graph L(G) of G (i.e. the dual graph in which the links of G are nodes). Then, we investigate if removing nodes in the line graph is the same as removing links in G. The relation between the Laplacian of the line graph and the graph itself is not obvious, which does not allow us to immediately map the performance of a node removal strategy to the performance of a link removal strategy. Carrying out our analysis on Erdős-Rényi, Watts-Strogatz and Bárabasi-Albert networks, we look for a relation, if existing, between (a) the node removal in the line graph of G and (b) the link removal in G. Results show that the two attack strategies show a notable degree of similarity mostly on the Bárabasi-Albert networks.