title: Decreasing the spectral radius of a graph by link removals.
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 (x(1))(i)(x(1))(j) of the components of the eigenvector x(1) 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.
authors.affiliation: Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands. P.F.A.VanMieghem@tudelft.nl
authors.forename: Piet
authors.initials: P
authors.lastname: Van Mieghem
authors.forename: Dragan
authors.initials: D
authors.lastname: Stevanović
authors.forename: Fernando
authors.initials: F
authors.lastname: Kuipers
authors.forename: Cong
authors.initials: C
authors.lastname: Li
authors.forename: Ruud
authors.initials: R
authors.lastname: van de Bovenkamp
authors.forename: Daijie
authors.initials: D
authors.lastname: Liu
authors.forename: Huijuan
authors.initials: H
authors.lastname: Wang
mesh_terms: D003196:Computer Graphics; D008962:Models, Theoretical