Investigating the Origins of Fractality Based on Two Novel Fractal Network Models

Abstract

Numerous network models have been investigated to gain insights into the origins of fractality. In this work, we introduce two novel network models, to better understand the growing mechanism and structural characteristics of fractal networks. The Repulsion Based Fractal Model (RBFM) is built on the well-known Song-Havlin-Makse (SHM) model, but in RBFM repulsion is always present among a specific group of nodes. The model resolves the contradiction between the SHM model and the Hub Attraction Dynamical Growth model, by showing that repulsion is the characteristic that induces fractality. The Lattice Small-world Transition Model (LSwTM) was motivated by the fact that repulsion directly influences the node distances. Through LSwTM we study the fractal-small-world transition. The model illustrates the transition on a fixed number of nodes and edges using a preferential-attachment-based edge rewiring process. It shows that a small average distance works against fractal scaling, and also demonstrates that fractality is not a dichotomous property, continuous transition can be observed between the pure fractal and non-fractal characteristics.

1 Introduction

Modelling real networks has attracted a great deal of research in the last two decades since mathematical models allow us to rigorously and extensively investigate the underlying mechanisms of networks, discover substantial network properties, and shed light on their origins. For example, the preferential attachment model of Barabási and Albert explained the origin of the scale-free property [1], the model of Watts and Strogatz helped in understanding the “small-world” phenomena in a variety of networks [17], while the model of Newman provided a better understanding of the properties of highly clustered networks [9].

Fractality is another well-studied property, which is present in a large number of real networks [10, 18]. Fractal scaling of networks has been introduced by Song et al. [13] motivated by the notion of geometric fractals. Fractality is defined by the so-called box-covering method. A network is called fractal, if the minimum number of boxes required to cover the whole vertex set follows a power-law relation with the size of the boxes, i.e.:

$$\begin{aligned} N_B(l_B)\sim l_B^{-d_B}, \end{aligned}$$

where $l_B$ denotes the size of the boxes, $N_B(l_B)$ stands for the number of $l_B$-sized boxes resulting from box-covering, and $d_B$ is called the box-dimension or fractal dimension of the network (if exists).

After laying the foundation of fractal network analysis, Song et al. also proposed a mathematical model to explain the emergence of fractality in complex networks [14]. The main steps of the Song-Havlin-Makse (SHM) model can be summarised as follows:

• 1. The initial graph is a simple structure, e.g., two nodes connected via a link.

• 2. In iteration step $t+1$ we connect m offspring to both endpoints of every edge, i.e., a v node gains $m \cdot \deg _t(v)$ offspring, where m is a predefined parameter and $\deg _t(v)$ is the degree of node v at the end of step t.

• 3. In iteration step $t+1$ every (u, v) edge is removed independently with probability p, where p is a predefined parameter. When an edge is removed, it is replaced with a new edge between random offspring of u and v.

The network grows dynamically and the degree correlation (hub repulsion/att-raction) of the emerging graph is driven by parameter p. The fractality is also influenced by the choice of parameter p, namely, it can be shown that the generated network is fractal for $p=1$, and non-fractal for $p=0$ [14]. The intermediate values develop mixtures between the two properties. The authors conclude that the “repulsion-between-hubs” principle is the key to the emergence of fractal scaling [14].

Kuang et al. proposed the Hub Attraction Dynamical Growth (HADG) model, which is a modification of the SHM model, where the novelty lies in the flexible edge rewiring probability [7]. They demonstrated that by assigning smaller rewiring probability to edges connecting hubs, it is possible to create fractal networks with hub attraction behaviour. They also introduced a so-called “within-box link-growth” phase to the model to increase the clustering coefficient of the resulting network, which does not affect the fractal scaling [7].

Besides the relation of hub repulsion/disassortativity to fractality, another interesting phenomenon to model has been the conflicting relation of fractality and the small-world property [6]. For example, Rozenfeld et al. proposed a new family of recursive networks, which are small-world for certain parameter settings, and fractal for others [11]. There are also many articles, which introduce models that exhibit a transition between the two properties [8, 12, 16, 20].

In this work, we introduce two novel fractal network models. First, we present the Repulsion Based Fractal Model (RBFM), which is intended to resolve the seeming contradiction of [7, 14] by showing that repulsion causes the fractality of both the SHM and HADG models. Motivated by the fact that repulsion between nodes inevitably increases the average shortest path distance of a network, we introduce a second model to study the relationship between fractality and small-worldness. The second model, called Lattice Small-world Transition Model (LSwTM), supports the findings of earlier works [8, 12, 16] that small-world property interferes with fractality, and that real transition exists between the two characteristics. In contrast to the related works, our model is not relying on the normalisation method, and LSwTM is not a growing network, but the transition is shown on a fixed number of edges and nodes.

2 Repulsion Based Fractal Model

This model is based on the Song-Havlin-Makse model, it also evolves through time, and we rewire edges to create repulsion among nodes. However, here the probability of an edge to be rewired is not fixed but depends on the degree of its endpoints. In contrast to the Song-Havlin-Makse model, repulsion is always present in RBFM, moreover, with a predefined parameter we can specify the nodes that repel each other (e.g., hubs or small degree nodes). The model also adapts the “within-box link-growth” step of Kuang et al. [7] in order to create more realistic networks. The growing mechanism of the Repulsion Based Fractal Model is as follows:

• 1. Similarly to the Song-Havlin-Makse model, we start with a simple graph structure, e.g. two nodes connected via a link.

• 2. The growth process of the model is the same as step 2 of the SHM model, namely in iteration step $t+1$ we connect $m \cdot \deg _t(v)$ offspring to every v node, where m is a predefined parameter and $\deg _t(v)$ is the degree of node v at the end of step t.

• 3. In iteration step $t+1$ we remove every (u, v) edge with probability $p_{uv}^Y$ that depends on the mean degree of u and v normalised by the maximum degree:

  $$\begin{aligned} p_{uv}^Y = 1 - \left| Y - \frac{\deg _t(u)+\deg _t(v)}{2\cdot \deg _{t, \max }}\right| , \end{aligned}$$

  where $Y \in [0,1]$ is a predefined parameter, $\deg _t(u)$ is the degree of node u, $\deg _{t, \max }$ is the maximum degree at step t. When an edge is removed, it is replaced with a uniformly randomly chosen new edge between the offspring of its endpoints.

• 4. We add $\deg _t(v)$ edges among the newly generated offspring of every old node v. In order not to create self-loops this step is only executed, when $m>1$.

With the Y parameter, we assign high edge rewiring probability to those edges, which endpoints’ average degree is close to $Y \cdot \deg _{t, \max }$. For example, if $Y = 0$, with high probability we rewire those edges, which connect nodes with a relatively small degree, on the other hand in the case of $Y = 1$, with high probability we rewire the edges, that are linked between nodes with large degree (hubs). Figure 1 illustrates these two extreme cases of the model. The speciality of this model, is that it gives rise to fractal graphs for all $Y \in [0, 1]$, as it can be seen on Fig. 2(a), too.

According to Song et al. [14] fractality is driven by disassortativity (negative degree correlation), however, Kuang et al. [7] introduced a model that generates fractal networks where the hubs are connected. The Repulsion Based Fractal (RBF) Model suggests that the property, which affects the fractal scaling of a network is “repulsion”, and repulsion does not necessarily have to be among hubs. The resolution of the contradiction lies in the fact that repulsion clearly affects the correlation of degrees. If there is a repulsion between hubs, i.e., if in the RBF model $Y = 1$, then hubs are only connected with small degree nodes, thus the degrees are anti-correlated and the network is disassortative. On the other hand, when the repulsion is between the small degree nodes, there are long paths consisting of small degree nodes, but in this case, the hubs are connected, hence there is a significantly larger correlation between the degrees. However, the resulting network is still fractal. The common mechanism that drives the fractality of the Song-Havlin-Makse model [14], the model of Kuang et al. [7], and the RBFM is repulsion.

Clearly, repulsion makes the graphs spread out, i.e., when the nodes are repelling each other, then the graph cannot be too compact. To study the relationship between small-worldness and fractality we introduce the Lattice Small-world Transition model that is detailed in Sect. 3.

Fig. 1

Illustration of the Repulsion Based Fractal Model for (a) $Y=0$, i.e., when small degree nodes tend to repel each other, (b) $Y=1$, i.e., when the repulsion is present among hubs

2.1 Properties of the RBFM

Some of the main properties of the networks generated by the Repulsion Based Fractal Model are deterministic, i.e., do not depend on the exact realisations, but are determined by the parameters. In fact, the number of nodes and edges of the network are only influenced by the choice of parameter m and the number of iterations t. Following the notations and thread of [7, 14] we can conclude the following for the $m>1$ case of the model:

$$\begin{aligned} E(t)-E(t-1)&=2m\cdot E(t-1) + 2\cdot E(t-1)\\ E(t)&=(2m+3)\cdot E(t-1) = E(0)\cdot (2m+3)^t, \end{aligned}$$

where E(t) denotes the number of edges of the network at step t, while E(0) is the number of edges of the initial graph. For the number of nodes the following findings can be made:

$$\begin{aligned} N(t)-N(t-1)&=2m\cdot E(t-1)\\ N(t)&=N(t-1)+2m\cdot E(0)\cdot (2m+3)^{t-1}\\&=N(0)+E(0)\cdot 2m \cdot \sum _{k=0}^{t-1}{(2m+3)^k}\\&=N(0)+E(0)\cdot \frac{m}{m+1} \cdot ((2m+3)^t-1), \end{aligned}$$

where N(t) refers to the number of nodes of the network at iteration step t, and N(0) is the number of nodes of the initial graph.

When $m=1$, step 4 cannot be executed, consequently the previous derivations simplify:

$$\begin{aligned} E(t)-E(t-1)&=2m\cdot E(t-1)\\ E(t)&= E(0)\cdot (2m+1)^t = E(0)\cdot 3^t \\ N(t)&=N(0)+E(0)\cdot 2m \cdot \sum _{k=0}^{t-1}{(2m+1)^k} \\&= N(0)+ E(0)\cdot ((2m+1)^t-1)= N(0)+ E(0)\cdot (3^t-1) \end{aligned}$$

Since the number of nodes and edges are deterministic in parameters m and t, the average degree of the network can also be studied analytically. In the $m=1$ case:

$$\begin{aligned} d_{avg} = \frac{2\cdot E(0) \cdot 3^t}{N(0)+ E(0)\cdot (3^t-1)} \xrightarrow [t \rightarrow \infty ]{} 2 \end{aligned}$$

When $m>1$:

$$\begin{aligned} d_{avg} = \frac{2\cdot E(0) \cdot (2m+3)^t}{N(0)+E(0)\cdot \frac{m}{m+1} \cdot ((2m+3)^t-1)} \xrightarrow [t \rightarrow \infty ]{} \frac{2(m+1)}{m} \xrightarrow [m \rightarrow \infty ]{} 2 \end{aligned}$$

To investigate how similar the random realisations instead of generalisations of the model with a given parameter setting are in terms of various network characteristics, we generated 30 graphs with a given parameter setting. We examined 7 network metrics, namely, the average path length, the normalised diameter, the normalised maximum degree, the average clustering coefficient, the assortativity coefficient, the maximum of the eigenvector centralities, and the skewness of the degree distribution. The results can be found in the supplementary material: https://github.com/marcessz/fractal-network-models. The examined characteristics can be considered stable because the values of the metrics do not differ significantly for the different realisations of the networks. The average clustering coefficient, and also the maximum of the eigenvector centralities may not seem to be as consistent as the other metrics, but the range, in which the values vary is still quite small. Furthermore, the fluctuation decreases for larger networks, i.e., when the model performs more iterations. Overall, we can conclude that the main characteristics of the network model for a given parameter setting do not depend heavily on the exact realisations.

We also investigated how sensitive the model is to its parameters, i.e., how a small change in the parameters affects the characteristics of the network. Due to the complicated network evolution process, it is difficult to analytically determine various characteristics of the model, thus we generated 30 graphs with a certain parameter setting and averaged the graph metrics of these 30 realisations. We repeated this procedure for various parameter settings to assess the parameter sensitivity of the model. Figure 2(b), (c), (d) show the contour plots of three network metrics (assortativity, maximum eigenvector centrality, average clustering coefficient). It can be seen that some of the characteristics do not, or just barely depend on the choice of parameter Y, while others are highly influenced by it. The average clustering coefficient is quite non-sensitive for all of the parameters, but naturally increases greatly, when the structure of the network is more complex than a path (i.e., when $m>1$). The other examined characteristics highly depend on the realisation of parameter Y. The average path length and the (normalised) diameter become larger as we increase the value of Y, and similar holds for the maximal eigenvector centrality. The generated networks are disassortative in all of the cases, but the model gets more disassortative for larger values of Y, i.e. when the repulsion is created among large degree nodes.

Fig. 2

(a) Illustration of the fractality of the Repulsion Based Fractal Model for different parameter settings. (b)–(d) Contour plots of three network metrics, which show the change of the metric values as a function of parameters m and Y of the Repulsion Based Fractal Model. The subfigures illustrate the values of the (b) assortativity coefficient, (c) maximal eigenvector centrality, (d) average clustering coefficient for networks generated by the model with $t=3$ setting and with multiple choices of parameters m and Y

3 Lattice Small-World Transition Model

Our novel model embraces both preferential attachment mechanism and the “geometric” structure that emerges in networks that can be embedded in two- and three-dimensional Euclidean spaces, for instance, infrastructure networks [2], blood vessels, and trabecular bones [19]. Several network models have been introduced to create a synergy between geometric network models and preferential attachment. For example, Flaxman et al. have presented two growth models in which the vertices of the network are randomly chosen points of the three-dimensional unit sphere, and edges are created taking into account both the proximity of the nodes and an extended preferential attachment mechanism [3, 4]. The use of the preferential attachment principle to create small-world networks has also been studied extensively [5, 15].

Here, we present a network model, which utilises the fractal nature of grid-like structures, and at the same time works against it with the preferential attachment mechanism. The Lattice Small-world Transition Model is defined as follows:

• 1. We start with a d-dimensional (practically $d=2$) grid graph with $n_1 \times n_2 \times \dots \times n_d$ vertices.

• 2. With probability p, every $(v_i, v_j)$ edge is replaced by $(v_i, v_k)$, where $v_k$ is chosen with a probability, that is proportional to $p_{v_k}$:

  $$\begin{aligned} p_{v_k} = \frac{1}{1 + \exp \left( -a \cdot \left( \frac{\deg (v_k)}{\deg _{\max }} - \frac{1}{2}\right) \right) }, \end{aligned}$$

  where a is a positive constant, $\deg (v_k)$ is the degree of node $v_k$ and $\deg _{\max }$ is the maximum degree of the current graph. Note that when the normalised degree of $v_k$ is $\frac{1}{2}$, then $p_{v_k}$ equals $\frac{1}{2}$. If $\deg (v_k)$ is less than $\deg _{\max }/2$, then $p_{v_k}$ is close to zero, on the other hand, when $\deg (v_k) > \deg _{\max }/2$ then $p_{v_k}$ is nearly one (if a is large enough). By practical motivation, to avoid multiple edges, the set of nodes to select $v_k$ from is defined as $S_{v_i}~=~V\backslash \{\Gamma _{v_i}\cup \{v_i\}\}$, where $\Gamma _{v_i}$ denotes the neighbourhood of $v_i$. By default, $v_j$ is replaced with $v_k$ during the rewiring process, however, if in this way the graph becomes disconnected, $v_i$ is replaced instead.

Figure 3 illustrates that even a small rewiring probability results in a network that differs greatly from a grid graph. The fractality of the generated network depends on the choice of p. For $p=0$ the network is purely fractal, and as p grows the model shows a transition from fractal to non-fractal. It also has to be mentioned that this transition is not sharp, and there are intermediate states, where the network is locally fractal, although the pure property is no longer present globally. These properties are well illustrated on Fig. 5(a). Furthermore, as fractality disappears small-world property arises. Figure 4 shows the change in the normalised diameter and average path length in terms of the model parameters. The normalisation by the logarithm of the number of nodes is done to be able to compare the distances of networks of different sizes. It can be seen that the distances are growing as p decreases, i.e., as the networks become fractal. Both RBFM and LSwTM suggest that a fractal network has to be spread out, and as LSwTM illustrates, as we rewire edges according to the preferential attachment mechanism, it turns small-world and loses its fractal structure.

Fig. 3

Illustration of the Lattice Small-world Transition Model for (a) $p=0$, (b) $p=0.1$

Fig. 4

(a) Normalised diameter and (b) average path length (i.e. diameter/average path length divided by the logarithm of the size) as a function of the logarithm of the number of nodes. The colouring is based on the p parameter of the model

3.1 Properties of the LSwTM

Similarly to the RBFM, some properties of the networks generated by the Lattice Small-world Transition Model are deterministic in the model parameters. The number of nodes and edges of a grid graph is determined by its $n_i \; (i=1, 2, \ldots , d)$ parameters. Since the model only includes edge rewiring steps and there is no edge/node deletion or addition, the resulting network has the same number of nodes and edges as the initial graph.

Simple derivations can be made for the number of nodes and edges of the generated networks, when the initial grid graph is d-dimensional, i.e when we have parameters $n_1, n_2, \ldots , n_d$:

$$\begin{aligned} |V|&= \prod _{i=1}^{d}{n_i} \\ |E|&= \sum _{i=1}^{d}{(n_i-1)\cdot \frac{\prod _{j=1}^{d}{n_j}}{n_i}} \end{aligned}$$

$$\begin{aligned} d_{avg}&= \frac{2\cdot \sum _{i=1}^{d}{(n_i-1)\cdot \frac{\prod _{j=1}^{d}{n_j}}{n_i}}}{\prod _{i=1}^{d}{n_i}} = \frac{2\cdot \left( \sum _{i=1}^{d}{ \prod _{j=1}^{d}{n_j}} - \sum _{i=1}^{d}{\frac{\prod _{j=1}^{d}{n_j}}{n_i}}\right) }{\prod _{i=1}^{d}{n_i}}\\&= 2d - 2\cdot \sum _{i=1}^{d}{\frac{1}{n_i}} \end{aligned}$$

When all $n_i$s are large, the average degree is close to 2d. On the other hand, when $n_i=2$ for all $i=1, 2, \ldots , d$, the average degree equals to d. Consequently, if $n_i>1$ for all i, the following bounds hold: $d \le d_{avg} < 2d.$ If $n_i=1$ for at least one i, the average degree can be smaller than d, since in this case we basically start with a lattice of dimension less than d.

We also investigated how similar the random realisations of the LSwTM are, moreover we also executed a sensitivity analysis on the parameters of the model. Again, we consider the same seven structural network metrics as before. For a given parameter setting the generated networks have very similar properties concerning the examined characteristics. The results can be found in the supplementary material: https://github.com/marcessz/fractal-network-models.

Figure 5(b), (c), (d) show how the model parameters affect some characteristics of the network. Most of the graph metrics are influenced mainly by the network size, for example, the maximal eigenvector centrality decreases as the network grows. The average clustering coefficient, apart from the small networks, is around 0, independently of the value of p. Some characteristics, however, rather depend on parameter p and are not affected highly by the network size. The assortativity coefficient decreases with the growing values of p, and the same holds for the average path length and the (normalised) diameter too, with the remark that these two become small even for values of p slightly greater than 0.

Fig. 5

(a) Illustration of the fractality of the LSwT model for different parameter settings. (b)–(d) Contour plots of three graph metrics, illustrating the metric values as a function of the parameters of the LSwTM. The subfigures illustrate the values of the (b) assortativity coefficient, (c) maximal eigenvector centrality, (d) average clustering coefficient for networks generated by the model with multiple choices of the number of the nodes and parameter p

4 Discussion and Summary

In this work, we introduced and analysed two network models to better understand what mechanisms affect the fractality of networks.

The Repulsion Based Fractal Model is based on the models of Song et al. [14] and Kuang et al. [7]. Song et al. assumed that in fractal networks the hubs are not connected, in other words, there is a repulsion between hubs, which is also known as disassortative mixing. On the other hand, Kuang et al. modified the Song-Havlin-Makse model, in such a way that it is able to generate fractal networks with connected hubs. Although Kuang et al. pointed out that disassortativity is not the mechanism that makes a network fractal, they did not investigate thoroughly the origins of fractality. Through the Repulsion Based Fractal Model, we showed that the repulsion between nodes induces fractality, and the repelling nodes do not necessarily have to be hubs. The RBF model also well illustrates that repulsion affects not only the fractality but the assortative-mixing of a network, which resolves the contradiction between the findings of Song et al. [14] and Kuang et al. [7].

As the RBFM and earlier works suggest [8, 12, 16, 20], fractality is influenced by the node distances. We introduced a model, which shows that if we take a purely fractal network, and we start to rewire edges according to the preferential attachment principle, then as the shortest path length decreases, the fractal structure breaks down gradually, and eventually the small-world property will dominate the network.