Bounding robustness in complex networks under topological changes through majorization techniques

Abstract

Measuring robustness is a fundamental task for analyzing the structure of complex networks. Indeed, several approaches to capture the robustness properties of a network have been proposed. In this paper we focus on spectral graph theory where robustness is measured by means of a graph invariant called Kirchhoff index, expressed in terms of eigenvalues of the Laplacian matrix associated to a graph. This graph metric is highly informative as a robustness indicator for several realworld networks that can be modeled as graphs. We discuss a methodology aimed at obtaining some new and tighter bounds of this graph invariant when links are added or removed. We take advantage of real analysis techniques, based on majorization theory and optimization of functions which preserve the majorization order (Schurconvex functions). Applications to simulated graphs show the effectiveness of our bounds, also in providing meaningful insights with respect to the results obtained in the literature.

References in corpus (16)

• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Evolution of networks
• Network robustness and fragility: Percolation on random graphs
• Characterization of complex networks: A survey of measurements
• Influence maximization in complex networks through optimal percolation
• A tool for filtering information in complex systems
• Dynamics of market correlations: Taxonomy and portfolio analysis
• Percolation Critical Exponents in Scale-Free Networks
• Network dismantling
• Generalized Network Dismantling
• Correlation based networks of equity returns sampled at different time horizons
• Optimization of Robustness of Complex Networks
• Fast and simple decycling and dismantling of networks
• Robustness and Closeness Centrality for Self-Organized and Planned Cities
• A majorization method for localizing graph topological indices

Cited by in corpus (2)

• Minimizing the effective graph resistance by adding links is NP-hard
• Assessing Systemic Risk in the Insurance Sector via Network Theory