Application of Network Reliability to Analyze Diffusive Processes on Graph Dynamical Systems

Moore and Shannon's reliability polynomial can be used as a global statistic to explore the behavior of diffusive processes on a graph dynamical system representing a finite sized interacting system. It depends on both the network topology and the dynamics of the process and gives the probability that the system has a particular desired property. Due to the complexity involved in evaluating the exact network reliability, the problem has been classified as a NP-hard problem. The estimation of the reliability polynomials for large graphs is feasible using Monte Carlo simulations. However, the number of samples required for an accurate estimate increases with system size. Instead, an adaptive method using Bernstein polynomials as kernel density estimators proves useful. Network reliability has a wide range of applications ranging from epidemiology to statistical physics, depending on the description of the functionality. For example, it serves as a measure to study the sensitivity of the outbreak of an infectious disease on a network to the structure of the network. It can also be used to identify important dynamics-induced contagion clusters in international food trade networks. Further, it is analogous to the partition function of the Ising model which provides insights to the interpolation between the low and high temperature limits.