Print Email Facebook Twitter Decreasing the spectral radius of a graph by link removals Title Decreasing the spectral radius of a graph by link removals Author Van Mieghem, P. Stevanovi?, D. Kuipers, F. Li, C. Van de Bovenkamp, R. Liu, D. Wang, H. Faculty Electrical Engineering, Mathematics and Computer Science Department Telecommunications Date 2011-07-06 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. To reference this document use: http://resolver.tudelft.nl/uuid:46dedfa7-d6e7-4f29-88f7-a7ea0a8b87d1 DOI https://doi.org/10.1103/PhysRevE.84.016101 Publisher American Physical Society ISSN 1539-3755 Source http://link.aps.org/doi/10.1103/PhysRevE.84.016101 Source Physical Review E, 84 (1), 2011 Part of collection Institutional Repository Document type journal article Rights © 2011 The Author(s)American Physical Society Files PDF VanMieghem_2011.pdf 782.1 KB Close viewer /islandora/object/uuid:46dedfa7-d6e7-4f29-88f7-a7ea0a8b87d1/datastream/OBJ/view