Journal of Supercomputing.
ISSN/ISBN: Not available at this time. DOI: 10.1007/s11227-021-04216-2
Abstract: Various methods have been proposed to evaluate the reliability of a graph, one of the most well known of which is the reliability polynomial, R(G, p). It is assumed that G(V, E) is a simple and unweighted connected graph whose nodes are perfect and edges are operational with an independent probability p. Thus, the edge reliability polynomial is a function of p of the number of network edges. There are various methods for calculating the coe cients of reliability polynomial, all of which are related to their recursive nature, which has led to an increase in their computational complexity. Therefore, if the difference between the number of links and nodes in the network exceeds a certain amount, the exact calculation of the coe cients R(G, p) is practically in the NP-hard complexity class. In this paper, while examining the problems in the previous methods, four new approaches for estimating the coe - cients of reliability polynomial are presented. In the rst approach, using an iterative method, the coe cients are estimated. This method, on average, has the same accu- racy as common methods in the related studies. In addition, the second method as an intelligent scheme for integrating the values of coe cients has been proposed. The values of coe cients for smaller, larger, and nally intermediate indices have been determined with the help of this intelligent approach. Further, as a third proposed method, Benford’s law is utilized to combine the coe cients. Finally, in the fourth approach, using the Legendre interpolation method, the coe cients are effectively estimated with an appropriate accuracy. To compare these approaches fairly and accurately with each other, they have been carried out on synthetic and real-world underlying graphs. Then, their effciency and accuracy have been evaluated, compared, and analyzed according to the experimental results.
Bibtex:
@article{,
issn = {0920-8542},
journal = {The journal of supercomputing},
publisher = {Kluwer Academic Publishers},
year = {2022},
title = {Efficient methods for computing the reliability polynomials of graphs and complex networks},
address = {[Dordrecht] :},
author = {Safaei, F and Akbar, R and Moudi, M},
doi = {10.1007/s11227-021-04216-2},
}
Reference Type: Journal Article
Subject Area(s): Computer Science