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 NVNV of boxes of size ℓℓ needed to cover all the nodes of a cellular network was found to scale as the power-law NV∼(ℓ+1)-DVNV∼(ℓ+1)-DV with a fractal dimension DV=3.53±0.26DV=3.53±0.26. We implement an alternative box-counting method in terms of the minimum number NENE 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 NENE scales with respect to ℓℓ as a power-law NE∼ℓ-DENE∼ℓ-DE with DE=2.67±0.15DE=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.