Application of semidefinite programming to maximize the spectral gap produced by node removal

Abstract

The smallest positive eigenvalue of the Laplacian of a network is called the spectral gap and characterizes various dynamics on networks. We propose mathematical programming methods to maximize the spectral gap of a given network by removing a fixed number of nodes. We formulate relaxed versions of the original problem using semidefinite programming and apply them to example networks.

arXiv comment1 figure. Short paper presented in CompleNet, Berlin, March 13-15 (2013)

References in corpus (3)

• Emergence of scaling in random networks
• Synchronization in complex networks
• Enhancing the spectral gap of networks by node removal