Decreasing the spectral radius of a graph by link removals

Journal article (2011)
Department
Telecommunications (EEMCS) (TU Delft)
Copyright: American Physical Society
DOI: https://doi.org/doi:10.1103/PhysRevE.84.016101
More Info
expand_more

Published Date

06-07-2011

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Source:

Physical Review E, 84 (1), 2011

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Telecommunications

Abstract

The decrease of the spectral radius, an important characterizer of network dynamics, by removing links is investigated. The minimization of the spectral radius by removing m links is shown to be an NP-complete problem, which suggests considering heuristic strategies. Several greedy strategies are compared, and several bounds on the decrease of the spectral radius are derived. The strategy that removes that link l=i~j with largest product (x1)i(x1)j of the components of the eigenvector x1 belonging to the largest adjacency eigenvalue is shown to be superior to other strategies in most cases. Furthermore, a scaling law where the decrease in spectral radius is inversely proportional to the number of nodes N in the graph is deduced. Another sublinear scaling law of the decrease in spectral radius versus the number m of removed links is conjectured.