Enhancing the spectral gap of networks by node removal

Abstract

Dynamics on networks are often characterized by the second smallest eigenvalue of the Laplacian matrix of the network, which is called the spectral gap. Examples include the threshold coupling strength for synchronization and the relaxation time of a random walk. A large spectral gap is usually associated with high network performance, such as facilitated synchronization and rapid convergence. In this study, we seek to enhance the spectral gap of undirected and unweighted networks by removing nodes because, practically, the removal of nodes often costs less than the addition of nodes, addition of links, and rewiring of links. In particular, we develop a perturbative method to achieve this goal. The proposed method realizes better performance than other heuristic methods on various model and real networks. The spectral gap increases as we remove up to half the nodes in most of these networks.

5 figures

References in corpus (9)

• Synchronization in complex networks
• Cascade control and defense in complex networks
• Analysis of a power grid using the Kuramoto-like model
• Characterizing the dynamical importance of network nodes and links
• Synchronization is optimal in non-diagonalizable networks
• Maximum Performance at Minimum Cost in Network Synchronization
• Dynamical and spectral properties of complex networks
• Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that
• Bounding network spectra for network design