TY - JOUR
T1 - Bounding robustness in complex networks under topological changes through majorization techniques
AU - Clemente, Gian Paolo
AU - Cornaro, Alessandra
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Statistical and Nonliear Physics
KW - Statistical and Nonliear Physics
UR - http://hdl.handle.net/10807/156215
U2 - 10.1140/epjb/e2020-100563-2
DO - 10.1140/epjb/e2020-100563-2
M3 - Article
SN - 1434-6036
SP - 1
EP - 13
JO - EUROPEAN PHYSICAL JOURNAL. B, CONDENSED MATTER AND COMPLEX SYSTEMS
JF - EUROPEAN PHYSICAL JOURNAL. B, CONDENSED MATTER AND COMPLEX SYSTEMS
ER -