Inconsistencies Among Spectral Robustness Metrics | SpringerLink
Skip to main content
Springer Nature Link
Log in

Inconsistencies Among Spectral Robustness Metrics

  • Conference paper
  • First Online:
Quality, Reliability, Security and Robustness in Heterogeneous Systems (Qshine 2018)

Abstract

Network robustness plays a critical role in the proper functioning of modern society. It is common practice to use spectral metrics, to quantify the robustness of networks. In this paper we compare eight different spectral metrics that quantify network robustness. Four of the metrics are derived from the adjacency matrix, the others follow from the Laplacian spectrum. We found that the metrics can give inconsistent indications, when comparing the robustness of different synthetic networks. Then, we calculate and compare the spectral metrics for a number of real-world networks, where inconsistencies still occur, but to a lesser extent. Finally, we indicate how the concept of the \(R^*\)-value, a weighted sum of robustness metrics, can be used to resolve the found inconsistencies.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 4804
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 6006
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Albert, R., Jeong, H., Barabási, A.L.: Error and attack tolerance of complex networks. Nature 406(6794), 378–382 (2000)

    Article  Google Scholar 

  2. Almendral, J.A., Díaz-Guilera, A.: Dynamical and spectral properties of complex networks. New J. Phys. 9(6), 187 (2007)

    Article  Google Scholar 

  3. Barahona, M., Pecora, L.M.: Synchronization in small-world systems. Phys. Rev. Lett. 89(5), 054101 (2002)

    Article  Google Scholar 

  4. Baras, J.S., Hovareshti, P.: Efficient and robust communication topologies for distributed decision making in networked systems. In: Proceedings of the 48th IEEE Conference on Decision and Control, pp. 3751–3756 (2009)

    Google Scholar 

  5. Cvetković, D., Simić, S.: Graph spectra in computer science. Linear Algebra Appl. 434(6), 1545–1562 (2011)

    Article  MathSciNet  Google Scholar 

  6. Cvetković, D.M.: Applications of graph spectra: an introduction to the literature. Appl. Graph Spectra 13(21), 7–31 (2009)

    MathSciNet  MATH  Google Scholar 

  7. Donetti, L., Hurtado, P.I., Munoz, M.A.: Entangled networks, synchronization, and optimal network topology. Phys. Rev. Lett. 95(18), 188701 (2005)

    Article  Google Scholar 

  8. Ellens, W., Spieksma, F., Van Mieghem, P., Jamakovic, A., Kooij, R.E.: Effective graph resistance. Linear Algebra. Appl. 435(10), 2491–2506 (2011)

    Article  MathSciNet  Google Scholar 

  9. Ellens, W., Kooij, R.E.: Graph measures and network robustness. arXiv preprint arXiv:1311.5064 (2013)

  10. Estrada, E.: Characterization of 3D molecular structure. Chem. Phys. Lett. 319(5), 713–718 (2000)

    Article  Google Scholar 

  11. Estrada, E.: When local and global clustering of networks diverge. Linear Algebra Appl. 488, 249–263 (2016)

    Article  MathSciNet  Google Scholar 

  12. Estrada, E., Rodriguez-Velazquez, J.A.: Subgraph centrality in complex networks. Phys. Rev. E 71(5), 056103 (2005)

    Article  MathSciNet  Google Scholar 

  13. Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23(2), 298–305 (1973)

    MathSciNet  MATH  Google Scholar 

  14. Hines, P., Balasubramaniam, K., Sanchez, E.C.: Cascading failures in power grids. IEEE Potentials 28(5), 24–30 (2009)

    Article  Google Scholar 

  15. Jamakovic, A., Van Mieghem, P.: On the robustness of complex networks by using the algebraic connectivity. In: Das, A., Pung, H.K., Lee, F.B.S., Wong, L.W.C. (eds.) NETWORKING 2008. LNCS, vol. 4982, pp. 183–194. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-79549-0_16

    Chapter  Google Scholar 

  16. Jun, W., Barahona, M., Yue-Jin, T., Hong-Zhong, D.: Natural connectivity of complex networks. Chin. Phys. Lett. 27(7), 078902 (2010)

    Article  Google Scholar 

  17. Karrer, B., Levina, E., Newman, M.E.J.: Robustness of community structure in networks. Phys. Rev. E 77(4), 046119 (2008)

    Article  Google Scholar 

  18. Knight, S., Nguyen, H.X., Falkner, N., Bowden, R., Roughan, M.: The Internet topology zoo. IEEE J. Sel. Areas Commun. 29(9), 1765–1775 (2011)

    Article  Google Scholar 

  19. Li, C., Wang, H., De Haan, W., Stam, C.J., Van Mieghem, P.: The correlation of metrics in complex networks with applications in functional brain networks. J. Stat. Mech. Theory Exp. 25(11), P11018 (2011)

    Article  MathSciNet  Google Scholar 

  20. Li, T., Fu, M., Xie, L., Zhang, J.F.: Distributed consensus with limited communication data rate. IEEE Trans. Autom. Control 56(2), 279–292 (2011)

    Article  MathSciNet  Google Scholar 

  21. Manzano, M., Sahneh, F.D., Scoglio, C.M., Calle, E., Marzo, J.L.: Robustness surfaces of complex networks. Nature Sci. Rep. 4(6133), 1–6 (2014)

    Google Scholar 

  22. Marcus, C.M., Westervelt, R.M.: Stability of analog neural networks with delay. Phys. Rev. A 39(1), 347 (1989)

    Article  MathSciNet  Google Scholar 

  23. Marzo, J.L., Calle, E., Gomez-Cosgaya, S., Rueda, D., Manosa, A.: On selecting the relevant metrics of network robustness. In: 10th International Workshop on Reliable Networks Design and Modeling (RNDM) (2018)

    Google Scholar 

  24. McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symbolic Comput. 60, 94–112 (2014)

    Article  MathSciNet  Google Scholar 

  25. Strogatz, S.H.: From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators. Phys. D Nonlinear Phenom. 143(1), 1–20 (2000)

    Article  MathSciNet  Google Scholar 

  26. Trajanovski, S., Martín-Hernández, J., Winterbach, W., Van Mieghem, P.: Robustness envelopes of networks. J. Complex Netw. 1(1), 44–62 (2013)

    Article  Google Scholar 

  27. Van Mieghem, P.: Graph Spectra for Complex Networks. Cambridge University Press, Cambridge (2010)

    Book  Google Scholar 

  28. Van Mieghem, P., Omic, J., Kooij, R.E.: Virus spread in networks. IEEE/ACM Trans. Netw. 17(1), 1–14 (2009)

    Article  Google Scholar 

  29. Wang, X., Koç, Y., Derrible, S., Ahmad, S.N., Pino, W.J., Kooij, R.E.: Multi-criteria robustness analysis of metro networks. Phys. A Stat. Mech. Appl. 474, 19–31 (2017)

    Article  Google Scholar 

  30. Wang, X., Koç, Y., Kooij, R.E., Van Mieghem, P.: A network approach for power grid robustness against cascading failures. In: 7th International Workshop on Reliable Networks Design and Modeling (RNDM), pp. 208–214. IEEE (2015)

    Google Scholar 

  31. Wang, X., Pournaras, E., Kooij, R.E., Van Mieghem, P.: Improving robustness of complex networks via the effective graph resistance. Eur. Phys. J. B 87(9), 1–12 (2014)

    Article  Google Scholar 

  32. Watanabe, T., Masuda, N.: Enhancing the spectral gap of networks by node removal. Phys. Rev. E 82(4), 046102 (2010)

    Article  MathSciNet  Google Scholar 

  33. Wu, J., Barahona, M., Tan, Y.J., Deng, H.Z.: Spectral measure of structural robustness in complex networks. IEEE Trans. Syst. Man Cybern.-Part A Syst. Hum. 41(6), 1244–1252 (2011)

    Article  Google Scholar 

  34. Wu, Z.X., Holme, P.: Onion structure and network robustness. Phys. Rev. E 84(2), 026106 (2011)

    Article  Google Scholar 

  35. Zanin, M., et al.: Combining complex networks and data mining: why and how. Phys. Rep. 635, 1–44 (2016)

    Article  MathSciNet  Google Scholar 

  36. Zeng, Y., Liang, Y.C.: Eigenvalue-based spectrum sensing algorithms for cognitive radio. IEEE Trans. Commun. 57(6), 1784–1793 (2009)

    Article  Google Scholar 

Download references

Acknowledgements

This research was supported in part by the Netherlands Organization for Scientific Research (NWO) with project number 439.16.107, the National Research Foundation (NRF), Prime Minister’s Office, Singapore, under its National Cybersecurity R & D Programme (Award No. NRF 2014NCR-NCR001-40) and administered by the National Cybersecurity R & D Directorate, by the Spanish Ministry of Science and Innovation project GIROS TEC2015-66412-R and by the Generalitat de Catalunya research support program SGR-1469.

Author information

Authors and Affiliations

  1. Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands

    Xiangrong Wang & Robert E. Kooij

  2. Computing Science Department, Institute of High Performance Computing, A*STAR, Singapore, Singapore

    Ling Feng

  3. iTrust, Centre for Research in Cyber Security, Singapore University of Technology and Design, Singapore, Singapore

    Robert E. Kooij

  4. Institute of Informatics and Applications, University of Girona, Girona, Spain

    Jose L. Marzo

Authors
  1. Xiangrong Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ling Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Robert E. Kooij
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jose L. Marzo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiangrong Wang .

Editor information

Editors and Affiliations

  1. Queen’s University Belfast, Belfast, UK

    Trung Q. Duong

  2. Institute of Fundamental and Applied Sciences, Duy Tan University, Ho Chi Minh City, Vietnam

    Nguyen-Son Vo

  3. Ho Chi Minh City University of Technology and Education, Ho Chi Minh City, Vietnam

    Van Ca Phan

Rights and permissions

Reprints and permissions

Copyright information

© 2019 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Wang, X., Feng, L., Kooij, R.E., Marzo, J.L. (2019). Inconsistencies Among Spectral Robustness Metrics. In: Duong, T., Vo, NS., Phan, V. (eds) Quality, Reliability, Security and Robustness in Heterogeneous Systems. Qshine 2018. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 272. Springer, Cham. https://doi.org/10.1007/978-3-030-14413-5_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-14413-5_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-14412-8

  • Online ISBN: 978-3-030-14413-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics