Numerical Assessment of the Percolation Threshold Using Complement Networks

Models of percolation processes on networks currently assume locally tree-like structures at low densities, and are derived exactly only in the thermodynamic limit. Finite size effects and the presence of short loops in real systems however cause a deviation between the empirical percolation threshold p_c and its model-predicted value q_c. Here we show the existence of an empirical linear relation between p_c and q_c across a large number of real and model networks. Such a putatively universal relation can then be used to correct the estimated value of q_c. We further show how to obtain a more precise relation using the concept of the complement graph, by investigating on the connection between the percolation threshold of a network and that of its complement.