Chapter 1
Entropy and Renormalization in Chaotic Visibility Graphs

Bartolo Luque, Fernando Javier Ballesteros, Alberto Robledo and Lucas Lacasa

In this chapter, we concentrate on a mapping from time series to graphs, the visibility algorithm introduced by Lacasa et al. [1]. In order to cite some of its most relevant features, we will stress its intrinsic nonlocality, low computational cost, straightforward implementation, and quite "simple" way of inheriting the time series properties in the structure of the associated graphs. These features will make it easier to find connections between the underlying processes and the networks obtained from them by a direct analysis of the latter. In particular, in this chapter, we will focus the implementation of the algorithm of visibility to three known routes to chaos. We will define a graph entropy and process of renormalization for visibility graphs that characterize these routes and analyze the relationship between the flow of renormalization and the extremes of the entropy function.

Disregarding any underlying process, we can consider a time series just as an ordered set of values and transform this set into a different mathematical object with the aids of an abstract mapping [2, 3]. We can then ask which properties of the original set are conserved, which are transformed and how, what can we say about one of the mathematical representations just by looking at the other. This exercise is of mathematical interest by itself. In addition, it turns out that time series or signals is a universal method of extracting information from dynamical systems in any field of science. Therefore, the preceding mathematical mapping gains some unexpected practical interest as it opens the possibility of analyzing a time series from an alternative point of view. Of course, the relevant information stored in the original time series should be somehow conserved in the mapping. The motivation is completed when the new representation belongs to a relatively mature mathematical field, where information encoded in such a representation can be effectively disentangled and processed. This is, precisely, the first motivation to map time series into networks.

This motivation is increased by two interconnected factors: (i) Although a mature field, time series analysis has some limitations, when it refers to study the so-called complex signals. Beyond the linear regime, there exists a wide range of phenomena, which are usually embraced in the field of the so-called complex systems. Dynamical phenomena such as chaos, long-range correlated stochastic processes, intermittency, and multifractality are examples of complex phenomena, where time series analysis is pushed to its own limits. Nonlinear time series analysis develops from techniques such as nonlinear correlation functions, embedding algorithms, multrifractal spectra, and projection theorem tools that increase in complexity parallel to the complexity of the process/series under study. New approaches to deal with complexity are not only welcome, but needed. Approaches dealing with the intrinsic nonlinearity by being intrinsically nonlinear in turn deal with the possible multiscale character of the underlying process by being designed to naturally incorporated multiple scales, and such is the framework of networks, of graph theory. (ii) The technological era brings us the possibility to digitally analyze myriads of data in a glimpse. Massive data sets can nowadays be parsed, and with the aid of well-suited algorithms, we can gain access and filter data from many processes, let it be of physical, technological, or even social garment.

1.1 Mapping Time Series to Networks

The idea of mapping time series into graphs seems attractive, because it bridges two prolific fields of modern science as nonlinear signal analysis and complex networks theory, as much that it has attracted the attention of several research groups, which have contributed to the topic with different strategies of mapping. We shall briefly outline some of them.

Zhang and Small [4] developed a method that mapped each cycle of a pseudo-periodic time series into a node in a graph. The connection between nodes was established by a distance threshold in the reconstructed phase space when possible or by the linear correlation coefficient between cycles in the presence of noise. Noisy periodic time series mapped into random graphs while chaotic time series did it into scale-free, small-world networks due to the presence of unstable periodic orbits. This method was subsequently applied to characterize cardiac dynamics.

Xu, in collaboration with Zhang and Small [5], concentrated in the relative frequencies of appearance of four-node motifs inside a particular graph to classify it into a particular superfamily of networks, which corresponded to specific underlying dynamics of the mapped time series. In this case, the method of mapping consisted in embedding the time series in an appropriated phase space, where each point corresponded to a node in the network. A threshold was imposed not only in the minimum distance between two neighbors to be eligible (temporal separation should be greater than the mean period of the data), but also to the maximum number of neighbors a node could have. Different superfamilies were found for chaotic, hyperchaotic, random, and noisy periodic underlying dynamics and unique fingerprints were also found for specific dynamical systems within a family.

Donner et al. [6-8] presented a technique, which was based on the properties of recurrence in the phase space of a dynamical system. More precisely, the recurrence matrix obtained by imposing a threshold in the minimum distance between two points in the phase space was interpreted as the adjacency matrix of an undirected, unweighted graph (as in Ref. [5]). Properties of such graphs at three different scales (local, intermediated, and global) were presented and studied on several paradigmatic systems (Hénon map, Rossler system, Lorenz system, and Bernoulli map). The variation of some of the properties of the graphs with the distance threshold was analyzed, the use of specific measures, such as the local clustering coefficient, was proposed as a way to detect dynamically invariant objects (saddle points or unstable periodic orbits), and studying the graph properties dependent on the embedding dimension was suggested as a means to distinguish between chaotic and stochastic systems.

The Amaral Lab [9] contributed with an idea along the lines of Shirazi et al. [10], Strozzi et al. [11], and Haraguchi et al. [12] of a surjective mapping, which admits an inverse operation. This approach opens the reciprocal possibility of benefiting from time series analysis to study the structure and properties of networks. Time series are treated as Markov processes, and values are grouped in quantiles, which will correspond to nodes in the associated graph. Weighted and directed connections are established between nodes as a function of the probability of transition between quantiles. An inverse operation can be defined without an a priori knowledge of the correspondence between nodes and quantiles just by imposing a continuity condition in the time series by means of a cost function defined on the weighted adjacency matrix of the graph. A random walk is performed on the network and a time series with properties equivalent to the original one is recovered. This method was applied to a battery of cases, which included a periodic-to-random family of processes parameterized by a probability of transition, a pair of chaotic systems (Lorentz and Rossler attractors), and two human heart rate time series. Reciprocally, the inverse map was applied to the metabolic network of Arabidopsis thaliana and to the '97 year Internet Network.

In the same vein of an inverse transformation, Shimada et al. [13] proposed a framework to transform a complex network to a time series, realized by a multidimensional scaling. Applying the transformation method to a model proposed by Watts and Strogatz [14], they show that ring lattices are transformed to periodic time series, small-world networks to noisy periodic time series, and random networks to random time series. They also show that these relationships are analytically held by using the circulant matrix theory and the perturbation theory of linear operators. They generalize the results to several high-dimensional lattices.

Gao and Jin proposed in Ref. [15] a method for constructing complex networks from a time series with each vector point of the reconstructed phase space represented by a single node and edge determined by the phase space distance. Through investigating an extensive range of network topology statistics, they find that the constructed network inherits the main properties of the time series in its structure. Specifically, periodic series and noisy series convert into regular networks and random networks, respectively, and networks generated from chaotic series typically exhibit small-world and scale-free features. Furthermore, they associate different aspects of the dynamics of the time series with the topological indices of the network and demonstrate how such statistics can be used to distinguish different dynamical regimes. Through analyzing the chaotic time series corrupted by measurement noise, they also indicate the antinoise ability of the method.

Sinatra et al. [16] introduced a method to convert an ensemble of sequences of symbols into a weighted directed network, whose nodes are motifs, while the directed links and their weights are defined from statistically significant co-occurrences of two motifs...