Predictability of Network Robustness from Spectral Measures

DOI Web Site
  • Yamashita Kazuyuki
    Department of Informatics, Graduate School of Science and Technology, Kwansei Gakuin University
  • Yasuda Yuichi
    Department of Informatics, Graduate School of Science and Technology, Kwansei Gakuin University
  • Nakamura Ryo
    Department of Electronics Engineering and Computer Science, Faculty of Engineering, Fukuoka University
  • Ohsaki Hiroyuki
    Department of Informatics, Graduate School of Science and Technology, Kwansei Gakuin University

抄録

<p>Robustness against failure and attack is one of the essential properties of large-scale dynamical system such as power grids, transportation system, communication systems, and computer networks. Despite its popularity and intuitiveness, a major drawback of descriptive robustness metrics such as the size of the largest connected component and the network diameter is computational complexity. Spectral measures such as the spectral radius, the natural connectivity, and the algebraic connectivity are much easier to obtain than descriptive metrics, but the predictability of those measures against different levels and types of failures has not been well understood. In this paper, we therefore investigate how effectively spectral measures can estimate the robustness of a network against random and adversary node removal. Our finding includes that, among five types of spectral measures, the effective resistance is most suitable for predicting the largest cluster component size under low node removal ratio, and that the predictability of the effective resistance is stable among different types of networks.</p>

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ