RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Prikl. Diskr. Mat., 2020, Number 47, Pages 62–86 (Mi pdm695)

Applied Graph Theory

Vertex decomposition to calculate the network probabilistic connectivity

D. A. Migov

Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, Russia

Abstract: We consider the problem of calculating such an indicator of network reliability as the random graph probabilistic connectivity. It is assumed that the edges of the network are subject to failures that occur independently of each other with given probabilities. Network nodes are assumed to be absolutely reliable. The possibility of using network decomposition via vertex cuts for the network reliability calculation is investigated. By cut we mean a set of network elements, the removal of which makes the network disconnected. The history of the development of such methods is given, and the place of our results is indicated among them. The results related to the case of two nodes cuts are presented in detail, including the results of the author and R. K. Wood (1985). Next, we consider the cuts of arbitrary power. The results in this area were obtained by the author (2004–2008) and J. M. Burgos (2016). Also, certain results using cuts were obtained by the author for the cumulative bounds updating of the random graph probabilistic connectivity (2012) and for the diameter constrained reliability calculation (2011–2012). Author results include the general method, which gives the formulas expressing the reliability of a network with a vertex cut through the reliabilities of its subnets obtained by cut decomposition, as well as through reliabilities of the subnets, contracted by all possible variants over cut vertices. On its basis, we derive such formulas for cuts of two, three, and four vertices. Some of the results of the author were previously published; some results are published for the first time, including the correct formula for four vertices cut and the valid proof of the solvability of a system of linear equations, which guarantees the existence of the above mentioned formulas. The results of numerical experiments showing the applicability of the proposed methods are given. For example, using the 3 cut formula the reliability calculation of the 3$\times$16 grid shows an acceleration of about 120 times compared with the factoring method. For biconnected structures, a mathematical apparatus and an algorithm are given that make it possible to effectively take into account all two-vertex sections when calculating their reliability. Without such an approach we should use above mentioned cut formulas recursively, for graphs obtained by cut decomposition and for these graphs contracted by all possible variants over cut vertices. This inevitably leads to recalculation of reliability for certain graphs. Using the proposed algorithm allows to avoid such recalculation and additionally speeds up the reliability calculation for suitable network structures.

Keywords: network reliability, random graph, probabilistic connectivity, factoring method, network decomposition, vertex cut, edge cut.

 Funding Agency Grant Number Russian Foundation for Basic Research 18-07-00460_à Russian Academy of Sciences - Federal Agency for Scientific Organizations 0315-2016-0006

DOI: https://doi.org/10.17223/20710410/47/6

Full text: PDF file (1227 kB)
References: PDF file   HTML file

UDC: ÓÄÊ 519.17+519.24

Citation: D. A. Migov, “Vertex decomposition to calculate the network probabilistic connectivity”, Prikl. Diskr. Mat., 2020, no. 47, 62–86

Citation in format AMSBIB
\Bibitem{Mig20} \by D.~A.~Migov \paper Vertex decomposition to calculate the network probabilistic connectivity \jour Prikl. Diskr. Mat. \yr 2020 \issue 47 \pages 62--86 \mathnet{http://mi.mathnet.ru/pdm695} \crossref{https://doi.org/10.17223/20710410/47/6}