Title: Fault Tolerance of Random Graphs with respect to Connectivity: Phase Transition in Logarithmic Average Degree,
Abstract: The fault tolerance of random graphs with unbounded degrees with respect to
connectivity is investigated. It is related to the reliability of wireless
sensor networks with unreliable relay nodes. The model evaluates the network
breakdown probability that a graph is disconnected after stochastic node
removal. To establish a mean-field approximation for the model, the cavity
method for finite systems is proposed. Then the asymptotic analysis is applied.
As a result, the former enables us to obtain an approximation formula for any
number of nodes and an arbitrary and degree distribution. In addition, the
latter reveals that the phase transition occurs on random graphs with
logarithmic average degrees. Those results, which are supported by numerical
simulations, coincide with the mathematical results, indicating successful
predictions by mean-field approximation for unbounded but not dense random
graphs.