Structural Vulnerability Analysis in Complex Networks Based on Core Theory

摘要

Recent studies show that the failures of just a few nodes or edges may disable the operation of the whole network, or even lead to the corruption of the entire system. For a given network and a ratio k, we aim to find out the set with the least number of vulnerable nodes whose removals reduce the connectivity of network structures (suppose to be m) to k*m. We introduce core theory to address this problem. Coritivity is an important measurement to assess the connectivity of network. It is capable of showing not only the difficulty to break down network but also how fragmental the network becomes. We demonstrate that the problem of finding core vertices is an NP-Hard problem. In this case, we propose an approximation algorithm to calculate coritivity of network. The most vulnerable nodes are selected by greedy methods from the set of core nodes found by the previous algorithm. We empirically test our approach on both synthetic and real-world datasets, the results confirm its efficacy compared to random method and three centrality-based algorithms.