Authors: Van Mieghem, Piet
Stevanović, Dragan 
Kuipers, Fernando
Li, Cong
Van De Bovenkamp, Ruud
Liu, Daijie
Wang, Huijuan
Title: Decreasing the spectral radius of a graph by link removals
Journal: Physical Review E - Statistical, Nonlinear, and Soft Matter Physics
Volume: 84
Issue: 1
Issue Date: 6-Jul-2011
Rank: M21a
ISSN: 1539-3755
DOI: 10.1103/PhysRevE.84.016101
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(x 1)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.
Publisher: American Physical Society

Show full item record


checked on Jun 15, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.