Approximating Spectral Impact of Structural Perturbations in Large Networks

Abstract

Determining the effect of structural perturbations on the eigenvalue spectra of networks is an important problem because the spectra characterize not only their topological structures, but also their dynamical behavior, such as synchronization and cascading processes on networks. Here we develop a theory for estimating the change of the largest eigenvalue of the adjacency matrix or the extreme eigenvalues of the graph Laplacian when small but arbitrary set of links are added or removed from the network. We demonstrate the effectiveness of our approximation schemes using both real and artificial networks, showing in particular that we can accurately obtain the spectral ranking of small subgraphs. We also propose a local iterative scheme which computes the relative ranking of a subgraph using only the connectivity information of its neighbors within a few links. Our results may not only contribute to our theoretical understanding of dynamical processes on networks, but also lead to practical applications in ranking subgraphs of real complex networks.

9 pages, 3 figures, 2 tables

References in corpus (8)

• Critical phenomena in complex networks
• Characterizing the dynamical importance of network nodes and links
• Synchronization is optimal in non-diagonalizable networks
• Master Stability Functions for Coupled Near-Identical Dynamical Systems
• Maximum Performance at Minimum Cost in Network Synchronization
• Predicting synthetic rescues in metabolic networks
• Dynamic Computation of Network Statistics via Updating Schema
• Sequence Nets

Cited by in corpus (26)

• Contact-based Social Contagion in Multiplex Networks
• Network synchronization landscape reveals compensatory structures, quantization, and the positive effect of negative interactions
• Graph Vulnerability and Robustness: A Survey
• Opinion control in complex networks
• Eigenvector localization in real networks and its implications for epidemic spreading
• Enhancing the spectral gap of networks by node removal
• Optimal interlayer structure for promoting spreading of SIS model in two-layer networks
• Synchronization of heterogeneous oscillators under network modifications: Perturbation and optimization of the synchrony alignment function
• Tune the topology to create or destroy patterns
• Spreading of Memes on Multiplex Networks
• Network connectivity during mergers and growth: optimizing the addition of a module
• Sensitive Dependence of Optimal Network Dynamics on Network Structure
• Perron communicability and sensitivity of multilayer networks
• Measuring nodes centrality when local and global measures overlap
• Social Climber attachment in forming networks produces phase transition in a measure of connectivity
• State-dependent effective interactions in oscillator networks through coupling functions with dead zones
• A network-specific approach to percolation in networks with bidirectional links
• Layer degradation triggers an abrupt structural transition in multiplex networks
• Seidel switching for weighted multi-digraphs and its quantum perspective
• Active Cyber Defense Dynamics Exhibiting Rich Phenomena
• Improving J-divergence of brain connectivity states by graph Laplacian denoising
• Maximizing the Smallest Eigenvalue of Grounded Laplacian Matrix
• Cycle-Star Motifs: Network Response to Link Modifications
• Optimization of convergence rate via algebraic connectivity
• Effective edge-based approach for promoting the spreading of SIR model
• Spectral Gradient Iterative Edge Attack for Synchronization Suppression in Complex Networks