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
$\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.