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.
Graphical abstract
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Liang, S. Jin, D. Wang, X. Zou, Eur. Phys. J. B 89, 186 (2016)
A.P. Masucci, C. Molinero, Eur. Phys. J. B 89, 53 (2016)
G. Paul, T. Tanizawa, S. Havlin, H.E. Stanley, Eur. Phys. J. B, 38, 187 (2004)
A. Sydney, C.M. Scoglio, P. Schumm, R.E. Kooij, Elasticity: Topological characterization of robustness in complex networks. inProceedings of the 3rd International Conference on Bio-Inspired Models of Network, Information and Computing Sytems (2008), Vol. 19, pp. 1–8
A. Braunstein, L. Dall’Asta, G. Semerjian, L. Zdeborova, PNAS 133, 12368 (2016)
D.S. Callaway, M.E.J. Newman, S.H. Strogatz, D.J. Watts, Phys. Rev. Lett. 85, 5468 (2000)
F. Morone, H.A. Makse, Nature 524, 65 (2015)
X.L. Ren, N. Gleinig, D. Helbing, N. Antulov-Fantulin, PNAS 116, 6554 (2019)
L Zdeborova, P. Zhang, H.J. Zhou, Sci. Rep. 6, 37954 (2016)
S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.U. Hwang, Phys. Rep. 424, 175 (2006)
F. Costa, F.A. Rodrigues, G. Travieso, P.R. Villas Boas, Adv. Phys. 56, 167 (2007)
S.N. Dorogovtsev, J.F.F. Mendes, Adv. Phys. 51, 1079 (2002)
W. Ellens, F.M. Spieksma, P. Van Mieghem, A. Jamakovic, R.E. Kooij, Linear Algebra Appl. 435, 2491 (2011)
P. Van MieghemGraph Spectra for Complex Networks (Cambridge University Press, Cambridge, 2011)
D.J. Klein, M. Randić, J. Math. Chem. 12, 81 (1993)
A.Z. Broder, A.R. Karlin, J. Theor. Prob. 2, 101 (1989)
A. Chandra, P. Raghavan, W. Ruzzo, R. Smolensky, P. Tiwari, The electrical resistance of a graph captures its commute and cover times, inSTOC (1989), pp. 574–586
X. Wang, E. Pournaras, R.E. Kooij, P. Van Mieghem, Eur. Phys. J. B 87, 221 (2014)
A. Ghosh, S. Boyd, A. Saberi, SIAM Rev. 50, 37 (2008)
P. Van Mieghem, X. Ge, P. Schumm, S. Trajanovski, H. Wang, Phys. Rev. E 82, 56 (2010)
W. Abbas, M. Egerstedt, Robust graph topologies for networked systems, in3rd IFAC Workshop on Distributed Estimation and Control in Networked Systems (2012), pp. 85–90
M. Bianchi, A. Cornaro, J.L. Palacios, A. Torriero, Localization of Graph Topological Indices via Majorization Technique, inQuantitative Graph Theory. Mathematical Foundations and Applications (CRC Press, Boca Raton, 2014), pp. 35–79
M. Bianchi, A. Cornaro, A. Torriero, Discr. Appl. Math. 161, 2731 (2013)
R. Grone, R. Merris, SIAM J. Discr. Math. 7, 221 (1994)
F. Harary,Graph Theory (Addison-Wesley Publishing Company, Boston, 1969)
L. Feng, I. Gutman, L. Yu, Trans. Comb. 1, 27 (2010)
H.Y. Zhu, D.J. Klein, I. Lukovits, J. Chem. Inf. Comput. Sci. 36, 420 (1996)
M. Bianchi, A. Cornaro, A. Torriero. Math. Inequal. Appl. 16, 329 (2013)
A.W. Marshall, I. Olkin, B. Arnold,Inequalities: Theory of Majorization and Its Applications. (Springer, Berlin, 2011)
M. Bianchi, A. Cornaro, J.L. Palacios, A. Torriero, J. Math.Chem. 51, 569 (2013)
G.P. Clemente, A. Cornaro, MATCH Commun. Math. Comput. Chem. 73, 175 (2015)
A. Cornaro, G.P. Clemente, Electron. Notes Discr. Math. 41, 383 (2013)
J.L. Palacios, J.M. Renom, Int. J. Quantum Chem. 111, 35 (2011)
H. Wang, H. Hua, D. Wang, Math. Commun. 15, 347 (2010)
B. Zhou, N. Trinajstić, Chem. Phys. Lett. 455, 120 (2008)
P. Erdős, A. Rényi, Publ. Math. 6, 290 (1959)
P. Erdős, A. Rényi, Publ. Math. Int. Hung. Acad. Sci. 5, 17 (1960)
R. Albert, A. Barabasi, Rev. Mod. Phys. 74, 47 (2002)
D.J. Watts, S.H. Strogatz, Nature 393, 440 (1998)
R. Albert, H. Jeong, A.L. Barabási, Nature 406, 378 (2000)
L.P. Chi, X. Cai, Int. J. Mod. Phys. B 18, 2394 (2004)
R. Cohen, D. Ben-Avraham, S. Havlin, Phys. Rev. E 66, 36 (2002)
F. Pozzi, T. Di Matteo, T. Aste, Sci. Rep. 3, 1665 (2013)
V. Tola, F. Lillo, M. Gallegati, R.N. Mantegna, J. Econ. Dyn. Control 32, 235 (2008)
M. Tumminello, T. Aste, T. Di Matteo, R.N. Mantegna, Proc. Natl. Acad. Sci. 102, 10421 (2005)
M. Tumminello, T. Di Matteo, T. Aste, R.N. Mantegna, Eur. Phys. J. B 55, 209 (2007)
L.M. Varela, G. Rotundo, M. Ausloos, J. Carrete, Complex network analysis in socioeconomic models, inComplexity and Geographical Economics (Springer, Berlin, 2015), pp. 209–245
J.P. Onnela, A. Chakraborti, K. Kaski, J. Kertesz, A. Kanto, Phys. Rev. E 68, 056110 (2003)
M. Ausloos, Physica A 285, 48 (2000)
N. Vandewalle, M. Ausloos, Physica A 246, 454 (1997)
S. Battiston, J.B. Glattfelder, D. Garlaschelli, F. Lillo, G. Caldarelli, The structure of financial networks, inNetwork Science (Springer, Berlin, 2010), pp. 131–163
M. Illing, Y. Liu, J. Financial Stab. 2, 243 (2006)
G.P. Clemente, R. Grassi, C. Pederzoli, J. Econ. Interact. Coord. 15, 1 (2019)
S.C. Hakkio, W.R. Keeton, Economic Review 94, 5 (2009), pp. 5–50
D. Holló, M. Kremer, M. Lo Duca, CISS - A composite indicator of systemic stress in the financial system, European Central Bank Working Paper (2012)
C. Minoiu, J.A. Reyes, J. Financial Stab. 9, 168 (2013)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
The EPJ Publishers remain neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Clemente, G.P., Cornaro, A. Bounding robustness in complex networks under topological changes through majorization techniques. Eur. Phys. J. B 93, 114 (2020). https://doi.org/10.1140/epjb/e2020-100563-2
Received:
Published:
DOI: https://doi.org/10.1140/epjb/e2020-100563-2