Fractality in complex networks: critical and supercritical skeletons

@misc{citeulike:635172, abstract = {Fractal scaling--a power-law behavior of the number of boxes needed to tile a given network with respect to the lateral size of the box--is studied. We introduce a new box-covering algorithm that is a modified version of the original algorithm introduced by Song et al. [Nature (London) 433, 392 (2005)]; this algorithm enables effective computation and easy implementation. Fractal networks are viewed as comprising a skeleton and shortcuts. The skeleton, embedded underneath the original network, is a special type of spanning tree based on the edge betweenness centrality; it provides a scaffold for the fractality of the network. When the skeleton is regarded as a branching tree, it exhibits a plateau in the mean branching number as a function of the distance from a root. Based on these observations, we construct a fractal network model by combining a random branching tree and local shortcuts. The scaffold branching tree can be either critical or supercritical, depending on the small-worldness of a given network. For the network constructed from the critical (supercritical) branching tree, the average number of vertices within a given box grows with the lateral size of the box according to a power-law (an exponential) form in the cluster-growing method. The distribution of box masses, i.e., the number of vertices within each box, follows a power law P\_m(M) sim M^{-eta}. The exponent eta depends on the box lateral size ell\_B. For small values of ell\_B, eta is equal to the degree exponent gamma of a given scale-free network, whereas eta approaches the exponent tau=gamma/(gamma-1) as ell\_B increases, which is the exponent of the cluster-size distribution of the random branching tree. We also study the perimeter of a given box as a function of the box mass.}, author = {Kim, J. S. and Goh, K. I. and Salvi, G. and Oh, E. and Kahng, B. and Kim, D. }, citeulike-article-id = {635172}, eprint = {cond-mat/0605324}, keywords = {complex, fractal, graphs, networks}, month = {May}, posted-at = {2007-02-23 21:02:13}, priority = {0}, title = {Fractality in complex networks: critical and supercritical skeletons}, url = {http://arxiv.org/abs/cond-mat/0605324}, year = {2006} }

TY - ELEC ID - citeulike:635172 L3 - citeulike-article-id:635172 TI - Fractality in complex networks: critical and supercritical skeletons N2 - Fractal scaling--a power-law behavior of the number of boxes needed to tile a given network with respect to the lateral size of the box--is studied. We introduce a new box-covering algorithm that is a modified version of the original algorithm introduced by Song et al. [Nature (London) 433, 392 (2005)]; this algorithm enables effective computation and easy implementation. Fractal networks are viewed as comprising a skeleton and shortcuts. The skeleton, embedded underneath the original network, is a special type of spanning tree based on the edge betweenness centrality; it provides a scaffold for the fractality of the network. When the skeleton is regarded as a branching tree, it exhibits a plateau in the mean branching number as a function of the distance from a root. Based on these observations, we construct a fractal network model by combining a random branching tree and local shortcuts. The scaffold branching tree can be either critical or supercritical, depending on the small-worldness of a given network. For the network constructed from the critical (supercritical) branching tree, the average number of vertices within a given box grows with the lateral size of the box according to a power-law (an exponential) form in the cluster-growing method. The distribution of box masses, i.e., the number of vertices within each box, follows a power law P_m(M) sim M^{-eta}. The exponent eta depends on the box lateral size ell_B. For small values of ell_B, eta is equal to the degree exponent gamma of a given scale-free network, whereas eta approaches the exponent tau=gamma/(gamma-1) as ell_B increases, which is the exponent of the cluster-size distribution of the random branching tree. We also study the perimeter of a given box as a function of the box mass. KW - complex KW - fractal KW - graphs KW - networks AU - Kim, JS AU - Goh, KI AU - Salvi, G AU - Oh, E AU - Kahng, B AU - Kim, D PY - 2006/May/12/ UR - http://arxiv.org/abs/cond-mat/0605324 ER -