Network Connectivity Under a Probabilistic Node Failure Model

doi:10.1109/TNSE.2022.3164357

Network Connectivity Under a Probabilistic Node Failure Model

2022-07-01

5

OA

AI

DOI：10.1109/TNSE.2022.3164357

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Largest connected component

node centrality in networks

spectral radius

Network Connectivity Under a Probabilistic Node Failure Model

Abstract

Journal

Organization