Logo NGI
nl
en
Zoeken

infrabase >

publicaties >

decreasing the spectral radius of a graph by link removals

 
Titel
Decreasing the spectral radius of a graph by link removals
Type
artikel vakblad
Referentie

Van Mieghem Piet; Dragan Stevanovicy; Fernando Kuipers; Cong Li; Ruud van de Bovenkamp; Daijie Liu and Huijuan Wang: Decreasing the spectral radius of a graph by link removals, pp. 1-24. In: Physical Review E, vol. 84, no. 1, July 2011.

Auteurs
Fernando Kuipers
 
Dajie Liu
 
Piet van Mieghem
Document
Beschrijving

The decrease of the spectral radius, an important characterizer of network dynamics, by remov- ing links is investigated. The minimization of the spectral radius by removing m links is shown to be an NP-complete problem, which suggests to consider 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 in- versely 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.

Projecten
Robustness and Optimization of Complex Networks

Logo NGI

Bouwcampus
Van der Burghweg 1
2628 CS Delft
secretariaat@nginfra.nl
telefoon: 015 303 0900

© 2016 Next Generation Infrastructures