19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Eigenvector approach to spectral radius minimization

Presented by Prof. Dragan STEVANOVIC
Type: Oral presentation
Track: Graph Spectra and its Applications


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 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=ij$ with largest product $x_i x_j$ of the components of the eigenvector $x$ 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.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors