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 × 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.
Download file
Counter downloads: 109
- Title Vertex decomposition to calculate the network probabilistic connectivity
- Headline Vertex decomposition to calculate the network probabilistic connectivity
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 47
- Date:
- DOI 10.17223/20710410/47/6
Keywords
надёжность сети, случайный граф, вероятность связности, метод факторизации, декомпозиция сети, сечение, разрез, network reliability, random graph, probabilistic connectivity, factoring method, network decomposition, vertex cut, edge cutAuthors
References
Жуковский М. Е., Райгородский А. М. Случайные графы: модели и предельные характеристики // Успехи математических наук. 2015. Т. 70. № 1(421). С. 35-88
Colbourn Ch. J. The Combinatorics of Network Reliability. N.Y.: Oxford Univ. Press, 1987. 160 p
Valiant L. The complexity of enumeration and reliability problems // SIAM J. Comput. 1979. V. 8. No. 3. P. 410-421
Page L. B. and Perry J. E. A practical implementation of the factoring theorem for network reliability // IEEE Trans. Reliability. 1988. V. 37. No. 3. P. 259-267
Рябинин И. А. Логико-вероятностное исчисление как аппарат исследования надежности и безопасности структурно-сложных систем // Автомат. и телемех. 2003. Т. 7. С. 178-186
Satyanarayana A. and Wood R. K. A linear-time algorithm for computing K-terminal reliability in series-parallel networks // SIAM J. Comput. 1985. V. 18. P. 818-883
Shooman A. M. and Kershenbaum A. Methods for communication-network reliability analysis: probabilistic graph reduction // IEEE Proc. Reliability and Maintainability Symp. 1992, Las Vegas, USA. N.Y.: IEEE Press, 1992. P. 441-448
Wood R. K. A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability // Networks. 1985. V. 15. No. 2. P. 173-190
Мочалов В. А. Метод синтеза отказоустойчивой струкутры сенсорной сети при наличии ограничений по размещению узлов сети в разнородном пространстве // T-Comm: Телекоммуникации и транспорт. 2012. Т. 6. № 10. С. 71-75
Rodionov A. S. and Rodionova O. K. Random hypernets in reliability analysis of multilayer networks // Lecture Notes in Electrical Engineering. 2015. V. 343. P. 307-315
Мелентьев В. А. Функция структурной отказоустойчивости и d-ограниченная компонента связности графа вычислительной системы // Прикладная дискретная математика. 2008. Т. 2. № 2. С. 102-106
Levendovszky J., Jereb L., Elek Zs., and Vesztergombi Gy. Adaptive statistical algorithms in network reliability analysis // Performance Evaluation. 2002. V. 48. No. 1-4. P. 225-236
Цициашвили Г. Ш., Осипова М.А., Лосев А. С. Вывод асимптотических констант для вероятности несвязности планарного взвешенного графа // Прикладная дискретная математика. 2014. № 2(24). С. 97-100
Лотоцкий А. Д. Исследование точных методов вычисления структурной надёжности компьютерных сетей // Инновации на основе информационных и коммуникационных технологий. 2014. Т. 1. С. 233-235
Родионов А. С., Родионова О. К. Некоторые методы ускорения расчета надёжности информационных сетей // Тр. 30-й Междунар. конф. «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (IT∙SF'2003), Гурзуф, Украина, 2003. Запорожье: Изд-во Запорож. ун-та, 2003. С. 215-217.
Мигов Д. А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики. 2010. Т. 6. С. 10-17
Chen Y., Li J., and Chen J. A new algorithm for network probabilistic connectivity // Proc. IEEE Military Communications Conf. V. 2. N.Y.: IEEE Press, 1999. P. 920-923
Tittmann P. Partitions and network reliability // Discr. Appl. Math. 1999. V. 95. No. 1-3. P. 445-453
Won J.-M. and Karray F. Cumulative update of all-terminal reliability for faster feasibility decision // IEEE Trans. Reliability. 2010. V. 59. No. 3. P. 551-562
Rodionov A., Migov D., and Rodionov O. Improvements in the efficiency of cumulative updating of all terminal network reliability // IEEE Trans. Reliability. 2012. V. 61. No. 2. P. 460-465
Martinez S. P., Calvino B. O., and 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. P. 1-6
Родионов А. С., Сакерин А. В., Мигов Д. А. Некоторые вопросы параллельной реализации алгоритма полного перебора (на примере задач надёжности сетей) // Вестник Сиб-ГУТИ. 2014. Т. 4. С. 79-84
Hebert P.-R. Sixty years of network reliability // Mathematics in Computer Science. 2018. V. 12. P. 275-293
Попков В. К. Математические модели связности. Ч. 1-3. Новосибирск: Изд-во ИВМиМГ СО РАН, 2000-2002
Wood R. K. Triconnected decomposition for computing K -terminal network reliability // Networks. 1989. V. 19. P. 203-220
Hopcroft J. and Tarjan R. Dividing a graph into triconnected components // SIAM J. Comput. 1973. V. 2. P. 135-158
Мигов Д. А. Использование разрезов случайного графа для вычисления вероятности его связности // Труды конф. молодых ученых ИВМиМГ СО РАН, 2004. Новосибирск: ИВМиМГ СО РАН, 2004. С. 133-130
Мигов Д. А. Расчет вероятности связности сети с применением вершинных разрезов специального вида // Тез. докл. V Всерос. конф. молодых ученых по мат. моделированию и инф. технологиям, 2004. Новосибирск: ИВТ СО РАН, 2004. С. 24-25
Мигов Д. А. Расчет вероятности связности сети с применением продольных разрезов // Труды конф. молодых ученых ИВМиМГ СО РАН, 2006. Новосибирск: ИВМиМГ СО РАН, 2006. С. 144-151
Migov D. A., Rodionova O. K., Rodionov A. S., and Choo H. Network probabilistic connectivity: using node cuts // LNCS. 2006. V. 4097. P. 702-709
Мигов Д. А. Расчёт вероятности связности случайного графа с применением сечений: дис. . . . канд. физ.-мат. наук. Новосибирск: Институт вычислительной математики и математической геофизики, 2008. 96 с
Мигов Д. А. Методы расчета надежности сетей, основанные на использовании сечений // Вычислительные технологии. 2008. Т. 13. С. 425-431
Мигов Д. А. Расчёт надёжности сети с ограничением на диаметр с применением точек сочленения // Автоматика и телемеханика. 2011. Т. 7. С. 69-74
Burgos J. M. and Amoza F. R. Factorization of network reliability with perfect nodes I: Introduction and statements // Discr. Appl. Math. 2016. V. 198. P. 82-90
Burgos J. M. Factorization of network reliability with perfect nodes II: Connectivity matrix // Discr. Appl. Math. 2016. V.198. P. 91-100
Gutwenger C. and Mutzel P. A. A linear time implementation of SPQR-trees // LNCS. 2001. V. 1984. P. 77-90
Tsin Y. H. Decomposing a multigraph into split components // Proc. CATS'12, Melbourne, Australia. 2012. V. 128. P. 3-12
Карпов Д. В. Дерево разрезов и минимальный k-связный граф // Записки научных семинаров ПОМИ. 2014. T. 427. С. 22-40
Halin R. S-functions for graphs // J. Geometry. 1976. V. 8. No. 2. P. 171-186
Vertex decomposition to calculate the network probabilistic connectivity | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/6
Download full-text version
Counter downloads: 315