Network reliability is the probabilistic measure that determines whether a network remains functional when its elements fail at random. Definition of functionality varies depending on the problem of interest, thus network reliability has much potential as a unifying framework to study a broad range of problems arising in complex network contexts. However, since its introduction in the 1950's, network reliability has remained more of an interesting theoretical construct than a practical tool. In large part, this is due to well-established complexity costs for both its evaluation and approximation, which has led to the classification of network reliability as a NP-Hard problem. In this dissertation we present an algorithm to estimate network reliability and then utilize it to evaluate the reliability of large networks under various descriptions of functionality.

The primary goal of this dissertation is to pose network reliability as a general scheme that provides a practical and efficiently computable observable to distinguish different networks. Employing this concept, we are able to demonstrate how local structural changes can impose global consequences. We further use network reliability to assess the most critical network entities which ensure a network's reliability. We investigate each of these aspects of reliability by demonstrating some example applications.