Keywords

1 Introduction

Understanding complex and aperiodic phenomena encountered in biology [27], chemistry [10, 16, 25, 32], economics [7] and physics [6, 9, 17], represents an open scientific challenge. The progress towards this fundamental goal can benefit from different theoretical frameworks, including statistical physics and complex network theory, information theory, non-linear dynamics and chaos, that constitute the composite panorama of Complex Science. In this context any effort to find synergies among different approaches greatly helps to move steps forward in controlling complexity. Our contribution here is concerned at presenting a possible pathway to relate chaos and network theory.

During the last years, complex network theory has rapidly grown as a interpretative framework for many complex systems and phenomena, ranging from financial crises to epidemics spreading [6]. Though this approach may appear as a drastic simplification of the specific features of a system constituents, it is able to disentangle the intrinsic topology of their interactions, which crucially impacts the possible dynamics running on the network itself [31].

In the realm of dynamical systems, network statistical techniques have been applied to analyse nonlinear time series, with a particular focus on characterizing chaotic dynamics. The main idea of this methodology is to transform the information of a time series from the temporal domain into the topology of a network and, hence, the key point resides in the way one defines nodes and links. So far, several transformation approaches have been proposed [2, 11,12,13,14, 19, 20, 24, 26, 28, 33, 35,36,37,38] and a bench of network tools have been adapted to the analysis of nonlinear time series.

However, less effort has been devoted to investigate how the latter could, in turn, be exploited as a source for growing complex network with non-trivial connectivity patterns. Most of real-world networks are inhomogeneous, showing scale-free property defined by a power-law degree distribution \(P(k) \sim k^{-\gamma }\), where k is the number of connections of a node (degree). This feature has been successfully explained through preferential attachment mechanisms [5]. In these mechanisms nodes that stochastically gain a higher degree, present also stronger ability to attract new links added to the network, leading to the formation of structures with a small number of highly connected nodes in spite of a broad spectrum of moderately and scarcely connected nodes.

Recently, it has been pointed out how an intrinsic aspect of this hierarchical connectivity is the presence of fractal and self-similar features embedded in the network topology. Stimulated by the seminal paper by Song et al. [34], fractal properties of scale-free networks have been revealed and measured by adapting box-counting approaches to the non-euclidean geometry of complex networks. In particular, networks were suitably partitioned into sub-graphs or clusters with characteristic diameters (in the sense of network distance) and self-similarity was shown when scaling this characteristic measure. Following similar a posteriori partition strategies, the possibility for multifractality has been also analytically demonstrated by Furuya and Yakubo [18] and attributed to the large fluctuations of local node density in scale-free networks.

In this context, an open question is whether (and which) deterministic multifractal processes could be considered a priori as alternative evolution mechanisms for growing scale-free networks that preserve the multifractality of the original source in the ultimate structure.

In this paper we present a novel model for developing power-law networks starting from a multifractal chaotic generator of numbers. We show that the resulting topologies preserve the multifractal nature of the underlying chaotic source and we also derive analytically the relation which ties the power-law exponent characterizing the connectivity of these networks with the generalized dimension of the projected dynamics. Finally, we discuss this closed-form relation as a stable tool for characterizing the multifractal spectrum of a time series through the analysis of the network connectivity.

2 Model

We generate networks from chaotic dynamical data by means of a transition transformation introduced in [11] and briefly resumed hereunder. We start with the set \(\mathcal V = \lbrace M \;\text {nodes} \rbrace \) and the network connectivity is built-up by using a normalized chaotic series of numbers , where \(n>> 1\) is the size of \(\mathcal {G}_{chaotic}\). Nodes are identified with the index \(i=\left\lfloor x_j M + 1 \right\rfloor \) (where \(\lfloor z \rfloor \) is the floor function) and an undirected connection between two successive nodes \(i =\left\lfloor x_j M + 1 \right\rfloor \) and \(l = \left\lfloor x_{j+1} M + 1 \right\rfloor \) (\(i,l \in \mathcal V\)) is established if it does not constitute any multiple–connection. When these criteria are not met, the successive pair of numbers, namely \(i'=\left\lfloor x_{j+1} M + 1\right\rfloor \) and \(l' = \left\lfloor x_{j+2} M + 1\right\rfloor \), is considered. The previous step is reiterated until the maximal possible number of edges is introduced in the network, i.e. until a stationary network is achieved.

The structures resulting from this procedure are connected networks by construction, preserve temporal information of the generator and, because of the peculiar fractal properties of the strange attractors underlying chaotic sources, consist of a fraction N(M) of the initial M nodes. In this framework, the network provides an alternative way for partitioning the fractal support of the chaotic dynamics congruent with the box-counting method [1, 21, 22], where the N(M) nodes of the network correspond to the number of boxes of length \(\epsilon = M^{-1}\) needed to cover the fractal chaotic attractor in the phase space. As a consequence, the maximal number of edges asymptotizes to the upper limit, \(\mathcal {L}_{chaotic}(M)\), which is characteristic of the chaotic source at hand and is strictly lower than the fully connected configuration \(M(M-1)/2\). N(M) and \(\mathcal {L}_{chaotic}(M)\) are related to the fractal dimension of the chaotic series as [11]:

$$\begin{aligned} \mathcal {L}_{chaotic}(M) \approx \frac{\langle k \rangle }{2} N(M) \backsim M^{D_0}, \end{aligned}$$
(1)

where \(D_0\) is the capacity dimension of the set (obtained through the linear regression of log(N(M)) versus log(M)) and \(\langle k \rangle \) is the average degree of the network. In our previous work [11] \(\mathcal {L}_{chaotic}(M)\) was used as a topological observable for (i) characterizing the capacity dimension of a chaotic series and (ii) discerning chaotic dynamics from random ones, being the latter capable of realizing fully connected configurations.

In this work we want to study more in detail the connectivity (typically the degree distribution) of the these networks and relate them to the multifractality of the underlying chaotic attractor. To do so, we consider a paradigmatic example of chaotic generators, the logistic map \(x_{j+1} = r \,x_j (1-x_j)\). This discrete-time formula maps the interval \(x \in \left[ 0,1\right] \) into itself when the control parameter r ranges between 0 and 4. Multifractal chaotic regimes interspersed with periodic windows occur in the interval \(r \in [3.57, 4)\) and hereunder we will consider the representative case \(r=3.7\) to back up the validity of the following analytical approach. The map is iterated as needed to achieve a stationary connectivity in the network (typically \(n \sim 10^3 M\)). In this sense possible finite-size effects of the chaotic time series are ruled out.

3 Scale-Free Networks Out of Chaos

When the algorithm described above is applied to the multifractal logistic source, the emerging networks exhibit characteristic scale-free properties as indicated by a power-law degree distribution with an exponent around 3. In Fig. 1 we report the cumulative degree distribution \(P_{cum}(k)=\frac{1}{N(M)}\sum \limits _{i/k_i \le k} \mathbbm {1}\) (giving the probability that a network node presents degree equal or larger than k) of the logistic network. The plot describes the scale-free nature of networks for different sizes (\(M \in [10^4, 10^7]\)) with all trends collapsing to a common power-law distribution \(P_{cum}(k)=k^{-\gamma '}\) characterized by \(\gamma ' \sim 2.142(3)\). The exponent of the simple degree distribution P(k) then reads \(\gamma = \gamma ' + 1 \sim 3.142(3)\). Power-law scale-invariant properties have been obtained for networks generated from other values of the critical parameter r of the logistic map (in the range where it presents multifractal characteristics) and from other 1-dimensional maps [29].

In the following analysis we prove that this power-law trends in the degree distribution reflect the multifractal nature of the network and can be analytically related to the generalized dimension of the chaotic generator.

Fig. 1.
figure 1

Cumulative degree distributions of the logistic network (\(r = 3.7\)) for \(M = 10^4\) (red circles), \(10^5\) (green squares), \(10^6\) (grey diamonds) and \(10^7\) (blue triangles) nodes. \(n = 1 \times 10^{10}\) iterations and \(P_{cum}(k)\) is averaged over 100 networks (i.e. 100 different initial seeds of the chaotic generator). (Color figure online)

Full size image

For strange attractors it is common that different regions are differently visited, and chaotic orbits will spend most of their time in a small minority of the \(N(\epsilon )\) boxes partitioning the fractal support underneath the chaotic attractor itself. An illustration of this property is given in Fig. 2a for the unidimensional support of the logistic map with \(r=3.7\). The dimension \(D_q\) takes into account these heterogeneous probability pattern and generalizes the definition of the box-counting dimension as

$$\begin{aligned} D_q = \frac{1}{q - 1} \lim _{\epsilon \rightarrow 0}\frac{\text {log} \sum _i^{N(\epsilon )}{p_i^q}}{\text {log} \; \epsilon }. \end{aligned}$$
(2)

This characterizes the intrinsic hierarchy within a fractal set in terms of the moments q of the partition function \(\sum _i^{N(\epsilon )}{p_i^q}\) [22, 29, 30]. Here \(p_i = \lim _{n \rightarrow \infty } \frac{n_i}{n}\) quantifies the probability, termed natural measure, that the chaotic map returns in the i-th box of the \(N(\epsilon )\) available boxes, during an infinitely long orbit (in practise \(n_i\) times over \(n>> 1\) iterations of the chaotic orbit). \(D_q(q)\) exhibits a non-constant scaling bounded between the asymptotic values \(D_{\pm \infty }\) when a heterogeneous probability distribution describes the recurrence of a chaotic trajectory over different regions of the attractor which can thus be defined multifractal. An example of such a case is shown in Fig. 2b, where we report the cumulative distribution of the natural measure, \(P_{cum}(p)\), for the logistic map displayed in Fig. 2a. It can be observed how this trend describes an extremely heterogeneous statistics and, in particular, follows a power-law behaviour (Fig. 2b), characterized by the same exponent as for the cumulative degree distribution of the associated graph (compare Figs. 1 and 2b).

From this evidence stems the initial ansatz of our analytical approach, where we assume that the degree of network nodes is representative of the natural measure of the corresponding boxes partitioning the fractal support. In particular, as a first approach, we can reasonably hypothesize that an increasing linear relation links the degree k of a certain node to the natural measure p of the associated box.

Fig. 2.
figure 2

(a) Natural measure p(i) of the i-th box for the logistic map with \(r =3.7\). The support [0, 1] is partitioned in \(M = 1 \times 10^7\) boxes; the map is iterated for \(n = 1 \times 10^{10}\) time steps and the statistics is performed over 100 initial conditions. (b) Cumulative probability distribution, \(P_{cum}(p)\), of the box natural measures p(i) for the logistic map with \(r = 3.7\), \(M = 1\times 10^7\) boxes, \(n = 1 \times 10^{10}\) iterations. \(P_{cum}(p)\) is averaged over 100 initial conditions.

Full size image

Thanks to this correlation, we can re-write the natural measures involved in the computation of \(D_q\) in terms of node degrees through

$$\begin{aligned} p_i \backsim \frac{k_i}{\langle k \rangle N(\epsilon )}. \end{aligned}$$
(3)

Since in scale-free networks the average degree \(\langle k \rangle \) is a constant [6, 15] and can be neglected in relation (3), the partition sum of Eq. (2) reads

$$\begin{aligned} \sum _i{p_i^q} \backsim \sum _i \bigg (\frac{k_i}{N(\epsilon )}\bigg )^q&\backsim N(\epsilon )^{-q} \mathop {\sum }\nolimits _i \frac{k_i^q}{N(\epsilon )} N(\epsilon ) \\ \nonumber&\backsim \langle k^q \rangle N(\epsilon )^{1-q}.\,\,\,\,\,\,\,\,\,\, \end{aligned}$$
(4)

From the definition of \(D_q\) (see Eq. (2)), it follows

$$\begin{aligned} \sum _i{p_i^q} \backsim \epsilon ^{(q-1)D_q} \backsim N(\epsilon )^{-(q-1)D_q/D_0} \end{aligned}$$
(5)

(being \(\epsilon = N(\epsilon )^{-(1/D_0)}\)). By comparing Eqs. (4) and (5), we find that

$$\begin{aligned} \langle k^q \rangle N(\epsilon )^{1-q} \backsim N(\epsilon )^{-(q-1)D_q/D_0} \end{aligned}$$
(6)

and, hence

$$\begin{aligned} \langle k^q \rangle \backsim N(\epsilon )^{(q-1)(1-D_q/D_0)}. \end{aligned}$$
(7)

which features a first expression relating a topological observable of the network and the generalized dimension of the multifractal chaotic source.

\(\langle k^q \rangle \) can be also written as

$$\begin{aligned} \langle k^q \rangle = \int _{m(\epsilon )}^{k_c(\epsilon )} dk \, P(k) \, k^q \end{aligned}$$
(8)

where \(P(k) \backsim k^{-\gamma +1}\) is the degree distribution of the projected network, \([m(\epsilon ), k_c(\epsilon )]\) is the k–domain where P(k) exhibits the power-law tail and the degree cut-off \(k_c(\epsilon )\) is the maximal degree of the network. In scale-free networks, when the exponent of the integral argument is \(q-\gamma >0\), integral (8) is asymptotically equal to \(k_c(\epsilon )^{q + 1 - \gamma }\) [6, 15] and quickly diverges as the size of the network tends to the thermodynamic limit. Keeping in mind Eq. (7), it can then be shown that for large positive values \(q = q_{\infty }\) where \(D_{q}\) saturates to \(D_{\infty }\), integral (8) reads

$$\begin{aligned} k_c(\epsilon )^{q_{\infty }} \backsim N(\epsilon )^{q_{\infty }(1-D_{\infty }/D_0)}, \end{aligned}$$
(9)

implying

$$\begin{aligned} k_c(\epsilon ) \backsim N(\epsilon )^{(1-D_{\infty }/D_0)}. \end{aligned}$$
(10)
Fig. 3.
figure 3

Scaling of the degree cut-off, \(k_c(\epsilon )\), as function of the network size \(N(\epsilon )\). \(D_{0}\) and \(D_{\infty }\) can be computed by means of Eqs. (1) and (11), respectively. For this illustrative case \(\beta =0.482\pm 0.004\) and \(D_0 \sim 1\).

Full size image

Equation (10) ties \(k_c(\epsilon )\) and \(D_{\infty }\) through \(D_0\). In detail, \(D_{\infty }\) can be extrapolated from the slope \(\beta = 1-D_{\infty }/D_0\) of the linear regression of log\((k_c(\epsilon ))\) plotted versus log\((N(\epsilon ))\) (see Fig. 3) following

$$\begin{aligned} D_{\infty } = D_0 (1 - \beta ), \end{aligned}$$
(11)

where \(D_0\) is known from Eq. (1). The second relation for \(\langle k^{q} \rangle \) is thus derived by substituting \(k_c(\epsilon )\) in Eq. (8), to obtain

$$\begin{aligned} \langle k^{q} \rangle \backsim N(\epsilon )^{(q + 1 - \gamma )(1-D_{\infty }/D_0)}. \end{aligned}$$
(12)

Finally, combining Eqs. (7) and (12)

$$\begin{aligned} (q-1)(1-D_q/D_0) = (q + 1 - \gamma )(1-D_{\infty }/D_0) \, \end{aligned}$$
(13)

and, conveniently re–arranging,

$$\begin{aligned} \gamma = 2 + (q-1)\frac{D_q - D_{\infty }}{D_0 - D_{\infty }}. \end{aligned}$$
(14)

one can laid down a closed-form relating \(\gamma \) to \(D_0, D_q\) and \( D_{\infty }\). This expresses the “latent” multifractality of a scale-free network grown from the projection of a multifractal chaotic series and describes how multifractal measures are quantitatively incorporated in the power-law exponent.

4 Concluding Discussion

In this paper we have presented a new perspective to bridge chaotic dynamics and complex networks. Specifically, we have introduced a simple procedure able to grow scale-free networks by using generators of multifractal chaotic series. The heterogeneity and the free–scale nature of these networks, encoded in the power-law degree distribution P(k), are demonstrated to be analytically related to the multifractal properties of the generating chaotic source. While fractal and multifractal properties of many real scale-free networks have been already unveiled through a posteriori analysis, our model shows that a chaotic multifractal processes can represent an a priori mechanism for growing power-law networks which, in turn, preserve multifractal information of the original source in the ultimate topology. With respect to the stochastic preferential attachment mechanisms chaotic generators could be seen as an alternative deterministic pathway for the formation of scale-free structures.

In our numerical exploration we found that a multifractal process can potentially be mapped into a power-law network if (i) a linear relation ties the natural measures to the degrees of the nodes and (ii) the distribution of the natural measures shows a power-law trend. Work is in progress [8] to generalize this description to cases in which the natural measure increases nonlinearly with the node degree. From a network analysis viewpoint other topological properties, such as clustering and assortativity within these multifractal networks should be investigated in depth in order to unravel further correlations between the network connectivity and the properties of underlying chaotic dynamics.

From the perspective of time series analysis, this work represents a further proof of concept of the great potential of network approaches when applied to the characterization of nonlinear dynamics. Thanks to a simple statistics on the network connectivity it is possible to calculate the generalized dimension of the associated chaotic generator via a closed formula. This can be exploited as a robust method for multifractal analysis, particularly stable for high indexes q of the generalized dimension, prohibitive to box-counting methods.

The validity of our approach is demonstrated here for the theoretical but still general study case of 1-dimensional logistic-like maps. A future domain of investigation is the case of multifractal series resulting from non-chaotic processes, like binomial multifractal generators [23]. Also our challenge is to extend this framework to real multifractal normalized time series of practical interest. Prominent examples are time series collecting earthquakes frequency and magnitude, that have been proven to converge into universal power-law descriptions [4]. In this context fractal and multifractal measures are of utmost interest and network theory is already fruitfully applied to disclose the highly hierarchical and complex spatio-temporal organization of these phenomena and improve predictive protocols [3].