Visibility graphs and symbolic dynamics
arXiv:1704.06467 · doi:10.1016/j.physd.2018.04.001
Abstract
Visibility algorithms are a family of geometric and ordering criteria by which a real-valued time series of N data is mapped into a graph of N nodes. This graph has been shown to often inherit in its topology non-trivial properties of the series structure, and can thus be seen as a combinatorial representation of a dynamical system. Here we explore in some detail the relation between visibility graphs and symbolic dynamics. To do that, we consider the degree sequence of horizontal visibility graphs generated by the one-parameter logistic map, for a range of values of the parameter for which the map shows chaotic behaviour. Numerically, we observe that in the chaotic region the block entropies of these sequences systematically converge to the Lyapunov exponent of the system. Via Pesin identity, this in turn suggests that these block entropies are converging to the Kolmogorov- Sinai entropy of the map, which ultimately suggests that the algorithm is implicitly and adaptively constructing phase space partitions which might have the generating property. To give analytical insight, we explore the relation k(x), x \in[0,1] that, for a given datum with value x, assigns in graph space a node with degree k. In the case of the out-degree sequence, such relation is indeed a piece-wise constant function. By making use of explicit methods and tools from symbolic dynamics we are able to analytically show that the algorithm indeed performs an effective partition of the phase space and that such partition is naturally expressed as a countable union of subintervals, where the endpoints of each subinterval are related to the fixed point structure of the iterates of the map and the subinterval enumeration is associated with particular ordering structures that we called motifs.
References in corpus (21)
- From time series to complex networks: the visibility graph
- The Visibility Graph: a new method for estimating the Hurst exponent of fractional Brownian motion
- Description of stochastic and chaotic series using visibility graphs
- Network structure of multivariate time series
- Time series irreversibility: a visibility graph approach
- Feigenbaum graphs: a complex network perspective of chaos
- Testing time series irreversibility using complex network methods
- A characterization of horizontal visibility graphs and combinatorics on words
- Analytical properties of horizontal visibility graphs in the Feigenbaum scenario
- Time reversibility from visibility graphs of non-stationary processes
- Sequential visibility-graph motifs
- Unveiling temporal correlations characteristic to phase transition in the intensity of a fibre laser radiation
- Quantifying the dynamical complexity of time series
- On the degree distribution of horizontal visibility graphs associated to Markov processes and dynamical systems: diagrammatic and variational approaches
- Horizontal Visibility graphs generated by type-I intermittency
- Sequential motif profile of natural visibility graphs
- Fully Developed Turbulence in the view of Horizontal Visibility Graphs
- Visibility graph analysis of solar wind velocity
- Canonical Horizontal Visibility Graphs are uniquely determined by their degree sequence
- Quasiperiodic graphs: structural design, scaling and entropic properties
- Generalized Statistical Mechanics at the Onset of Chaos