Visibility graphs and symbolic dynamics
 Citation data:

Physica D: Nonlinear Phenomena, ISSN: 01672789, Vol: 374, Page: 3544
 Publication Year:
 2018
 Repository URL:
 http://arxiv.org/abs/1704.06467
 DOI:
 10.1016/j.physd.2018.04.001
 Author(s):
 Publisher(s):
 Tags:
 Physics and Astronomy; Nonlinear Sciences  Chaotic Dynamics; Mathematics  Dynamical Systems; Physics  Data Analysis, Statistics and Probability
 Most Recent Tweet View All Tweets
article description
Visibility algorithms are a family of geometric and ordering criteria by which a realvalued time series of N data is mapped into a graph of N nodes. This graph has been shown to often inherit in its topology nontrivial 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 oneparameter 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 time series. Hence, Pesin’s identity suggests that these block entropies are converging to the Kolmogorov–Sinai entropy of the physical measure, 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∈[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 piecewise 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.