## 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 K_{n}
, 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
}(K_{n}
): (i) the average reliability
Rel
A
¯
(
K
n
)
https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351174664/3694f755-869e-4049-90fd-02861cf29af6/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-u.s3.eu-west-1.amazonaws.com/9781351174664/3694f755-869e-4049-90fd-02861cf29af6/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.