Mean-field Analysis of Network Reliability with respect to Connectivity against Stochastic Node Removals*

Connectivity of networks is one of the simplest properties of graphs and has been studied in random graph theory. In theoretical computer science, connectivity is regarded as reliability of wireless communication networks. Recently, Nozaki et. al studied connectivity of random graphs against stochastic node errors as a model of reliability of wireless sensor networks with unreliable relay nodes [1]. In the model, each node is removed independently with a constant probability. The average probability over random graphs that the resultant graphs are disconnected is named a network breakdown probability. In this presentation, we demonstrate a mean-field analysis of the network breakdown probability for random graphs with unbounded average degrees. The approximation formula is applicable to random graph ensembles with any degree distribution and well approximate numerical results. In addition, the asymptotic analysis of the approximation formula reveals that the phase transition of connectivity occurs at an average degree threshold which lies in the logarithmic regime of number of nodes.
[1] T. Nozaki, T. Nakano, and T. Wadayama, IEEE Int. Symp. on Inf. Theo., pp. 481-485, 2017.