Decreasing the spectral radius of a graph by link removals

Piet Van Mieghem, Dragan Stevanović, Fernando Kuipers, Cong Li, Ruud van de Bovenkamp, Daijie Liu, and Huijuan Wang
Phys. Rev. E 84, 016101 – Published 6 July 2011

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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
4 More
  • Received 15 April 2011

DOI:https://doi.org/10.1103/PhysRevE.84.016101

©2011 American Physical Society

Authors & Affiliations

Piet Van Mieghem*, Dragan Stevanović, Fernando Kuipers, Cong Li, Ruud van de Bovenkamp, Daijie Liu, and Huijuan Wang

  • Delft University of Technology, Delft, The Netherlands

  • *Faculty of Electrical Engineering, Mathematics and Computer Science, P. O. Box 5031, NL-2600 GA Delft, The Netherlands; P.F.A.VanMieghem@tudelft.nl
  • Faculty of Mathematics, Natural Sciences and Information Technology, University of Primorska, Glagoljaska 8, 6000 Koper, Slovenia, and Faculty of Sciences and Mathematics, University of Nis, Visegradska 33, RS-18000 Nis, Serbia.

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 84, Iss. 1 — July 2011

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×