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

$\lambda _{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

$\lambda _{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.

	Year	Citations

About