Network Connectivity Under a Probabilistic Node Failure Model
Lucia Cavallaro, Stefania Costantini, Pasquale De Meo, Antonio Liotta, Giovanni Stilo
Abstract
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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">probabilistic node failure model</i> , considering two variants: <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Uniform</i> nodes survival-to-failure probability; and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Best Connected</i> , 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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">effectiveness</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">coverage</i> , on eight real-world graphs. Specifically, the effectiveness is defined as the drop in the spectral radius <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\lambda _{1}$</tex-math></inline-formula> after node removal, while the coverage is understood as the reduction of the size of the largest connected component <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$c$</tex-math></inline-formula> of a graph. We find that the degree can generally be used to cause the biggest drop in both <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\lambda _{1}$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$c$</tex-math></inline-formula> , 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.