Decreasing the spectral radius of a graph by link removals

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 co...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. E, Statistical, nonlinear, and soft matter physics Statistical, nonlinear, and soft matter physics, 2011-07, Vol.84 (1 Pt 2), p.016101-016101, Article 016101
Main Authors: Van Mieghem, Piet, Stevanović, Dragan, Kuipers, Fernando, Li, Cong, van de Bovenkamp, Ruud, Liu, Daijie, Wang, Huijuan
Format: Article
Language:English
Subjects:
Computer Graphics
Models, Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1539-3755
1550-2376
DOI:10.1103/PhysRevE.84.016101