Changing the ranking in eigenvector centrality of a weighted graph by small perturbations

In this article, we consider eigenvector centrality for the nodes of a graph and study the robustness (and stability) of this popular centrality measure. For a given weighted graph G (both directed and undirected), we consider the associated weighted adjacency matrix A, which by definition is a non-negative matrix. The eigenvector centralities of the nodes of G are the entries of the Perron eigenvector of A, which is the (positive) eigenvector associated with the eigenvalue with largest modulus. They provide a ranking of the nodes according to the corresponding centralities. An indicator of the robustness of eigenvector centrality consists in looking for a nearby perturbed graph G, with the same structure as G (i.e., with the same vertices and edges), but with a weighted adjacency matrix A such that the highest m entries (m >= 2) of the Perron eigenvector of A coalesce, making the ranking at the highest level ambiguous. To compute a solution to this matrix nearness problem, a nested iterative algorithm is proposed that makes use of a constrained gradient system of matrix differential equations in the inner iteration and a one-dimensional optimization of the perturbation size in the outer iteration. The proposed algorithm produces the optimal perturbation (i.e., the one with smallest Frobenius norm) of A which causes the looked-for coalescence, which is a measure of the sensitivity of the graph. As a by-product of our methodology we derive an explicit formula for the gradient of a suitable functional corresponding to the minimization problem, leading to a characterization of the stationary points of the associated gradient system. This in turn gives us important properties of the solutions, revealing an underlying low rank structure. Our numerical experiments indicate that the proposed strategy outperforms more standard approaches based on algorithms for constrained optimization. The methodology is formulated in terms of graphs but applies to any non-negative matrix, with potential applications in fields like population models, consensus dynamics, economics, etc.