Exploring self-similarity of complex cellular networks: The edge-covering method with simulated annealing and log-periodic sampling

Song et al. [Self-similarity of complex networks, Nature 433 (2005) 392–395] have recently used a version of the box-counting method, called the node-covering method, to quantify the self-similar properties of 43 cellular networks: the minimal number NV of boxes of size ℓ needed to cover all the nodes of a cellular network was found to scale as the power-law NV∼(ℓ+1)-DV with a fractal dimension DV=3.53±0.26. We implement an alternative box-counting method in terms of the minimum number NE of edge-covering boxes which is well-suited to cellular networks, where the search over different covering sets is performed with the simulated annealing algorithm. The method also takes into account a possible discrete scale symmetry to optimize the sampling rate and minimize possible biases in the estimation of the fractal dimension. With this methodology, we find that NE scales with respect to ℓ as a power-law NE∼ℓ-DE with DE=2.67±0.15 for the 43 cellular networks previously analyzed by Song et al. [Self-similarity of complex networks, Nature 433 (2005) 392–395]. Bootstrap tests suggest that the analyzed cellular networks may have a significant log-periodicity qualifying a discrete hierarchy with a scaling ratio close to 2.