Analysis on the Effects of Graph Perturbations on Centrality Metrics

Graph robustness upon node failures state-of-art is huge. However, not enough is known on the effects of centrality metrics ranking after graph perturbations. To fill this gap, our aim is to quantify how much small graph perturbations will affect the centrality metrics. Thus, we considered two type of probabilistic failure models (i.e., Uniform and Best Connected), a fraction tau of nodes under attack, with 0 < tau <= 1, and three popular centrality metrics (i.e., Degree, the Eigenvector and the Katz centrality). We discovered that in the Uniform model the amount of change in the adjacency matrix due to a perturbation is not significantly affected when tau is small even with a quite high failure probability (i.e., p <= 85%) and that the Eigenvector centrality is the most susceptible metric to deformation respect to the others herein analysed; whereas, in the Best Connected model, the amount of perturbation is proportional to tau.