Name
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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/TNSE.2022.3164357 | IEEE Transactions on Network Science and Engineering |
Keywords | DocType | Volume |
Largest connected component,node centrality in networks,spectral radius | Journal | 9 |
Issue | ISSN | Citations |
4 | 2327-4697 | 0 |
PageRank | References | Authors |
0.34 | 30 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lucia Cavallaro | 1 | 0 | 0.34 |
| Stefania Costantini | 2 | 536 | 59.90 |
| Pasquale De Meo | 3 | 0 | 0.34 |
| Antonio Liotta | 4 | 837 | 90.10 |
| Giovanni Stilo | 5 | 0 | 0.34 |