Fault tolerance of random graphs with respect to connectivity: Mean-field approximation for semidense random graphs

The fault tolerance of random graphs with unbounded degrees with respect to connectivity is investigated, which relates 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, we propose the cavity method for finite systems. The analysis enables us to obtain an approximation formula for random graphs with any number of nodes and an arbitrary degree distribution. In addition, its asymptotic analysis reveals that the phase transition occurs in semidense random graphs whose average degree grows logarithmically. These results, which are supported by numerical simulations, coincide with the mathematical results, indicating successful predictions by the mean-field approximation for unbounded but not dense random graphs.

Figure 1

Network breakdown probability $P_{\langle k\rangle ,n}\left(\epsilon \right)$ as a function of node breakdown probability $\epsilon$ for regular random graphs with $n$ nodes of which the degree is $\langle k\rangle ={log}_{2}n$. Solid lines represent evaluations by the mean-field approximation. Symbols show numerical results averaged over ${10}^6$ randomly generated survival graphs. The vertical dashed line represents the phase transition threshold ${\epsilon }^{*}=1/2$ by asymptotic analysis.

Figure 2

Network breakdown probability $P_{\langle k\rangle ,n}\left(\epsilon \right)$ as a function of node breakdown probability $\epsilon$ for scale-free networks with $n$ nodes whose scaling factor is $\gamma$ and minimum degree is $\tilde{k}=(\gamma -2)/(\gamma -1){log}_{2}n$. Lines represent evaluations by the mean-field approximation. Symbols show numerical results averaged over ${10}^4$ randomly generated survival graphs.

Figure 3

Phase transition threshold ${\epsilon }^{*}$ as a function of a factor of the average degree $\langle k\rangle$ given as $d=\langle k\rangle /lnn$.