Network Connectivity Under a Probabilistic Node Failure Model

Node-removal processes are generally used to test network robustness against failures, to verify the strength of a power grid, or to contain fake news. Yet, a node-removal task is typically assumed to be always successful; we argue that this is unrealistic, and that the node strengths should also be considered to better accommodate network failure scenarios. We propose a probabilistic node failure model, considering two variants: Uniform nodes survival-to-failure probability; and Best Connected, i.e., survival probability proportional to node degree. Our evaluation considers five popular centrality metrics (degree, h-index, coreness, Eigenvector, Katz centrality), performing an experimental analysis on effectiveness and coverage, on eight real-world graphs. Specifically, the effectiveness is defined as the drop in the spectral radius λ1 after node removal, while the coverage is understood as the reduction of the size of the largest connected component c of a graph. We find that the degree can generally be used to cause the biggest drop in both λ1 and c, especially in graphs deriving from human interactions/collaborations. Comparing with conventional methods, our probabilistic model exhibits significant differences (ranging from 0% to 83%), highlighting the benefits of the proposed method.