Visibility graphs and symbolic dynamics

DOI10.1016/J.PHYSD.2018.04.001zbMATH Open1392.37012arXiv1704.06467OpenAlexW2609311736WikidataQ130038201 ScholiaQ130038201MaRDI QIDQ725232FDOQ725232

Authors: Lucas Lacasa, Wolfram Just 

Publication date: 1 August 2018

Published in: Physica D (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1704.06467

Recommendations

• Analytical properties of horizontal visibility graphs in the Feigenbaum scenario
• Horizontal Visibility graphs generated by type-II intermittency
• Feigenbaum graphs at the onset of chaos
• From time series to complex networks: the visibility graph
• On the degree distribution of horizontal visibility graphs associated with Markov processes and dynamical systems: diagrammatic and variational approaches

zbMATH Keywords

symbolic dynamicsKolmogorov-Sinai entropyvisibility graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Time series analysis of dynamical systems (37M10) Symbolic dynamics (37B10)

Cites Work

• An inequality for the entropy of differentiable maps
• Some properties of absolutely continuous invariant measures on an interval
• Entropy of interval maps via permutations
• Quasiperiodic graphs: structural design, scaling and entropic properties
• Analytical properties of horizontal visibility graphs in the Feigenbaum scenario
• Generalized statistical mechanics at the onset of chaos
• From time series to complex networks: the visibility graph
• On the abundance of aperiodic behaviour for maps on the interval
• On the irrationality of certain series
• Concepts and results in chaotic dynamics. A short course
• Multicomponent dynamical systems: SRB measures and phase transitions
• Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise
• Chaos in nonlinear difference equations. I: Qualitative study of (formal) chaos.
• The application of complex network time series analysis in turbulent heated jets
• On the degree distribution of horizontal visibility graphs associated with Markov processes and dynamical systems: diagrammatic and variational approaches
• Fully developed turbulence in the view of horizontal visibility graphs

Cited In (10)

• Symbolic dynamics and the category of graphs
• Symbolic dynamics for a kinds of piecewise smooth maps
• Identification of healthy and pathological heartbeat dynamics based on ECG-waveform using multifractal spectrum
• Horizontal visibility graph of a random restricted growth sequence
• The visibility graph of \(n\)-bonacci sequence
• Reciprocal characterization from multivariate time series to multilayer complex networks
• On the spectral properties of Feigenbaum graphs
• SYMBOLIC DYNAMICS GENERATED BY A COMBINATION OF GRAPHS
• Refined composite multiscale phase Rényi dispersion entropy for complexity measure
• A review of symbolic dynamics and symbolic reconstruction of dynamical systems

This page was built for publication: Visibility graphs and symbolic dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q725232)