Source-linked AI summary
Description of stochastic and chaotic series using visibility graphs
Lucas Lacasa, Raul Toral
TL;DR
The paper asks how to distinguish closely related chaotic and stochastic time series for modeling and forecasting. It applies the horizontal visibility algorithm, mapping series to graphs whose exponential degree-distribution slope λ characterizes the process. The exact frontier λ = ln(3/2) separates correlated stochastic from chaotic series, with analytical, numerical, and experimental support.
Problem
Chaotic and stochastic processes share many features, so identifying whether unpredictability arises from deterministic chaos or stochastic dynamics is important for modeling and forecasting.
Method
The paper uses the horizontal visibility algorithm to map time series into graphs and characterize their structure through graph-theoretical properties.
Results
The associated graphs have exponential degree distributions, with correlated stochastic series showing λ > ln(3/2), while chaotic series converge toward the frontier from the opposite direction.
Takeaways & Limitations
λ = ln(3/2) serves as an effective frontier between correlated stochastic and chaotic processes in the horizontal-visibility-graph representation.
Takeaways & Limitations
The characterization of flows remains a limitation of the algorithm.
Abstract
from arXiv · showhide
Nonlinear time series analysis is an active field of research that studies the structure of complex signals in order to derive information of the process that generated those series, for understanding, modeling and forecasting purposes. In the last years, some methods mapping time series to network representations have been proposed. The purpose is to investigate on the properties of the series through graph theoretical tools recently developed in the core of the celebrated complex network theory. Among some other methods, the so-called visibility algorithm has received much attention, since it has been shown that series correlations are captured by the algorithm and translated in the associated graph, opening the possibility of building fruitful connections between time series analysis, nonlinear dynamics, and graph theory. Here we use the horizontal visibility algorithm to characterize and distinguish between correlated stochastic, uncorrelated and chaotic processes. We show that in every case the series maps into a graph with exponential degree distribution P (k) ~ exp(-λk), where the value of λ characterizes the specific process. The frontier between chaotic and correlated stochastic processes, λ = ln(3/2), can be calculated exactly, and some other analytical developments confirm the results provided by extensive numerical simulations and (short) experimental time series.
I. INTRODUCTION
The paper addresses the subtle problem of distinguishing chaotic deterministic dynamics from stochastic processes, proposing a conceptually simple and computationally efficient horizontal-visibility-graph method. The parameter λ both separates these processes and quantifies their degree of chaoticity or stochasticity.
- Motivation: Chaotic and stochastic processes can share many features, making their discrimination important for modeling and forecasting.The distinction concerns whether unpredictability originates in a chaotic deterministic or stochastic dynamical system.
- Motivation: Existing approaches are often phenomenological and computationally complicated, motivating a reliable direct distinction between stochastic and chaotic time series.The paper positions its method as an alternative to these drawbacks.
- Approach: The proposed approach maps time series into networks whose connections capture series structure, then characterizes the resulting graphs with graph-theoretical tools.It uses the visibility algorithm, which translates series correlations into visibility-graph properties.
- Approach: The horizontal visibility algorithm is used to characterize and discriminate chaotic, uncorrelated, and correlated stochastic processes.The method builds on evidence that visibility graphs capture periodicity, fractality, and chaoticity.
- Main findings: P(k) ∼ exp(−λk) describes the degree distribution in each case, with λ < ln(3/2) for chaos and λ > ln(3/2) for correlated stochastic processes.The uncorrelated frontier is λun = ln(3/2) and can be calculated exactly.
- Validation: Analytical developments confirm numerical simulations spanning correlated Gaussian fields, chaotic maps, and short experimental cardiac series.The studied stochastic correlations include long-range power-law and short-range exponential forms.
- Interpretation: The parameter λ also quantifies the degree of chaoticity or stochasticity, while extrinsic noise in mixed time series is captured by the algorithm.The paper further analyzes deviations from the uncorrelated theory and validates results on experimental series.
II. HORIZONTAL VISIBILITY ALGORITHM
The horizontal visibility algorithm maps each time-series datum to a graph node and connects pairs whose horizontal line is unobstructed by intermediate data. For uncorrelated series, the resulting degree distribution is exponential with a universal decay parameter.
- Each time-series datum becomes a node in the horizontal visibility graph.
- Two nodes connect when a horizontal line between their data values intersects no intermediate height.
- The connection rule is expressed by requiring both endpoint values to exceed every intermediate datum.
- For independent identically distributed continuous variables, the associated graph has a specified degree distribution.
- λ_un = ln(3/2) rewrites the uncorrelated degree distribution as P(k) ~ exp(-λ_un k), independently of the continuous generating density.
- Correlations are assessed through deviations from the theoretical uncorrelated value λ = λ_un.
III. CORRELATED STOCHASTIC SERIES
The study examines horizontal-visibility graphs of long- and short-range correlated stochastic series. Both yield exponential degree distributions whose slope depends systematically on correlation strength and approaches the uncorrelated limit.
- The analysis focuses on power-law long-range and exponentially decaying short-range correlated stochastic processes.
- P(k) ~ exp(-λk) fits the large-k degree distributions for both correlation types.
- λ depends monotonically on γ or τ and approaches λ_un = ln(3/2) as correlations vanish.
- For power-law correlations, convergence is slow and remains measurably different from the uncorrelated case even for γ > 4.0.
- Exponential correlations converge faster toward the uncorrelated limit as τ decreases.
- The modified Fourier-filtering procedure removes undesired cut-off effects while accounting for the discrete nature of the series.
A. Application to real cardiac interbeat dynamics
The horizontal-visibility graph is applied to healthy cardiac interbeat series as a real example of a correlated stochastic process. Their exponential degree distributions agree with the theoretical characterization and differ from the uncorrelated benchmark.
- The cardiac data comprise beat-to-beat fluctuations from five young subjects aged 21–34 years with healthy sinus rhythm.
- The series contain about 6000 data points and reproduce the patterns found in the preceding stochastic examples.
- For power-law correlations, λ decreases monotonically as γ increases toward the uncorrelated regime.
- For correlated stochastic series, the characteristic λ exceeds the uncorrelated value even under weak correlations.
- The cardiac HVG has an exponential degree distribution with λ = 0.5 > λ_un, identifying it as correlated stochastic data.
IV. CHAOTIC MAPS
The paper analyzes chaotic series generated by several maps and finds exponential horizontal-visibility degree distributions. Their slope λ remains below the uncorrelated value, increases with chaos dimensionality, and approaches λun = ln(3/2).
- IV. CHAOTIC MAPS: Several chaotic maps, including logistic, tent, Hénon, Lozi, Kaplan–Yorke, and Arnold cat maps, are analyzed through their horizontal visibility graphs.The study also includes α-maps and a delayed Hénon map.
- IV. CHAOTIC MAPS: P(k) ∼ exp(−λk) approximates the degree-distribution tails of chaotic series across the analyzed maps.The distributions are plotted on a semilog scale for series of 2^18 data.
- IV. CHAOTIC MAPS: λ < λun holds in every chaotic-map case, while λ increases monotonically with chaos dimensionality.The reported asymptotic behavior is λ → ln(3/2) at large attractor dimension.
- IV. CHAOTIC MAPS: The uncorrelated degree distribution is a limiting case of the chaotic distributions, with convergence toward λun occurring from below.This contrasts with the convergence behavior reported for stochastic processes.
- IV. CHAOTIC MAPS: λ = ln(3/2) acts as an effective frontier: chaotic series lie below it, whereas correlated stochastic processes lie above it.The comparison includes power-law and exponentially correlated stochastic series and several chaotic maps.
V. HEURISTICS
The heuristic analysis explains the slope ordering through variability and visibility. Correlated stochastic series suppress large-degree nodes, while deterministic chaotic continuity increases their probability, yielding λchaos < λun < λstoch.
- V. HEURISTICS: Correlations reduce data variability relative to uncorrelated series and therefore reduce the number of nodes with large degree.In the infinite-correlation limit, the series becomes constant and λ diverges.
- V. HEURISTICS: λstoch > λun follows as correlated stochastic processes approach the uncorrelated value λun = ln(3/2) when correlations become small.The argument applies to the small-correlation limit.
- V. HEURISTICS: Chaotic trajectories are continuous along their attractors, producing a smoothing effect that increases the probability of larger node degrees.Uncorrelated series are described as rougher and more likely to contain smaller-degree nodes.
- V. HEURISTICS: λchaos < λun < λstoch summarizes the slope ordering supported by the heuristic argument and numerical results.The exponential form is linked to recurrence in chaotic series and return distributions in Poisson processes for stochastic series.
VI. ANALYTICAL DEVELOPMENTS
The analytical developments derive exact or numerical results for selected Markovian processes and compare them with simulations. General closed expressions remain difficult for correlated processes because long-range dependence prevents factorization.
- VI. ANALYTICAL DEVELOPMENTS: P(k) = (1/3)(2/3)^(k−2) is the previously proved degree distribution for uncorrelated random series.This result provides the uncorrelated reference case for later comparisons.
- VI. ANALYTICAL DEVELOPMENTS: General closed expressions for correlated stochastic or chaotic processes are difficult because long-range correlations prevent probability factorization.The resulting calculations are typically impossible to solve in the general case.
- VI. ANALYTICAL DEVELOPMENTS: For Markovian systems, global dependence reduces to one-step dependence, enabling exact expressions for selected probabilities such as P(2) and P(3).The Ornstein–Uhlenbeck process is used as the principal example.
- VI. ANALYTICAL DEVELOPMENTS: The study compares analytical calculations for Ornstein–Uhlenbeck P(2) and P(3) with numerical results across different correlation times.These comparisons are summarized in Table I.
A. Ornstein-Uhlenbeck process
For the Ornstein–Uhlenbeck process, the paper uses its Markov property to derive numerical procedures for POU(2) and POU(3). The resulting values agree with numerical simulations for several correlation times.
- A. Ornstein-Uhlenbeck process: The Ornstein–Uhlenbeck process is treated as a short-range correlated stationary Markov series with C(t) ∼ exp(−t/τ).Its transition kernel uses K = exp(−1/τ).
- A. Ornstein-Uhlenbeck process: The Markov factorization f(x−1, x0, x1) = f(x−1)f(x0|x−1)f(x1|x0) reduces the dependence needed for the calculation.This property supports the analytical treatment of local visibility probabilities.
- A. Ornstein-Uhlenbeck process: 0.3012, 0.3211, and 0.3331 are the calculated values of POU(2) for τ = 1.0, 0.5, and 0.1, respectively.The values are reported in perfect agreement with earlier numerical results.
- A. Ornstein-Uhlenbeck process: 0.230, 0.226, and 0.221 are the calculated values of POU(3) for τ = 1.0, 0.5, and 0.1, respectively.These results are reported in good agreement with the numerical results in Table I.
B. Logistic map
The section develops analytical calculations for horizontal-visibility degree probabilities in chaotic maps, using natural measures and deterministic transition probabilities. For the fully chaotic logistic map, the calculation agrees with numerical results.
- Chaotic maps have the Markov property, allowing an analytical treatment despite being deterministic.
- For trajectories on a chaotic attractor, a natural measure describes the long-run proportion of time spent in different attractor regions.
- For the logistic map with µ = 4, the attractor is [0, 1], and its probability measure is a beta distribution with a = 0.5 and b = 0.5.
- The deterministic transition probability is represented using a Dirac delta distribution, replacing stochastic transition probabilities in the calculation.
- The resulting analytical value agrees with numerical results, and the development can be applied to other chaotic maps with well-defined natural measures.
VII. COMMENT ON NOISY PERIODIC MAPS
The section analyzes how horizontal visibility graphs represent periodic series with extrinsic and intrinsic noise. Extrinsic noise creates an exponential tail with slope ln(3/2), whereas intrinsic noise can produce a difficult-to-distinguish pathological case.
- Periodic series produce horizontal-visibility graphs whose degree distributions have finite, period-related structure.
- Adding extrinsic uncorrelated noise increases the visibility of high-valued nodes and perturbs the periodic degree distribution.
- For a period-2 series with Gaussian noise N(0, 0.05), numerical results confirm the analytical degree distribution; finite-size effects make P(3) nonzero.
- The algorithm detects both the periodic signal and extrinsic noise, but intrinsic noise in periodic maps can generate a chaotic-like exponential tail with λ < λun.
- An exponential tail with slope ln(3/2) arises when a small amount of extrinsic noise is added to a periodic signal.
- In this pathological case, the algorithm fails to determine whether the entropy source is stochastic or chaotic, motivating further investigation.
VIII. CONCLUSION
The conclusion presents horizontal visibility graphs as a way to characterize correlated stochastic, uncorrelated, and chaotic series through exponential degree distributions. The slope λ separates the processes around the exact frontier ln(3/2), while noisy maps and continuous-time flows remain open issues.
- Correlated stochastic series map into horizontal-visibility graphs with exponential degree distributions having λ > ln(3/2).
- For weak correlations, the slope slowly approaches its asymptotic value, and results are confirmed for a physiological series with long-range correlations.
- Chaotic series show the opposite convergence, with degree-distribution slopes approaching ln(3/2) from below.
- Uncorrelated random series have the exact slope ln(3/2), independently of their probability density.
- The horizontal visibility algorithm is fast, taking a few seconds to generate a graph for N = 2^18 data on a standard personal computer.
- Applications include characterizing physiological and natural signals before selecting among modeling frameworks.
- Further work should address Lyapunov exponents, short-term memory, noisy maps, and continuous-time flows, which remain limitations or open problems.
IX. APPENDIX: STATISTICAL ERROR IN λ
The appendix discusses uncertainty in estimating λ from finite time series and exponential fits. It identifies finite-degree statistics, measurement errors, and short-series averaging choices as practical considerations.
- The slope λ is calculated by fitting the tail of the horizontal-visibility degree distribution to an exponential function.
- Finite time series lack statistics for large graph degrees, while experimental series may contain measurement errors.
- For the considered correlated stochastic and chaotic systems, finite-size effects appear less relevant for relatively large series with N > 2^14.
- Partitioning a stationary series into s subsamples allows λ estimates from each subsample, with uncertainty given by their standard deviation.
- For very short series of order O(10^3), ensemble averaging is more appropriate than the partitioning procedure.
- A power-law correlated stochastic process with C(t) = t^-γ and γ = 1.5 has an associated slope λ = 0.54.