Horizontal visibility graphs: exact results for random time series.

By B. Luque, Lucas Lacasa, Fernando J. Ballesteros, Jordi Luque. Physical review. E, Statistical, nonlinear, and soft matter physics, 2009

721 citations recorded by the source corpus.

The visibility algorithm has been recently introduced as a mapping between time series and complex networks. This procedure allows us 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 with random series, namely, the degree distribution, the clustering coefficient, and the 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), independent of the probability distribution from which the series was generated. Accordingly, visibility graphs with other P(k) are related to nonrandom 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 independent and identically distributed (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 that are conjectured to be random are analyzed.

Subfields: Computer Vision and Pattern Recognition, Economics and Econometrics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/370b784d04cb952cfac2b4d179ddfd9dfb997288

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Economics and Econometrics

In Statistical and Nonlinear Physics

Citations in the corpus

Complex network approaches to nonlinear time series analysis (2019, methodology): “[59,234] proposed utilizing a simplified criterion of horizontal visibility for transforming a time series into a complex network.”
Recurrence networks—a novel paradigm for nonlinear time series analysis (2009, background): “Recently, a slightly modified approach of horizontal visibility graphs has been proposed and applied to certain random time series [74].”
Exact results of the limited penetrable horizontal visibility graph associated to random time series and its application (2017, neutral): “= = ( ) d LPHVG t LPHVG t a a a a [ ( ), ( )] , where A and A (14) m n i L”
Analysis and Classification of Sleep Stages Based on Difference Visibility Graphs From a Single-Channel EEG Signal (2014, methodology): “have been used to distinguish chaotic series from random series [23].”
Statistical properties of visibility graph of energy dissipation rates in three-dimensional fully developed turbulence (2009, methodology): “n which the multifractal nature of the time series has a negligible inﬂuence [18]. The visibility algorithm can be simpliﬁed to a variant termed the horizontal visibility algorithm, which is solvable [20]. The visibility algorithm has been diversely used to investigate stock market indices [18, 21],”
Irreversibility and complex network behavior of stream flow fluctuations (2016, background): “[28] as a special case of the visibility 10 algorithm [20,21] to map stream flow time series into graphs.”
Quantification of network structural dissimilarities (2017, methodology): “We compare these networks (Power Grid and Euroroad) with other well-known tree-like structures, as are the case of networks constructed via the horizontal visibility graph 53 , from fractional Brownian motion (fBm) time series, with different Hurst exponents ( H ) 54 .”