ABSTRACT
In network reliability, the best-known performance measure is the so-called all-terminal reliability Rel A (G), i.e., the probability that all the nodes of the network (or its underlying graph G) are connected. A particular family of graphs, namely the complete graphs Kn , in which each node is connected to the n – 1 others, have long been a key issue in this field. Brown, Cox and Ehrenborg have recently proposed new performance indices for networks based on the all-terminal reliability Rel A (Kn ): (i) the average reliability Rel A ¯ ( K n ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781351174664/8eaf59aa-3ab2-4f02-a6a7-3741c7dd9132/content/eq1301.tif"/> , (ii) the “average of the average” all-terminal reliability AvgAvg (G, n) of all the graphs with n vertices and at most one edge between two nodes. They showed that as n increases, these measures tend to 1. In this work, we generalize their idea to the k-terminal reliability—the probability that k nodes are connected—which can also be used to describe a network’s resilience. The new measures can be derived from the k-terminal reliability of the complete graph. Since we are interested in the application of these indices to large systems (n >> 1), we have performed numerical investigations to assess their variations with n. We have identified the leading, analytical correction (in 1/n) to unity. This corroborates a previous conjecture made on the asymptotic value of Rel A ¯ ( K n ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781351174664/8eaf59aa-3ab2-4f02-a6a7-3741c7dd9132/content/eq1302.tif"/> . These new results could be helpful as simple, ready-to-use evaluations/orders of magnitude of the resilience of a network, when its size is so large as to make exact or approximate computations either impossible or very cumbersome.
