Bounding robustness in complex networks under topological changes through majorization techniques
- PDF / 1,433,004 Bytes
- 12 Pages / 595.276 x 785.197 pts Page_size
- 94 Downloads / 130 Views
THE EUROPEAN PHYSICAL JOURNAL B
Regular Article
Bounding robustness in complex networks under topological changes through majorization techniques Gian Paolo Clemente and Alessandra Cornaro a Department of Mathematics for Economic, Financial and Actuarial Sciences Universit´ a Cattolica del Sacro Cuore, Milano, Italy
Received 19 November 2019 Published online 17 June 2020 c EDP Sciences / Societ`
a Italiana di Fisica / Springer-Verlag GmbH Germany, part of Springer Nature, 2020 Abstract. Measuring robustness is a fundamental task for analysing 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 real-world 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. Applications to simulated graphs and to empirical networks generated by collecting assets of the S&P 100 show the effectiveness of our bounds, also in providing meaningful insights with respect to the results obtained in the literature.
1 Introduction Assessing and improving robustness of complex networks is a challenge that has gained increasing attention in the literature. Network robustness research has indeed been carried out by scientists with different backgrounds. As a result, quite a lot of different approaches have been undertaken to capture the robustness properties of a network (see, for example, [1–3]). Traditionally, the concept of robustness was mainly centred on graph connectivity. Recently, a more contemporary definition has been developed. According to [4], it is defined as the ability of a network to maintain its total throughput under node and link removal. Furthermore, by removing or deactivating a specific set of nodes, a network structure can be dismantled into isolated subcomponents, thereby disrupting the malfunctioning of a system or containing the spread of misinformation or an epidemic (see, e.g., [5–9]). In this framework several robustness metrics based on network topology or spectral graph theory have been proposed (see [10–12]). In particular, we focus on spectral graph theory where robustness is measured by means of functions of eigenvalues of the Laplacian matrix associated to a graph (see [13,14]). Indeed, this paper is aimed to the inspection of a graph measure called effective graph resistance, also known as Kirchhoff index (or resistance distance), derived from the field of electric a
e-mail: [email protected]
circuit analysis [15]. The Kirchhoff index has undergone intense scrutiny in rec
Data Loading...
