Skip to main content
SpringerLink
Log in

Analysis of Cluster Damages in Network Systems

  • Published:
Computational Mathematics and Mathematical Physics Aims and scope Submit manuscript

Abstract

Changes in the functional characteristics of a multicommodity network with cluster architecture of the logical links depending on damages of edges of its physical topology graph are studied. The concept of a cluster damage is defined as a damage that separates at least one vertex from its sinks. The analysis is carried out on the class of minimum cluster damages. The stability of each cluster of logical links is analyzed with respect to the set of damages when the damage is not directly aimed at the source vertex of the cluster. Estimates of the cluster integrity on the whole and in terms of the undamaged (undivided) links remaining in the cluster are obtained. These estimates provide a basis for bi-criteria ranking of clusters depending on their susceptibility to nonrandom damages of the network. Characteristics of the minimum cluster damages and methods for their comparison are proposed. This approach can be used for a quick analysis of vulnerability of large territorially distributed systems, including telecommunication, communication, and control systems.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1.
Fig. 2.
Fig. 3.

Similar content being viewed by others

REFERENCES

  1. V. V. Velichko, V. K. Popkov, and G. V. Popkov, Models and Methods of Increasing the Survivability of Modern Communication Systems (Goryachaya liniya, Moscow, 2017) [in Russian].

  2. A. K. Levakov, Operational Features of Next Generation Telecommunication Systems in Emergency Situations (IRIAS, Moscow, 2012) [in Russian].

    Google Scholar 

  3. D. J. Watts and S. H. Strogatz, “Collective dynamics of ’small-world’ networks,” Nature, No. 393 (6684), 409–410 (1998).

    Article  Google Scholar 

  4. T. H. Grubesic, T. C. Matisziw, A. T. Murray, et al. “Comparative approaches for assessing network vulnerability,” Int. Regional Sci. Rev. 31 (1), 88–112 (2008).

    Article  Google Scholar 

  5. M. A. Alim, N. P. Nguyen, D. N. Thang, et al., “Structural vulnerability analysis of overlapping communities in complex networks,” Proc. of the 2014 IEEE/WIC/ACM Int. Conf. on Web Intell., WI ’14 (ACM, New York, 2014), pp. 231–235.

  6. T. Gomes, C. Esposito, D. Hutchison, F. Kuipers, J. Rak, and M. Tornatore, “A survey of strategies for communication networks to protect against large-scale natural disasters,” Int. Workshop on Reliable Networks Design and Modeling (RNDM), 2016, pp. 11–22.

  7. A. Kuhnle, N. P. Nguyen, T. N. Dinh, and M. T. Thai, “Vulnerability of clustering under nodes failure in complex networks,” Social Network Anal. Mining 7 (1), 8–24 (2017).

    Article  Google Scholar 

  8. J. Ponton, P. Wei, and D. Sun, “Weighted clustering coefficient maximization for air transportation networks,” Control Conf. (ECC), 2013. pp. 866–871.

  9. F. Frank and I. T. Frish, Communication, Transmission and Transportation Networks (Addison-Wesley, Reading, Mass., 1971; Svyaz’, Moscow, 1978).

  10. L. R. Ford and D. R. Fulkerson, Flows in Networks (Princeton Univ. Press, Princeton, 1962; Mir, Moscow, 1966).

  11. P. A. Jensen and J. W. Barnes, Network Flow Programming (Wiley, New York, 1980; Radio i Svyaz’, Moscow, 1984).

  12. Yu. B. Germeier, Introduction to the Theory of Operations Research (Nauka, Moscow, 1971) [in Russian].

    Google Scholar 

  13. Yu. E. Malashenko, I. A. Nazarova, and N. M. Novikova, “An approach to the analysis of possible structural damages in multicommodity network systems,” Comput. Math. Math. Phys. 59, 1562–1575 (2019).

    Article  MathSciNet  Google Scholar 

  14. A. A. Assad, “Multicommodity network flows: A survey,” Networks 8 (1), 37–91 (1978).

    Article  MathSciNet  Google Scholar 

  15. C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, 1982; Mir, Moscow, 1985).

  16. Yu. E. Malashenko, I. A. Nazarova, and N. M. Novikova, “Fuel and energy system control at large-scale damages. IV. A priori estimates of structural and functional vulnerability,” J. Comput. Syst. Sci. Int. 57, 907–920 (2018).

    Article  Google Scholar 

  17. Yu. E. Malashenko, I. A. Nazarova, and N. M. Novikova, “Vulnerability analysis of multi-polar networks after structural damages,” Inform. Primen. 13 (1), 33–39 (2019).

    Google Scholar 

  18. M. Lalou, M. A. Tahraoui, and H. Kheddouci, “The critical node detection problem in networks: A survey,” Comput. Sci. Rev. 28, 92–117 (2018).

    Article  MathSciNet  Google Scholar 

  19. M. Ventresca, K. R. Harrison, and B. M. Ombuki-Berman, “The bi-objective critical node detection problem,” Eur. J. Oper. Res. 265, 895–908 (2018).

    Article  MathSciNet  Google Scholar 

  20. J. Li, P. M. Pardalos, B. Xin, and J. Chen, “The bi-objective critical node detection problem with minimum pairwise connectivity and cost: Theory and algorithms,” Soft Comput. 23, 12729–12744 (2019).

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia

    Yu. E. Malashenko, I. A. Nazarova & N. M. Novikova

Authors
  1. Yu. E. Malashenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. I. A. Nazarova
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. N. M. Novikova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to I. A. Nazarova or N. M. Novikova.

Additional information

Translated by A. Klimontovich

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Malashenko, Y.E., Nazarova, I.A. & Novikova, N.M. Analysis of Cluster Damages in Network Systems. Comput. Math. and Math. Phys. 60, 341–351 (2020). https://doi.org/10.1134/S0965542520020098

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0965542520020098

Keywords:

Search

Navigation