Vertex decomposition to calculate the network probabilistic connectivity

D. A. Migov

Prikladnaâ diskretnaâ matematika, no. 1 (2020), pp. 62-86.

Résumé

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.

Détail

Keywords: network reliability, random graph, probabilistic connectivity, factoring method, network decomposition, edge cut.
Mots-clés : vertex cut

Bibliographie

[1] Zhukovskiy M. E., Raygorodskiy A. M., “Random graphs: models and asymptotic characteristics”, Uspekhi Matematicheskikh Nauk, 70:1(421) (2015), 35–88 (in Russian) | DOI | MR

[2] Colbourn Ch. J., The Combinatorics of Network Reliability, Oxford Univ. Press, N.Y., 1987, 160 pp. | MR

[3] Valiant L., “The complexity of enumeration and reliability problems”, SIAM J. Comput., 8:3 (1979), 410–421 | DOI | MR | Zbl

[4] Page L. B., Perry J. E., “A practical implementation of the factoring theorem for network reliability”, IEEE Trans. Reliability, 37:3 (1988), 259–267 | DOI

[5] Ryabinin I. A., “Logical-probabilistic calculus: A tool for studying the reliability and safety of structurally complex systems”, Automation and Remote Control, 64:7 (2003), 178–186 | DOI | MR | Zbl

[6] Satyanarayana A., Wood R. K., “A linear-time algorithm for computing $K$-terminal reliability in series-parallel networks”, SIAM J. Comput., 18 (1985), 818–883 | DOI | MR

[7] Shooman A. M., Kershenbaum A., “Methods for communication-network reliability analysis: probabilistic graph reduction”, IEEE Proc. Reliability and Maintainability Symp. (1992), IEEE Press, Las Vegas, USA. N.Y., 1992, 441–448 | MR

[8] Wood R. K., “A factoring algorithm using polygon-to-chain reductions for computing $K$-terminal network reliability”, Networks, 15:2 (1985), 173–190 | DOI | MR | Zbl

[9] Mochalov V. A., “The method of synthesis of fault-tolerant structure of the sensor network in restrictions on the placement of network nodes in a heterogeneous space”, T-Comm: Telekommunikatsii i Transport, 6:10 (2012), 71–75 (in Russian)

[10] Rodionov A. S., Rodionova O. K., “Random hypernets in reliability analysis of multilayer networks”, Lecture Notes in Electrical Engineering, 343, 2015, 307–315 | DOI

[11] Melentyev V. A., “Function of structural fault tolerance and $d$-limited connected component of graph of a computational system”, Prikladnaya Diskretnaya Matematika, 2:2 (2008), 102–106 (in Russian)

[12] Levendovszky J., Jereb L., Elek Zs., Vesztergombi Gy., “Adaptive statistical algorithms in network reliability analysis”, Performance Evaluation, 48:1–4 (2002), 225–236 | DOI | Zbl

[13] Tsitsiashvili G. Sh., Osipova M A., Losev A. S., “Derivation of asymptotic constants for the probabilistic connectivity of a planar weighted graph”, Prikladnaya Diskretnaya Matematika, 2014, no. 2(24), 97–100 (in Russian)

[14] Lototsky A. D., “Study of accurate methods for calculating the structural reliability of computer networks”, Innovatsii na Osnove Informatsionnykh i Kommunikatsionnykh Tekhnologiy, 1 (2014), 233–235 (in Russian)

[15] Rodionov A. S., Rodionova O. K., “Some methods for speeding up the calculation of the reliability of information networks”, Proc. IT+SF 2003 (Gurzuf, Ukraine, 2003), Zaporozhye State University Publ., Zaporozhye, 2003, 215–217 (in Russian)

[16] Migov D. S., “Formulas for quickly calculating the probabilistic connectivity of a subset of vertices in graphs of small dimension”, Problemy Informatiki, 6 (2010), 10–17 (in Russian)

[17] Chen Y., Li J., Chen J., “A new algorithm for network probabilistic connectivity”, Proc. IEEE Military Communications Conf., v. 2, IEEE Press, N.Y., 1999, 920–923

[18] Tittmann P., “Partitions and network reliability”, Discr. Appl. Math., 95:1–3 (1999), 445–453 | DOI | MR | Zbl

[19] Won J.-M., Karray F., “Cumulative update of all-terminal reliability for faster feasibility decision”, IEEE Trans. Reliability, 59:3 (2010), 551–562 | DOI

[20] Rodionov A., Migov D., Rodionov O., “Improvements in the efficiency of cumulative updating of all terminal network reliability”, IEEE Trans. Reliability, 61:2 (2012), 460–465 | DOI

[21] Martinez S. P., Calvino B. O., Rocco S. C. M., “All-terminal reliability evaluation through a Monte Carlo simulation based on an MPI implementation”, European Safety and Reliability Conference: Advances in Safety, Reliability and Risk Management, PSAM 2011/ESREL 2012 (Helsinki, 2012), 1–6

[22] Rodionov A., Sakerin A., Migov D., “Some issues of parallel implementation of the exhaustive search algorithm (by the example of network reliability problems)”, Vestnik SibGUTI, 4 (2014), 79–84 (in Russian)

[23] Hebert P.-R., “Sixty years of network reliability”, Mathematics in Computer Science, 12 (2018), 275–293 | DOI | MR | Zbl

[24] Popkov V. K., Mathematical Models of Connectivity, v. 1–3, ICMMG Publ., Novosibirsk, 2000–2002 (in Russian)

[25] Wood R. K., “Triconnected decomposition for computing $K$-terminal network reliability”, Networks, 19 (1989), 203–220 | DOI | MR | Zbl

[26] Hopcroft J., Tarjan R., “Dividing a graph into triconnected components”, SIAM J. Comput., 2 (1973), 135–158 | DOI | MR

[27] Migov D. A., “Using vertex cuts of a random graph to calculate the probability of its connectivity”, Proc. Young Scientists Conf. ICMMG of SB RAS, ICMMG Publ., Novosibirsk, 2004, 133–130 (in Russian)

[28] Migov D. A., “Calculation of the probability of network connectivity using vertex cuts of a special kind”, Proc. All-Russian Young Scientists Conf. Math. Modeling and Inf. Technology (2004), ICT of SB RAS, Novosibirsk, 24–25 (in Russian)

[29] Migov D. A., “Calculation of the probability of network connectivity using longitudinal cuts”, Proc. Young Scientists Conf. ICMMG SB RAS, ICMMG Publ., Novosibirsk, 2006, 144–151 (in Russian)

[30] Migov D. A., Rodionova O. K., Rodionov A. S., Choo H., “Network probabilistic connectivity: using node cuts”, LNCS, 4097, 2006, 702–709 | MR

[31] Migov D. A., Calculation of the Connectivity Probability of a Random Graph Using Cuts, PhD Thesis, ICMMG, Novosibirsk, 2008, 96 pp. (in Russian)

[32] Migov D. A., “Methods for calculating the reliability of networks based on the use of sections”, Vychislitelnyye Tekhnologii, 13 (2008), 425–431 (in Russian)

[33] Migov D. A., “Computing diameter constrained reliability of a network with junction points”, Automation and Remote Control, 72:7 (2011), 1415–1419 | DOI | MR | Zbl

[34] Burgos J. M., Amoza F. R., “Factorization of network reliability with perfect nodes I: Introduction and statements”, Discr. Appl. Math., 198 (2016), 82–90 | DOI | MR | Zbl

[35] Burgos J. M., “Factorization of network reliability with perfect nodes II: Connectivity matrix”, Discr. Appl. Math., 198 (2016), 91–100 | DOI | MR | Zbl

[36] Gutwenger C., Mutzel P. A., “A linear time implementation of SPQR-trees”, LNCS, 1984 (2001), 77–90 | Zbl

[37] Tsin Y. H., “Decomposing a multigraph into split components”, Proc. CATS'12 (Melbourne, Australia, 2012), The Australasian Theory Symposium, 128, 3–12

[38] Karpov D. V., “Section tree and minimally $k$-connected graph”, Zapiski Nauchnykh Seminarov POMI, 427, 2014, 22–40 (in Russian)

[39] Halin R., “$S$-functions for graphs”, J. Geometry, 8:2 (1976), 171–186 | DOI | MR | Zbl