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 (21)

• Emergence of scaling in random networks
• Error and attack tolerance of complex networks
• The large-scale organization of metabolic networks
• Synchronization in complex networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Self-similar community structure in organisations
• Universal Behavior of Load Distribution in Scale-free Networks
• Growing Scale-Free Networks with Tunable Clustering
• Cascade control and defense in complex networks
• Analysis of a power grid using the Kuramoto-like model
• Entangled networks, synchronization, and optimal network topology
• Characterizing the dynamical importance of network nodes and links
• Synchronization is optimal in non-diagonalizable networks
• Network synchronization landscape reveals compensatory structures, quantization, and the positive effect of negative interactions
• Maximum Performance at Minimum Cost in Network Synchronization
• Approximating Spectral Impact of Structural Perturbations in Large Networks
• Dynamical and spectral properties of complex networks
• Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that
• Immunization of networks with community structure
• Bounding network spectra for network design

Cited by in corpus (10)

• Opinion control in complex networks
• Does the brain behave like a (complex) network? I. Dynamics
• Origin and implications of zero degeneracy in networks spectra
• Sensitive Dependence of Optimal Network Dynamics on Network Structure
• Spectral Gap-Based Seismic Survey Design
• Spectral and Dynamic Consequences of Network Specialization
• Comparing the reliability of networks by spectral analysis
• Mechanisms for Network Growth that Preserve Spectral and Local Structure
• God ($\equiv Elohim$), the first small world network
• Application of semidefinite programming to maximize the spectral gap produced by node removal