Source-linked AI summary
Horizontal visibility graphs: exact results for random time series
Bartolo Luque, Lucas Lacasa, Fernando Ballesteros, Jordi Luque
TL;DR
The paper develops a simpler, analytically solvable horizontal visibility algorithm for mapping time series to graphs and characterizing random-series topology. It derives distribution-independent results for i.i.d. series and shows that the method distinguishes low- and high-dimensional chaotic series, including noisy cases, from the random baseline.
Problem
Distinguishing random from chaotic time series is difficult for high-dimensional or noisy chaos, motivating a direct graph-based randomness test.
Method
The paper introduces horizontal visibility graphs and analytically studies their degree distribution, clustering coefficient, and mean path length for i.i.d. random series.
Results
The random-series degree distribution is P(k) = (1/3)(2/3)^(k−2) for every probability distribution, while the method distinguishes low-dimensional noisy and high-dimensional chaotic series from randomness.
Takeaways & Limitations
Horizontal visibility graphs provide a simple randomness discriminator whose random baseline is universal and whose finite-series predictions are numerically reliable.
Takeaways & Limitations
The paper’s exact theory addresses i.i.d. random variables, while distinguishing determinism from generic stochastic processes lies beyond its scope.
Abstract
from arXiv · showhide
The visibility algorithm has been recently introduced as a mapping between time series and complex networks. This procedure allows to apply methods of complex network theory for characterizing time series. In this work we present the horizontal visibility algorithm, a geometrically simpler and analytically solvable version of our former algorithm, focusing on the mapping of random series (series of independent identically distributed random variables). After presenting some properties of the algorithm, we present exact results on the topological properties of graphs associated to random series, namely the degree distribution, clustering coefficient, and mean path length. We show that the horizontal visibility algorithm stands as a simple method to discriminate randomness in time series, since any random series maps to a graph with an exponential degree distribution of the shape P(k) = (1/3)(2/3)**(k-2), independently of the probability distribution from which the series was generated. Accordingly, visibility graphs with other P(k) are related to non-random series. Numerical simulations confirm the accuracy of the theorems for finite series. In a second part, we show that the method is able to distinguish chaotic series from i.i.d. theory, studying the following situations: (i) noise-free low-dimensional chaotic series, (ii) low-dimensional noisy chaotic series, even in the presence of large amounts of noise, and (iii) high-dimensional chaotic series (coupled map lattice), without needs for additional techniques such as surrogate data or noise reduction methods. Finally, heuristic arguments are given to explain the topological properties of chaotic series and several sequences which are conjectured to be random are analyzed.
I. INTRODUCTION
The paper introduces horizontal visibility graphs as a geometrically simpler, analytically solvable mapping from time series to networks. It develops exact random-series results and uses deviations from the resulting universal topology to characterize non-random dynamics.
- I. INTRODUCTION: The visibility algorithm maps each time-series datum to a graph node, connecting pairs that satisfy a geometric visibility criterion.This mapping enables complex-network techniques for time-series characterization.
- I. INTRODUCTION: Periodic series produce motif-repeating visibility graphs whose degree distributions contain finitely many peaks, motivating a geometric-transform interpretation.The degree-distribution peaks are compared with the finite spectral peaks of periodic signals under the Discrete Fourier Transform.
- I. INTRODUCTION: The horizontal criterion connects x_i and x_j when both endpoint heights exceed every intermediate height, producing a geometrically simpler graph construction.The horizontal visibility graph is a subgraph of the original visibility graph and remains connected and affine-invariant.
- I. INTRODUCTION: For random series, the degree-distribution derivation enumerates bounding and inner-data configurations, including arbitrarily many hidden data between visible points.The calculation uses the cumulative distribution F(x) to combine configuration probabilities.
A. Degree versus height
The paper relates node degree to datum height in horizontal visibility graphs, showing that higher-valued data correspond to more connected nodes and that finite-series simulations match theory.
- A. Degree versus height: P(k|x) denotes the conditional probability that a node has degree k given datum height x.The average degree K(x) is then defined from this conditional distribution.
- A. Degree versus height: K(x) = 2 − 2 ln(1 − F(x)) gives the average degree for nodes associated with height x.Here F(x) is the cumulative distribution function of the data.
- A. Degree versus height: K(x) increases monotonically with datum height because F(x) and ln(x) are monotonically increasing functions.This establishes a direct ordering between data height and expected node degree.
- A. Degree versus height: The hubs are nodes associated with the largest data values, corresponding to extreme events in the series.The theoretical prediction identifies high-valued observations as the most connected nodes.
- A. Degree versus height: Numerical results for 10^6 uniformly distributed data show perfect agreement between measured average degree and equation 17.The simulations use F(x) = x for the uniform distribution.
B. Local clustering coefficient distribution
The local clustering coefficient is derived geometrically from node degree, and the resulting clustering distribution agrees closely with finite-series simulations while indicating hierarchical structure.
- B. Local clustering coefficient distribution: The local clustering coefficient C measures the fraction of a node’s neighbors that are mutually connected.It is obtained by counting triangles involving the node and normalizing by the possible triangles.
- B. Local clustering coefficient distribution: For degree k = 2, the two neighboring bounding data are mutually visible, giving C(k = 2) = 1.This configuration forms one triangle.
- B. Local clustering coefficient distribution: For degree k = 3, only 2 of 6 possible neighbor pairs form triangles, giving C(k = 3) = 2/6.The inner datum is visible to only one of the bounding data.
- B. Local clustering coefficient distribution: The relation between degree k and clustering coefficient C indicates a hierarchical structure.The paper uses this relation to derive the local clustering coefficient distribution P(C).
- B. Local clustering coefficient distribution: For a random series of 10^6 data, the simulated clustering distribution agrees excellently with the theoretical prediction in equation 19.The numerical distribution is compared with the theoretical curve in figure 6.
C. Long distance visibility, mean degree and mean path length
For i.i.d. random series, long-distance visibility has a distribution-independent probability, yielding logarithmic mean path length and a small-world graph structure.
- The clustering distribution for 10^6 uniformly distributed random data agrees excellently with the theoretical prediction under periodic boundary conditions.The plotted prediction is P(C) = (1/3)(2/3)^(2/C−2).
- P(n) = 2/[n(n + 1)] is the probability that two nodes separated by n intermediate data are connected, independently of the random variable’s distribution.A combinatorial argument places the two largest values in n(n + 1) positions, with two arrangements producing visibility.
- The adjacency matrix is predominantly concentrated around the main diagonal, with sparse long-range shortcuts governed by P(n).Every datum sees its nearest neighbors, ensuring connectivity, while longer links create a quasi-homogeneous small-world structure.
- L(N) scales logarithmically with system size, showing that horizontal visibility graphs of generic random series are small-world.The numerical fit is L(N) = 1.3 log(N) − 1.7.
V. APPLICATION OF THE THEORY TO DISCRIMINATE CHAOTIC SERIES
The paper applies horizontal visibility theory to distinguish chaotic dynamics from i.i.d. randomness, including difficult cases involving noise and high-dimensional chaos.
- The method is evaluated as a practical test for distinguishing random signals from chaotic ones in finite time series.The motivation is the difficulty of reliably separating stochastic and deterministic chaos, especially for highly chaotic or noisy data.
- Random-series mean path lengths grow logarithmically, providing a theoretical topological reference for the discrimination task.The reported numerical fit is L(N) = 1.3 log(N) − 1.7.
- Horizontal visibility graphs with topological properties different from the random-series theory are not uncorrelated random series.The paper explores the reliability of this criterion on finite series.
- The application covers noise-free low-dimensional chaos, noisy low-dimensional chaos, and high-dimensional chaotic series.The stated high-dimensional case is a coupled map lattice, and the noisy case includes noise levels up to 100% by amplitude.
A. Low-dimensional chaos
The method is tested on fully chaotic low-dimensional maps and shown to capture temporal structure beyond what appears after shuffling the data.
- Noise-free simulations use the Logistic map at µ = 4 and the fully chaotic Hénon map to calculate horizontal-visibility degree distributions.The paper compares these distributions with the theoretical random-series prediction in a semi-log plot.
- Shuffling the data restores the random-series degree distribution because it breaks temporal correlations.For the Logistic map, the shuffled series is equivalent to randomness drawn from the system’s beta-distributed invariant measure.
- The degree distribution functions as a topological analogue of autocorrelation with additional sensitivity to nonlinear correlations.The method operates on graph topology rather than directly in the time or frequency domain.
B. Noisy chaotic series
The paper tests robustness to measurement noise using a fully chaotic Logistic-map signal and compares noisy cases with the random-series prediction.
- Measurement noise is added to a fully chaotic Logistic-map signal at µ = 4.0 to test the algorithm’s robustness.The motivation is that conventional chaos indicators can be misled when noise destroys the fractal structure of a chaotic attractor.
- Figure 10 compares 10% and 100% amplitude noise against the theoretical random-series degree distribution.Triangles denote 10% noise and circles denote 100% noise; the solid line is P(k) = (1/3)(2/3)^(k−2).
C. High dimensional chaos: Coupled Map Lattice
The authors use a coupled map lattice of 1000 Logistic maps to generate high-dimensional chaotic series and compare its visibility-graph degree distribution with the random-series prediction. A χ2 test rejects randomness despite smaller deviations than in low-dimensional chaos.
- C. High dimensional chaos: Coupled Map Lattice: 1000 coupled Logistic maps generate a high-dimensional chaotic series with estimated attractor dimension D2 = 800.The maps use f(x) = 4x(1 −x) and coupling strength ǫ = 0.4.
- C. High dimensional chaos: Coupled Map Lattice: The graph’s degree distribution is compared with the random-series prediction P(k) = (1/3)(2/3)k−2.Figure 11 presents the chaotic-series distribution alongside the theoretical random-series curve.
- C. High dimensional chaos: Coupled Map Lattice: A χ2 goodness-of-fit test clearly rejects randomness for the high-dimensional chaotic series.The deviations from the random prediction are less evident than for low-dimensional chaotic series, but the test still distinguishes high-dimensional chaos from randomness.
D. Topological properties of chaotic series
Chaotic-series visibility graphs can retain exponential degree-distribution tails while differing from the random-series prediction. The paper relates these deviations heuristically to extreme-event visibility and conjectures a connection with Poincaré recurrence statistics.
- D. Topological properties of chaotic series: Logistic and Hénon chaotic series show exponential degree-distribution tails that differ from the random-series prediction in equation 15.The difference is observed in the associated visibility graphs rather than as a departure from exponential decay itself.
- D. Topological properties of chaotic series: Highly visible data act as hubs whose degrees are truncated by other extreme data.The paper links hub degree to extreme events and explains the tail through their visibility relationships.
- D. Topological properties of chaotic series: A χ2 goodness-of-fit test does not reject the normality of π, e, and ln 2.The tested sequences use the first 6·105 digits, grouped into tuples of six to form series of 105 data.
- D. Topological properties of chaotic series: The functional form of P(k) is conjectured to relate to chaotic-series Poincaré recurrence-time statistics.The paper attributes deviations from Poissonian statistics to deterministic effects and leaves the connection for future work.
E. Stochastic processes versus chaos
The paper distinguishes chaos from i.i.d. randomness but explicitly limits its theory to uncorrelated random series. It conjectures broader discrimination of chaos from colored noise and fractional Brownian motion based on their different visibility-graph forms.
- E. Stochastic processes versus chaos: The theory addresses only i.i.d. variables, so distinguishing determinism from generic stochastic processes lies beyond this work’s scope.Examples of broader processes include fractional Brownian motion and high-order Markov models.
- E. Stochastic processes versus chaos: Fractional Brownian motions and colored noise are reported to map into scale-free visibility graphs differing from chaotic-series and i.i.d. forms.The paper presents this as support for a conjecture rather than as a result established by the present theory.
VI. SOME CONJECTURED RANDOM LIKE SERIES: DECIMAL EXPANSION OF NORMAL NUMBERS
The paper treats decimal expansions of normal numbers as series whose visibility-graph degree distributions should follow the i.i.d. random prediction. It applies goodness-of-fit tests to conjectured normal constants while noting that continuous flows are not directly covered by the theory.
- VI. SOME CONJECTURED RANDOM LIKE SERIES: DECIMAL EXPANSION OF NORMAL NUMBERS: A normal number has equally likely k-tuples in every base, so its decimal expansion can be analyzed as a series.For decimal expansions, every string of a fixed length is expected to occur with equal likelihood.
- VI. SOME CONJECTURED RANDOM LIKE SERIES: DECIMAL EXPANSION OF NORMAL NUMBERS: The visibility graph of a normal number’s decimal expansion should follow equation 15, the degree-distribution prediction for random series.A deviation from that equation would imply non-normality of the number.
- VI. SOME CONJECTURED RANDOM LIKE SERIES: DECIMAL EXPANSION OF NORMAL NUMBERS: The i.i.d. theory is not straightforward to compare with visibility graphs from continuous flows because discretization preserves continuity properties absent from the theory.The paper defers this comparison to further work.