  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.
