{'fraction_non_alphanumeric': 0.036159065532938246, 'fraction_numerical': 0.00848578545048527, 'mean_word_length': 4.358122411412793, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fractal and Transfractal Scale-Free Networks

Self-similarity is a property of fractal structures, a concept introduced by Mandelbrot and one of the fundamental mathematical results of the 20th century. The importance of fractal geometry stems from the fact that these structures were recognized in numerous examples in Nature, from the coexistence of liquid/gas at the critical point of evaporation of water, to snowflakes, to the tortuous coastline of the Norwegian fjords, to the behavior of many complex systems such as economic data, or the complex patterns of human agglomeration. Here we review the recent advances in self-similarity of complex networks and its relation to transport, diffusion, percolations and other topological properties such us degree distribution, modularity, and degree-degree correlations.


DEFINITION OF THE SUBJECT AND ITS IMPORTANCE
The explosion in the study of complex networks during the last decade has offered a unique view in the structure and behavior of a wide range of systems, spanning many different disciplines [1]. The importance of complex networks lies mainly in their simplicity, since they can represent practically any system with interactions in a unified way by stripping complicated details and retaining the main features of the system. The resulting networks include only nodes, representing the interacting agents and links, representing interactions. The term 'interactions' is used loosely to describe any possible way that causes two nodes to form a link. Examples can be real physical links, such as the wires connecting computers in the Internet or roads connecting cities, or alternatively they may be virtual links, such as links in WWW homepages or acquaintances in societies, where there is no physical medium actually connecting the nodes.
The field was pioneered by the famous mathematician P. Erdős many decades ago, when he greatly advanced graph theory [2]. The theory of networks would have perhaps remained a problem of mathematical beauty, if it was not for INTRODUCTION Self-similarity is a property of fractal structures, a concept introduced by Mandelbrot and one of the fundamental mathematical results of the 20th century [14,15,20]. The importance of fractal geometry stems from the fact that these structures were recognized in numerous examples in Nature, from the coexistence of liquid/gas at the critical point of evaporation of water [21,22,23], to snowflakes, to the tortuous coastline of the Norwegian fjords, to the behavior of many complex systems such as economic data, or the complex patterns of human agglomeration [14,15].
Typically, real world scale-free networks exhibit the small-world property [1], which implies that the number of nodes increases exponentially with the diameter of the network, rather than the power-law behavior expected for self-similar structures. For this reason complex networks were believed to not be length-scale invariant or self-similar.
In 2005, C. Song, S. Havlin and H. Makse presented an approach to analyze complex networks, that reveals their self-similarity [17]. This result is achieved by the application of a renormalization procedure which coarse-grains the system into boxes containing nodes within a given size [17,24]. As a result, a power-law relation between the number of boxes needed to cover the network and the size of the box is found, defining a finite self-similar exponent. These fundamental properties, which are shown for the WWW, cellular and protein-protein interaction networks, help to understand the emergence of the scale-free property in complex networks. They suggest a common self-organization dynamics of diverse networks at different scales into a critical state and in turn bring together previously unrelated fields: the statistical physics of complex networks with renormalization group, fractals and critical phenomena.

FRACTALITY IN REAL-WORLD NETWORKS
The study of real complex networks has revealed that many of them share some fundamental common properties. Of great importance is the form of the degree distribution for these networks, which is unexpectedly wide. This means that the degree of a node may assume values that span many decades. Thus, although the majority of nodes have a relatively small degree, there is a finite probability that a few nodes will have degree of the order of thousands or even millions. Networks that exhibit such a wide distribution P (k) are known as scale-free networks, where the term refers to the absence of a characteristic scale in the degree k. This distribution very often obeys a power-law form with a degree exponent γ, usually in the range 2 < γ < 4 [25], A more generic property, that is usually inherent in scale-free networks but applies equally well to other types of networks, such as in Erdős-Rényi random graphs, is the small-world feature. Originally discovered in sociological studies [26], it is the generalization of the famous 'six degrees of separation' and refers to the very small network diameter. Indeed, in small-world networks a very small number of steps is required to reach a given node starting from any other node. Mathematically this is expressed by the slow (logarithmic) increase of the average diameter of the network,l, with the total number of nodes N ,l ∼ ln N , where ℓ is the shortest distance between two nodes and defines the distance metric in complex networks [2,25,27,28], namely, where ℓ 0 is a characteristic length. These network characteristics have been shown to apply in many empirical studies of diverse systems [1,6,25]. The simple knowledge that a network has the scale-free and/or small-world property already enables us to qualitatively recognize many of its basic properties. However, structures that have the same degree exponents may still differ in other aspects [12]. For example, a question of fundamental importance is whether scale-free networks are also self-similar or fractals. The illustrations of scale-free networks (see e.g. Figs. 1 and 2b) seem to resemble traditional fractal objects. Despite this similarity, Eq. (2) definitely appears to contradict a basic property of fractality: fast increase of the diameter with the system size. Moreover, a fractal object should be self-similar or invariant under a scale transformation, which is again not clear in the case of scale-free networks where the scale has necessarily limited range. So, how is it even possible that fractal scale-free networks exist? In the following, we will see how these seemingly contradictory aspects can be reconciled.

Fractality and Self-Similarity
The classical theory of self-similarity requires a power-law relation between the number of nodes N and the diameter of a fractal object ℓ [13,16]. The fractal dimension can be calculated using either box-counting or cluster-growing techniques [14]. In the first method the network is covered with N B boxes of linear size ℓ B . The fractal dimension or box dimension d B is then given by [15]: In the second method, instead of covering the network with boxes, a random seed node is chosen and nodes centered at the seed are grown so that they are separated by a maximum distance ℓ. The procedure is then repeated by choosing many seed nodes at random and the average "mass" of the resulting clusters, M c (defined as the number of nodes in the cluster) is calculated as a function of ℓ to obtain the following scaling: defining the fractal cluster dimension d f [15]. If we use Eq. (4) for a small-world network, then Eq. (2) readily implies that d f = ∞. In other words, these networks cannot be characterized by a finite fractal dimension, and should be regarded as infinite-dimensional objects. If this were true, though, local properties in a part of the network would not be able to represent the whole system. Still, it is also well established that the scale-free nature is similar in different parts of the network. Moreover, a graphical representation of real-world networks allows us to see that those systems seem to be built by attaching (following some rule) copies of itself. The answer lies in the inherent inhomogeneity of the network. In the classical case of a homogeneous system (such as a fractal percolation cluster) the degree distribution is very narrow and the two methods described above are fully equivalent, because of this local neighborhood invariance. Indeed, all boxes in the box-covering method are statistically similar with each other as well as with the boxes grown when using the cluster-growing technique, so that Eq. (4) can be derived from Eq. (3) and d B = d f .
In inhomogeneous systems, though, the local environment can vary significantly. In this case, Eqs. (3) and (4) are no longer equivalent. If we focus on the box-covering technique then we want to cover the entire network with the minimum possible number of boxes N B (ℓ B ), where the distance between any two nodes that belong in a box is smaller than ℓ B . An example is shown in Fig. 2a using a simple 8-node network. After we repeat this procedure for different values of ℓ B we can plot N B vs ℓ B .
When the box-covering method is applied to real large-scale networks, such us the WWW [25] (http://www.nd.edu/∼networks), the network of protein interaction of H. sapiens and E. coli [29,30] and several cellular networks [31,32], then they follow Eq. (3) with a clear power-law, indicating the fractal nature of these systems (Figs. 3a, 3b, 3c). On the other hand when the method is applied to other real world networks such us the Internet [33] or the Barabási-Albert network [34], they do not satisfy Eq. (3), which manifests that these networks are not fractal.
The reason behind the discrepancy in the fractality of homogeneous and inhomogeneous systems can be better clarified studying the mass of the boxes. For a given ℓ B value, the average mass of a box M B (ℓ B ) is as also verified in Fig. 3 for several real-world networks. On the other hand, the average performed in the cluster growing method (averaging over single boxes without tiling the system) gives rise to an exponential growth of the mass in accordance with the small-world effect, Eq. (2). Correspondingly, the probability distribution of the mass of the boxes M B using box-covering is very broad, while the cluster-growing technique leads to a narrow probability distribution of M c . The topology of scale-free networks is dominated by several highly connected hubs-the nodes with the largest degree-implying that most of the nodes are connected to the hubs via one or very few steps. Therefore, the average performed in the cluster growing method is biased; the hubs are overrepresented in Eq. (6) since almost every node is a neighbor of a hub, and there is always a very large probability of including the same hubs in all clusters. On the other hand, the box covering method is a global tiling of the system providing a flat average over all the nodes, i.e. each part of the network is covered with an equal probability. Once a hub (or any node) is covered, it cannot be covered again.
In conclusion, we can state that the two dominant methods that are routinely used for calculations of fractality and give rise to Eqs. (3) and (4) are not equivalent in scale-free networks, but rather highlight different aspects: box covering reveals the self-similarity, while cluster growth reveals the small-world effect. The apparent contradiction is due to the hubs being used many times in the latter method.
The apparent contradiction between the small-world and fractal properties, as expressed through Eqs. 2 and 3 can be explained as follows. Scale-free networks can be classified into three groups: (i) pure fractal, (ii) pure small-world and (iii) a mixture between fractal and small-world. (i) A fractal network satisfies Eq. 3 at all scales, meaning that a b FIG. 2: The renormalization procedure for complex networks. a, Demonstration of the method for different ℓB and different stages in a network demo. The first column depicts the original network. The system is tiled with boxes of size ℓB (different colors correspond to different boxes). All nodes in a box are connected by a minimum distance smaller than the given ℓB. For instance, in the case of ℓB = 2, one identifies four boxes which contain the nodes depicted with colors red, orange, white, and blue, each containing 3, 2, 1, and 2 nodes, respectively.
Then each box is replace by a single node; two renormalized nodes are connected if there is at least one link between the unrenormalized boxes. Thus we obtain the network shown in the second column. The resulting number of boxes needed to tile the network, NB (ℓB), is plotted in Fig. 4 versus ℓB to obtain dB as in Eq. (3). The renormalization procedure is applied again and repeated until the network is reduced to a single node (third and fourth columns for different ℓB). b, Three stages in the renormalization scheme applied to the entire WWW. We fix the box size to ℓB = 3 and apply the renormalization for four stages. This corresponds, for instance, to the sequence for the network demo depicted in the second row in part a of this figure. We color the nodes in the web according to the boxes to which they belong.
for any value of ℓ B , the number of boxes always follows a power-law (examples are shown in Fig. 3a, 3b, 3c). (ii) When a network is a pure small-world, it never satisfies Eq. 3. Instead, N B follows an exponential decay with ℓ B and the network cannot be regarded as fractal. Figs. 3d and 3e show two examples of pure small-world networks. (iii) In the case of mixture between fractal and small-world, Eq. 3 is satisfied up to some cut-off value of ℓ B , above which the fractality breaks down and the small-world property emerges. The small-world property is reflected in the plot of N B vs. ℓ B as an exponential cut-off for large ℓ B . We can also understand the coexistence of the small-world property and the fractality through a more intuitive approach. In a pure fractal network the length of a path between any pair of nodes scales as a power-law with the number of nodes in the network. Therefore, the diameter L also follows a power-law, L ∼ N 1/dB . If one adds a few shortcuts (links between randomly chosen nodes), many paths in the network are drastically shortened and the small-world property emerges as L ∼ Log N . In spite of this fact, for shorter scales, ℓ B ≪ L, the network still behaves as a fractal. In this sense, we can say that globally the network is small-world, but locally (for short scales) the network behaves as a fractal. As more shortcuts are added, the cut-off in a plot of N B vs. ℓ B appears for smaller ℓ B , until the network becomes a pure small-world for which all paths lengths increase logarithmically with N . The reasons why certain networks have evolved towards a fractal or non-fractal structure will be described later, together with models and examples that provide additional insight into the processes involved.

Renormalization
Renormalization is one of the most important techniques in modern Statistical Physics [35,36,37]. The idea behind this procedure is to continuously create smaller replicas of a given object, retaining at the same time the essential structural features, and hoping that the coarse-grained copies will be more amenable to analytic treatment.
The idea for renormalizing the network emerges naturally from the concept of fractality described above. If a network is self-similar, then it will look more or less the same under different scales. The way to observe these different length-scales is based on renormalization principles, while the criterion to decide on whether a renormalized structure retains its form is the invariance of the main structural features, expressed mainly through the degree distribution.
The method works as follows. Start by fixing the value of ℓ B and applying the box-covering algorithm in order to cover the entire network with boxes (see Appendix). In the renormalized network each box is replaced by a single node and two nodes are connected if there existed at least one connection between the two corresponding boxes in the original network. The resulting structure represents the first stage of the renormalized network. We can apply the same procedure to this new network, as well, resulting in the second renormalization stage network, and so on until we are left with a single node.
The second column of the panels in Fig. 2a shows this step in the renormalization procedure for the schematic network, while Fig. 2b shows the results for the same procedure applied to the entire WWW for ℓ B = 3.
The renormalized network gives rise to a new probability distribution of links, P (k ′ ) (we use a prime ′ to denote quantities in the renormalized network). This distribution remains invariant under the renormalization: Here, we present the basic scaling relations that characterize renormalizable networks. The degree k ′ of each node in the renormalized network can be seen to scale with the largest degree k in the corresponding original box as This equation defines the scaling transformation in the connectivity distribution. Empirically, it was found that the scaling factor s(< 1) scales with ℓ B with a new exponent, d k , as This scaling is verified for many networks, as shown in Fig. 4a. The exponents γ, d B , and d k are not all independent from each other. The proof starts from the density balance equation n(k)dk = n ′ (k ′ )dk ′ , where n(k) = N P (k) is the number of nodes with degree k and n ′ (k ′ ) = N ′ P (k ′ ) is the number of nodes with degree k ′ after the renormalization (N ′ is the total number of nodes in the renormalized network). Substituting Eq. (8) leads to N ′ = s γ−1 N . Since the total number of nodes in the renormalized network is the number of boxes needed to cover the unrenormalized network at any given ℓ B we have the identity N ′ = N B (ℓ B ). Finally, from Eqs. (3) and (9) one obtains the relation between the three indexes The use of Eq. (10) yields the same γ exponent as that obtained in the direct calculation of the degree distribution. The significance of this result is that the scale-free properties characterized by γ can be related to a more fundamental length-scale invariant property, characterized by the two new indexes d B and d k .
We have seen, thus, that concepts introduced originally for the study of critical phenomena in statistical physics, are also valid in the characterization of a different class of phenomena: the topology of complex networks. A large number of scale-free networks are fractals and an even larger number remain invariant under a scale-transformation. The influence of these features on the network properties will be delayed until the sixth chapter, after we introduce some algorithms for efficient numerical calculations and two theoretical models that give rise to fractal networks.

MODELS: DETERMINISTIC FRACTAL AND TRANSFRACTAL NETWORKS
The first model of a scale-free fractal network was presented in 1979 when N. Berker and S. Ostlund [38] proposed a hierarchical network that served as an exotic example where renormalization group techniques yield exact results, including the percolation phase transition and the q → 1 limit of the Potts model. Unfortunately, in those days the importance of the power-law degree distribution and the concept of fractal and non-fractal complex networks were not known. Much work has been done on these types of hierarchical networks. For example, in 1984, M. Kaufman and R. Griffiths made use of Berker and Ostlund's model to study the percolation phase transition and its percolation exponents [39,40,41].
Since the late 90's, when the importance of the power-law degree distribution was first shown [1] and after the finding of C. Song, S. Havlin and H. Makse [17], many hierarchical networks that describe fractality in complex networks have been proposed. These artificial models are of great importance since they provide insight into the origins and fundamental properties that give rise to the fractality and non-fractality of networks.

The Song-Havlin-Makse Model
The correlations between degrees in a network [42,43,44,45] are quantified through the probability P (k 1 , k 2 ) that a node of degree k 1 is connected to another node of degree k 2 . In Fig. 5 we can see the degree correlation profile R(k 1 , k 2 ) = P (k 1 , k 2 )/P r (k 1 , k 2 ) of the cellular metabolic network of E. coli [46] (known to be a fractal network) and for the Internet at the router level [47] (a non-fractal network), where P r (k 1 , k 2 ) is obtained by randomly swapping the links without modifying the degree distribution. Fig. 5 shows a dramatic difference between the two networks. The network of E. coli, that is a fractal network, present an anti-correlation of the degrees (or dissasortativity [42,43]), which means that mostly high degree nodes are linked to low degree nodes. This property leads to fractal networks. On the other hand, the Internet exhibits a high correlation between degrees leading to a non-fractal network.
With this idea in mind, in 2006 C. Song, S. Havlin and H. Makse presented a model that elucidates the way new nodes must be connected to the old ones in order to build a fractal, a non-fractal network, or a mixture between fractal and non-fractal network [18]. This model shows that, indeed, the correlations between degrees of the nodes are a determinant factor for the fractality of a network. This model was later extended [48] to allow loops in the network, while preserving the self-similarity and fractality properties. The algorithm is as follows (see Fig. 6): In generation n = 0, start with two nodes connected by one link. Then, generation n + 1 is obtained recursively by attaching m new nodes to the endpoints of each link l of generation n. In addition, with probability e remove link l and add x new links connecting pairs of new nodes attached to the endpoints of l.
The degree distribution, diameter and fractal dimension can be easily calculated. For example, if e = 1 (pure fractal network), the degree distribution follows a power-law P (k) ∼ k −γ with exponent γ = 1 + log(2m + x)/log m and the fractal dimension is d B = log(2m + x)/log m. The diameter L scales, in this case, as power of the number of nodes as L ∼ N 1/dB [18,24]. Later, in Section "Properties of Fractal and Transfractal Networks", several topological properties are shown for this model network.  [38] and the pseudo-fractal network of Dorogovstev, Goltsev and Mendes [49] and that, by appropriately varying its two parameters u and v, leads to either fractal networks or non-fractal networks [50,51]. The algorithm to build the (u, v)-flowers is the following: In generation n = 1 one starts with a cycle graph (a ring) consisting of u + v ≡ w links and nodes (other choices are possible). Then, generation n + 1 is obtained recursively by replacing each link by two parallel paths of u and v links long. Without loss of generality, u ≤ v. Examples of (1, 3)-and (2, 2)-flowers are shown in Fig. 7. The DGM network corresponds to the special case of u = 1 and v = 2 and the Berker and Ostlund model corresponds to u = 2 and v = 2.
An essential property of the (u, v)-flowers is that they are self-similar, as evident from an equivalent method of construction: to produce generation n + 1, make w = u + v copies of the net in generation n and join them at the hubs. The number of links of a (u, v)-flower of generation n is and the number of nodes is The degree distribution of the (u, v)-flowers can also be easily obtained since by construction, (u, v)-flowers have only nodes of degree k = 2 m , m = 1, 2, . . . , n. As in the DGM case, (u, v)-flowers follow a scale-free degree distribution, Recursive scale-free trees may be defined in analogy to the flower nets. If v is even, one obtains generation n + 1 of a (u, v)-tree by replacing every link in generation n with a chain of u links, and attaching to each of its endpoints chains of v/2 links. Fig. 8 shows how this works for the (1, 2)-tree. If v is odd, attach to the endpoints (of the chain of u links) chains of length (v ± 1)/2. The trees may be also constructed by successively joining w replicas at the appropriate hubs, and they too are self-similar. They share many of the fundamental scaling properties with (u, v)-flowers: Their degree distribution is also scale-free, with the same degree exponent as (u, v)-flowers.
The self-similarity of (u, v)-flowers, coupled with the fact that different replicas meet at a single node, makes them amenable to exact analysis by renormalization techniques. The lack of loops, in the case of (u, v)-trees, further simplifies their analysis [38,50,51,52].

Dimensionality of the (u, v)-flowers
There is a vast difference between (u, v)-nets with u = 1 and u > 1. If u = 1 the diameter L n of the n-th generation flower scales linearly with n. For example, L n for the (1, 2)-flower [49] and L n = 2n for the (1, 3)-flower. It is easy to see that the diameter of the (1, v)-flower, for v odd, is L n = (v − 1)n + (3 − v)/2, and, in general one can show that L n ∼ (v − 1)n.
For u > 1, however, the diameter grows as a power of n. For example, for the (2, 2)-flower we find L n = 2 n , and, more generally, the diameter satisfies L n ∼ u n . To summarize, Similar results are quite obvious for the case of (u, v)-trees, where L n ∼ vn u = 1, u n u > 1, trees.
Since N n ∼ (u + v) n [Eq. (12)], we can recast these relations as Thus, (u, v)-nets are small world only in the case of u = 1. For u > 1, the diameter increases as a power of N , just as in finite-dimensional objects, and the nets are in fact fractal . For u > 1, the change of mass upon the rescaling of length by a factor b is where d B is the fractal dimension [16]. In this case, N (uL) = (u + v)N (L), so

Transfinite Fractals
Small world nets, such as (1, v)-nets, are infinite-dimensional. Indeed, their mass (N , or M ) increases faster than any power (dimension) of their diameter. Also, note that a naive application of (4) to u → 1 yields d f → ∞. In the case of (1, v)-nets one can use their weak self-similarity to define a new measure of dimensionality,d f , characterizing how mass scales with diameter: Instead of a multiplicative rescaling of length, L → bL, a slower additive mapping, L → L + ℓ, that reflects the small world property is considered. Because the exponentd f usefully distinguishes between different graphs of infinite dimensionality,d f has been termed the transfinite fractal dimension of the network. Accordingly, objects that are self-similar and have infinite dimension (but finite transfinite dimension), such as the (1, v)-nets, are termed transfinite fractals, or transfractals, for short. For (1, v)-nets, we see that upon 'zooming in' one generation level the mass increases by a factor of w = 1 + v, while the diameter grows from L to L + v − 1 (for flowers), or to L + v (trees). Hence their transfractal dimension is There is some arbitrariness in the selection of e as the base of the exponential in the definition (19). However the base is inconsequential for the sake of comparison between dimensionalities of different objects. Also, scaling relations between various transfinite exponents hold, irrespective of the choice of base: consider the scaling relation of Eq. 10 valid for fractal scale-free nets of degree exponent γ [17,18]. For example, in the fractal (u, v)-nets (with u > 1) renormalization reduces lengths by a factor b = u and all degrees are reduced by a factor of 2, so b d k = 2. Thus d k = ln 2/ ln u, and since d B = ln(u + v)/ ln u and γ = 1 + ln(u + v)/ ln 2, as discussed above, the relation (10) is indeed satisfied.
For transfractals, renormalization reduces distances by an additive length, ℓ, and we express the self-similarity manifest in the degree distribution as whered k is the transfinite exponent analogous to d k . Renormalization of the transfractal (1, v)-nets reduces the link lengths by ℓ = v − 1 (for flowers), or ℓ = v (trees), while all degrees are halved. Thus, Along with (20), this result confirms that the scaling relation is valid also for transfractals, and regardless of the choice of base. A general proof of this relation is practically identical to the proof of (??) [17], merely replacing fractal with transfractal scaling throughout the argument. For scale-free transfractals, following m = L/ℓ renormalizations the diameter and mass reduce to order one, and the scaling (19) implies L ∼ mℓ, N ∼ e mℓd f , so that in accordance with their small world property. At the same time the scaling (21) implies K ∼ e mℓd k , or K ∼ Nd k /d f . Using the scaling relation (22), we rederive K ∼ N 1/(γ−1) , which is indeed valid for scale-free nets in general , be they fractal or transfractal.

PROPERTIES OF FRACTAL AND TRANSFRACTAL NETWORKS
The existence of fractality in complex networks immediately calls for the question of what is the importance of such a structure in terms of network properties. In general, most of the relevant applications seem to be modified to a larger or lesser extent, so that fractal networks can be considered to form a separate network sub-class, sharing the main properties resulting from the wide distribution of regular scale-free networks, but at the same time bearing novel properties. Moreover, from a practical point of view a fractal network can be usually more amenable to analytic treatment.
In this section we summarize some of the applications that seem to distinguish fractal from non-fractal networks.

Modularity
Modularity is a property closely related to fractality. Although this term does not have a unique well-defined definition we can claim that modularity refers to the existence of areas in the network where groups of nodes share some common characteristics, such as preferentially connecting within this area (the 'module') rather than to the rest of the network. The isolation of modules into distinct areas is a complicated task and in most cases there are many possible ways (and algorithms) to partition a network into modules.
Although networks with significant degree of modularity are not necessarily fractals, practically all fractal networks are highly modular in structure. Modularity naturally emerges from the effective 'repulsion' between hubs. Since the hubs are not directly connected to each other, they usually dominate their neighborhood and can be considered as the 'center of mass' for a given module. The nodes surrounding hubs are usually assigned to this module.
The renormalization property of self-similar networks is very useful for estimating how modular a given network is, and especially for how this property is modified under varying scales of observation. We can use a simple definition for modularity M , based on the idea that the number of links connecting nodes within a module, L in i , is higher than the number of link connecting nodes in different modules, L out i . For this purpose, the boxes that result from the box-covering method at a given length-scale ℓ B are identified as the network modules for this scale. This partitioning assumes that the minimization of the number of boxes corresponds to an increase of modularity, taking advantage of the idea that all nodes within a box can reach each other within less than ℓ B steps. This constraint tends to assign the largest possible number of nodes in a given neighborhood within the same box, resulting in an optimized modularity function.
A definition of the modularity function M that takes advantage of the special features of the renormalization process is, thus, the following [48]: where the sum is over all the boxes. The value of M through Eq. (23) for a given ℓ B value is of small usefuleness on its own, though. We can gather more information on the network structure if we measure M for different values of ℓ B . If the dependence of M on ℓ B has the form of a power-law, as if often the case in practice, then we can define the modularity exponent d M through The exponent d M carries the important information of how modularity scales with the length, and separates modular from non-modular networks. The value of d M is easy to compute in a d-dimensional lattice, since the number of links within any module scales with its bulk, as L in i ∼ ℓ d B and the number of links outside the module scale with the length of its interface, i.e. L out i ∼ ℓ d−1 B . So, the resulting scaling is M ∼ ℓ B i.e. d M = 1. This is also the borderline value that separates non-modular structures (d M < 1) from modular ones (d M > 1).
For the Song-Havlin-Makse fractal model introduced in the previous section, a module can be identified as the neighborhood around a central hub. In the simplest version with x = 1, the network is a tree, with well-defined modules. Larger values of x mean that a larger number of links are connecting different modules, creating more loops and 'blurring' the discreteness of the modules, so that we can vary the degree of modularity in the network. For this model, it is also possible to analytically calculate the value of the exponent d M .
During the growth process at step t, the diameter in the network model increases multiplicatively as L(t+1) = 3L(t). The number of links within a module grows with 2m+x (each node on the side of one link gives rise to m new links and x extra links connect the new nodes), while the number of links pointing out of a module is by definition proportional to x. Thus, the modularity M (ℓ B ) of a network is proportional to (2m + x)/x. Eq. (24) can then be used to calculate d M for the model: which finally yields So, in this model the important quantity that determines the degree of modularity in the system is the ratio of the growth parameters m/x. Most of the real-life networks that have been measured display some sort of modular character, i.e. d M > 1, although many of them have values very close to 1. Only in a few cases we have observed exponents d M < 1. Most interesting is, though, the case of d M values much larger than 1, where a large degree of modularity is observed and this trend is more pronounced for larger length-scales.
The importance of modularity as described above can be demonstrated in biological networks. There, it has been suggested that the boxes may correspond to functional modules and in protein interaction networks, for example, there may be an evolution drive of the system behind the development of its modular structure.

Robustness
Shortly after the discovery of the scale-free property, the first important application of their structure was perhaps their extreme resilience to removal of random nodes [7,9,51,53,54,55,56]. At the same time such a network was found to be quite vulnerable to an intentional attack, where nodes are removed according to descreasing order of their degree [8,57]. The resilience of a network is usually quantified through the size of the largest remaining connected cluster S max (p), when a fraction p of the nodes has been removed according to a given strategy. At a critical point p c where this size becomes equal to S max (p c ) ≃ 0, we consider that the network has been completely disintegrated. For the random removal case, this threshold is p c ≃ 1, i.e. practically all nodes need to be destroyed. In striking contrast, for intentional attacks p c is in general of the order of only a few percent, although the exact value depends on the system details.
Fractality in networks considerably strengthens the robustness against intentional attacks, compared to non-fractal networks with the same degree exponent γ. In Fig. 9 the comparison between two such networks clearly shows that the critical fraction p c increases almost 4 times from p c ≃ 0.02 (non-fractal topology) to p c ≃ 0.09 (fractal topology). These networks have the same γ exponent, the same number of links, number of nodes, number of loops and the same clustering coefficient, differing only in whether hubs are directly connected to each other. The fractal property, thus, provides a way of increasing resistance against the network collapse, in the case of a targeted attack.
The main reason behind this behavior is the dispersion of hubs in the network. A hub is usually a central node that helps other nodes to connect to the main body of the system. When the hubs are directly connected to each other, this central core is easy to destroy in a targeted attack leading to a rapid collapse of the network. On the contrary, isolating the hubs into different areas helps the network to retain connectivity for longer time, since destroying the hubs now is not similarly catastrophic, with most of the nodes finding alternative paths through other connections.
The advantage of increased robustness derived from the combination of modular and fractal network character, may provide valuable hints on why most biological networks have evolved towards a fractal architecture (better chance of survival against lethal attacks).

Degree Correlations
We have already mentioned the importance of hub-hub correlations or anti-correlations in fractality. Generalizing this idea to nodes of any degree, we can ask what is the joint degree probability P (k 1 , k 2 ) that a randomly chosen link connects two nodes with degree k 1 and k 2 , respectively. Obviously, this is a meaningful question only for networks with a wide degree distribution, otherwise the answer is more or less trivial with all nodes having similar degrees. A similar and perhaps more useful quantity is the conditional degree probability P (k 1 |k 2 ), defined as the probability that a random link from a node having degree k 2 points to a node with degree k 1 . In general, the following balance condition is satisfied It is quite straightforward to calculate P (k 1 |k 2 ) for completely uncorrelated networks. In this case, P (k 1 |k 2 ) does not depend on k 2 , and the probability to chose a node with degree k 1 becomes simply P (k 1 |k 2 ) = k 1 P (k 1 )/ k 1 . In the case where degree-degree correlations are present, though, the calculation of this function is very difficult, even when restricting ourselves to a direct numerical evaluation, due to the emergence of huge fluctuations. We can still estimate this function, though, using again the self-similarity principle. If we consider that the function P (k 1 , k 2 ) remains invariant under the network renormalization scheme described above, then it is possible to show that and similarly In the above equations we have also introduced the correlation exponent ǫ, which characterizes the degree of correlations in a network. For example, the case of uncorrelated networks is described by the value ǫ = γ − 1.
The exponent ǫ can be measured quite accurately using an appropriate quantity. For this purpose, we can introduce a measure such as which estimates the probability that a node with degree k has neighbors with degree larger than bk, and b is an arbitrary parameter that has been shown not to influence the results. It is easy to show that This relation allows us to estimate ǫ for a given network, after calculating the quantity E b (k) as a function of k.
The above discussion can be equally applied to both fractal and non-fractal networks. If we restrict ourselves to fractal networks, then we can develop our theory a bit further. If we consider the probability E(ℓ B ) that the largest degree node in each box is connected directly with the other largest degree nodes in other boxes (after optimally covering the network), then this quantity scales as a power law with ℓ B : where d e is a new exponent describing the probability of hub-hub connection [18]. The exponent ǫ, which describes correlations over any degree, is related to d e , which refers to correlations between hubs only. The resulting relation is For an infinite fractal dimension d B → ∞, which is the onset of non-fractal networks that cannot be described by the above arguments, we have the limiting case of ǫ = 2. This value separates fractal from non-fractal networks, so that fractality is indicated by ǫ > 2. Also, we have seen that the line ǫ = γ − 1 describes networks for which correlations are minimal. Measurements of many real-life networks have verified the above statements, where networks with ǫ > 2 having been clearly characterized as fractals with alternate methods. All non-fractal networks have values of ǫ < 2 and the distance from the ǫ = γ − 1 line determines how much stronger or weaker the correlations are, compared to the uncorrelated case. In short, using the self-similarity principle makes it possible to gain a lot of insight on network correlations, a notoriously difficult task otherwise. Furthermore, the study of correlations can be reduced to the calculation of a single exponent ǫ, which is though capable of delivering a wealth of information on the network topological properties.

Diffusion and Resistance
Scale-free networks have been described as objects of infinite dimensionality. For a regular structure this statement would suggest that one can simply use the known diffusion laws for d = ∞. Diffusion on scale-free structures, however, is much harder to study, mainly due to the lack of translational symmetry in the system and different local environments. Although exact results are still not available, the scaling theory on fractal networks provides the tools to better understand processes, such as diffusion and electric resistance.
In the following, we describe diffusion through the average first-passage time T AB , which is the average time for a diffusing particle to travel from node A to node B. At the same time, assuming that each link in the network has an electrical resistance of 1 unit, we can describe the electrical properties through the resistance between the two nodes A and B, R AB .
The connection between diffusion (first-passage time) and electric networks has long been established in homogeneous systems. This connection is usually expressed through the Einstein relation [16]. The Einstein relation is of great importance because it connects a static quantity R AB with a dynamic quantity T AB . In other words, the behavior of a diffusing particle can be inferred by simply having knowledge of a static topological property of the network.
In any renormalizable network the scaling of T and R follow the form: where T ′ (R ′ ) and T (R) are the first-passage time (resistance) for the renormalized and original networks, respectively. The dynamical exponents d w and ζ characterize the scaling in any lattice or network that remains invariant under renormalization. The Einstein relation relates these two exponents through the dimensionality of the substrate d B , according to: The validity of this relation in inhomogeneous complex networks, however, is not yet clear. Still, in fractal and transfractal networks there are many cases where this relation has been proved to be valid, hinting towards a wider applicability. For example, in Refs. [50,52] it has been shown that the Einstein Relation [16] in (u, v)-flowers and (u, v)-trees is valid for any u and v, that is for both fractal and transfractal networks. In general, in terms of the scaling theory we can study diffusion and resistance (or conductance) in a similar manner [48].
Because of the highly inhomogeneous character of the structure, though, we are interested in how these quantities behave as a function of the end-node degrees k 1 and k 2 when they are separated by a given distance ℓ. Thus, we are  looking for the full dependence of T (ℓ; k 1 , k 2 ) and R(ℓ; k 1 , k 2 ). Obviously, for lattices or networks with narrow degree distribution there is no degree dependence and those results should be a function of ℓ only. For self-similar networks, we can rewrite Eq. (34) above as where we have taken into account Eq. (3). This approach offers the practical advantage that the variation of N ′ /N is larger than the variation of ℓ B , so that the exponents calculation can be more accurate. To calculate these exponenets, we fix the box size ℓ B and we measure the diffusion time T and resistance R between any two points in a network before and after renormalization. If for every such pair we plot the corresponding times and resistances in T ′ vs T and R ′ vs R plots, as shown in Fig. 10, then all these points fall in a narrow area, suggesting a constant value for the ratio T ′ /T over the entire network. Repeating this procedure for different ℓ B values yields other ratio values. The plot of these ratios vs N ′ /N (Fig. 11) finally exhibits a power-law dependence, verifying Eq. (36). We can then easily calculate the exponents d w and ζ from the slopes in the plot, since the d B exponent is already known through the standard box-covering methods. It has been shown that the results for many different networks are consistent, within statistical error, with the Einstein relation [48,50]. The dependence on the degrees k 1 , k 2 and the distance ℓ can also be calculated in a scaling form using the selfsimilarity properties of fractal networks. After renormalization, a node with degree k in a given network, will have a degree k ′ = ℓ −d k B k according to Eq. (9). At the same time all distances ℓ are scaled down according to ℓ ′ = ℓ/ℓ B . This means that Eqs. (36) can be written as Substituting the renormalized quantities we get: The above equation holds for all values of ℓ B , so we can select this quantity to be ℓ B = k Concerning the structural aspects of fractal networks, we have described that in most networks the degree distribution P (k), the joint degree distribution P (k 1 , k 2 ) and a number of other quantities remain invariant under renormalization. Are there any quantities that are not invariable, and what would their importance be?
Of central importance is the relation of topological features with functionality. The optimal network covering leads to the partitioning of the network into boxes. Do these boxes carry a message other than nodes proximity? For example, the boxes could be used as an alternative definition for separated communities, and fractal methods could be used as a novel method for community detection in networks [58,59,60,61,62].
The networks that we have presented are all static, with no temporal component, and time evolution has been ignored in all our discussions above. Clearly, biological networks, the WWW, and other networks have grown (and continue to grow) from some earlier simpler state to their present fractal form. Has fractality always been there or has it emerged as an intermediate stage obeying certain evolutionary drive forces? Is fractality a stable condition or growing networks will eventually fall into a non-fractal form?
Finally, we want to know what is the inherent reason behind fractality. Of course, we have already described how hub-hub anti-correlations can give rise to fractal networks. However, can this be directly related to some underlying mechanism, so that we gain some information on the process? In general, in Biology we already have some idea on the advantages of adopting a fractal structure. Still, the question remains: why fractality exists in certain networks and not in others? Why both fractal and non-fractal networks are needed? It seems that we will be able to increase our knowledge for the network evolutionary mechanisms through fractality studies.
In conclusion, a deeper understanding of the self-similarity, fractality and transfractality of complex networks will help us analyze and better understand many fundamental properties of real-world networks.

APPENDIX: THE BOX COVERING ALGORITHMS
The estimation of the fractal dimension and the self-similar features in networks have become standard properties in the study of real-world systems. For this reason, in the last three years many box covering algorithms have been proposed [24,63]. This section presents four of the main algorithms, along with a brief discussion on the advantages and disadvantages that they offer.
Recalling the original definition of box covering by Hausdorff [13,15,64], for a given network G and box size ℓ B , a box is a set of nodes where all distances ℓ ij between any two nodes i and j in the box are smaller than ℓ B . The minimum number of boxes required to cover the entire network G is denoted by N B . For ℓ B = 1, each box encloses only 1 node and therefore, N B is equal to the size of the network N . On the other hand, is the diameter of the network plus one. The ultimate goal of a box-covering algorithm is to find the minimum number of boxes N B (ℓ B ) for any ℓ B . It has been shown that this problem belongs to the family of NP-hard problems [65], which means that the solution cannot be achieved in polynomial time. In other words, for a relatively large network size, there is no algorithm that can provide an exact solution in a reasonably short amount of time. This limitation requires treating the box covering problem with approximations, using for example optimization algorithms.

The greedy coloring algorithm
The box-covering problem can be mapped into another NP-hard problem [65]: the graph coloring problem. An algorithm that approximates well the optimal solution of this problem was presented in [24]. For an arbitrary value of ℓ B , first construct a dual network G ′ , in which two nodes are connected if the distance between them in G (the original network) is greater or equal than ℓ B . Fig. 13 shows an example of a network G which yields such a dual network G ′ for ℓ B = 3 (upper row of Fig. 13).
Vertex coloring is a well-known procedure, where labels (or colors) are assigned to each vertex of a network, so that no edge connects two identically colored vertices. It is clear that such a coloring in G ′ gives rise to a natural box covering in the original network G, in the sense that vertices of the same color will necessarily form a box since the distance between them must be less than ℓ B . Accordingly, the minimum number of boxes N B (G) is equal to the minimum required number of colors (or the chromatic number) in the dual network G ′ , χ(G ′ ).
In simpler terms, (a) if the distance between two nodes in G is greater than ℓ B these two neighbors cannot belong in the same box. According to the construction of G ′ , these two nodes will be connected in G ′ and thus they cannot have the same color. Since they have a different color they will not belong in the same box in G. (b) On the contrary, if the distance between two nodes in G is less than ℓ B it is possible that these nodes belong in the same box. In G ′  = 3), where two nodes are connected if they are at a distance ℓ ≥ ℓB. We use a greedy algorithm for vertex coloring in G ′ , which is then used to determine the box covering in G, as shown in the plot.
these two nodes will not be connected and it is allowed for these two nodes to carry the same color, i.e. they may belong to the same box in G, (whether these nodes will actually be connected depends on the exact implementation of the coloring algorithm).
The algorithm that follows both constructs the dual network G ′ and assigns the proper node colors for all ℓ B values in one go. For this implementation a two-dimensional matrix c iℓ of size N × ℓ max B is needed, whose values represent the color of node i for a given box size ℓ = ℓ B .
1. Assign a unique id from 1 to N to all network nodes, without assigning any colors yet.
2. For all ℓ B values, assign a color value 0 to the node with id=1, i.e. c 1ℓ = 0.
3. Set the id value i = 2. Repeat the following until i = N .
(a) Calculate the distance ℓ ij from i to all the nodes in the network with id j less than i. The results of the greedy algorithm may depend on the original coloring sequence. The quality of this algorithm was investigated by randomly reshuffling the coloring sequence and applying the greedy algorithm several times and in different models [24]. The result was that the probability distribution of the number of boxes N B (for all box sizes ℓ B ) is a narrow Gaussian distribution, which indicates that almost any implementation of the algorithm yields a solution close to the optimal.
Strictly speaking, the calculation of the fractal dimension d B through the relation is valid only for the minimum possible value of N B , for any given ℓ B value, so any box covering algorithm must aim to find this minimum N B . Although there is no rule to determine when this minimum value has been actually reached (since this would require an exact solution of the NP-hard coloring problem) it has been shown [66] that the greedy coloring algorithm can, in many cases, identify a coloring sequence which yields the optimal solution.

Burning algorithms
This section presents three box covering algorithms based on more traditional breadth-first search algorithm. A box is defined as compact when it includes the maximum possible number of nodes, i.e. when there do not exist any other network nodes that could be included in this box. A connected box means that any node in the box can be reached from any other node in this box, without having to leave this box. Equivalently, a disconnected box denotes FIG. 16: Burning with the radius rB from (a) a hub node or (b) a non-hub node results in very different network coverage. In (a) we need just one box of rB = 1 while in (b) 5 boxes are needed to cover the same network. This is an intrinsic problem when burning with the radius. (c) Burning with the maximum distance ℓB (in this case ℓB = 2rB + 1 = 3) we avoid this situation, since independently of the starting point we would still obtain NB = 1. (1) and (2) until all nodes have a box assigned.

Repeat
This Random Box Burning algorithm has the advantage of being a fast and simple method. However, at the same time there is no inherent optimization employed during the network coverage. Thus, this simple Monte-Carlo method is almost certain that will yield a solution far from the optimal and one needs to implement many different realizations and only retain the smallest number of boxes found out of all these realizations.
Burning with the radius rB, and the Maximum-Excluded-Mass-Burning (MEMB) algorithm A box of size ℓ B includes nodes where the distance between any pair of nodes is less than ℓ B . It is possible, though, to grow a box from a given central node, so that all nodes in the box are within distance less than a given box radius r B (the maximum distance from a central node). This way, one can still recover the same fractal properties of a network. For the original definition of the box, ℓ B corresponds to the box diameter (maximum distance between any two nodes in the box) plus one. Thus, ℓ B and r B are connected through the simple relation ℓ B = 2r B + 1. In general this relation is exact for loopless configurations, but in general there may exist cases where this equation is not exact (Fig. 14).
The MEMB algorithm always yields the optimal solution for non scale-free homogeneous networks, since the choice of the central node is not important. However, in inhomogeneous networks with wide-tailed degree distribution, such as scale-free networks, this algorithm fails to achieve an optimal solution because of the presence of hubs.
The MEMB, as a difference from the Random Box Burning and the CBB, attempts to locate some optimal central nodes which act as the burning origins for the boxes. It contains as a special case the choice of the hubs as centers of the boxes, but it also allows for low-degree nodes to be burning centers, which sometimes is convenient for finding a solution closer to the optimal.
In the following algorithm we use the basic idea of box optimization, in which each box covers the maximum possible number of nodes. For a given burning radius r B , we define the excluded mass of a node as the number of uncovered nodes within a chemical distance less than r B . First, calculate the excluded mass for all the uncovered nodes. Then, seek to cover the network with boxes of maximum excluded mass. The details of this algorithm are as follows (see Fig. 17): 2. For all nodes calculate the "central distance", which is the chemical distance to its nearest center. The central distance has to be less than r B , and the center identification algorithm above guarantees that there will always exist such a center. Obviously, all center nodes have a central distance equal to 0.
3. Sort the non-center nodes in a list according to increasing central distance.
4. For each non-center node i, at least one of its neighbors has a central distance less than its own. Assign to i the same id with this neighbor. If there exist several such neighbors, randomly select an id from these neighbors. Remove i from the list.
5. Repeat step (4) according to the sequence from the list in step (3) for all non-center nodes.

Comparison between algorithms
The choice of the algorithm to be used for a problem depends on the details of the problem itself. If connected boxes are a requirement, MEMB is the most appropriate algorithm; but if one is only interested in obtaining the fractal dimension of a network, the greedy-coloring or the random box burning are more suitable since they are the fastest algorithms.
As explained previously, any algorithm should intend to find the optimal solution, that is, find the minimum number of boxes that cover the network. Fig. 18 shows the performance of each algorithm. The greedy-coloring, the CBB and MEMB algorithms exhibit a narrow distribution of the number of boxes, showing evidence that they cover the network with a number of boxes that is close to the optimal solution. Instead, the Random Box Burning returns a wider distribution and its average is far above the average of the other algorithms. Because of the great ease and speed with which this technique can be implemented, it would be useful to show that the average number of covering boxes is overestimated by a fixed proportionality constant. In that case, despite the error, the predicted number of boxes would still yield the correct scaling and fractal dimension.