Source-linked AI summary
From time series to complex networks: the visibility graph
Lucas Lacasa, Bartolo Luque, Fernando Ballesteros, Jordi Luque, Juan Carlos Nuno
TL;DR
The paper addresses whether graph theory can characterize time-series structure by introducing a visibility algorithm that maps series into networks. The resulting topology preserves distinctions among periodic, random, and fractal series, while the binary undirected mapping has recognized scope limitations.
Problem
The paper asks whether a graph derived from a time series inherits enough of the series’ structure to characterize the generating process using graph theory.
Method
The visibility algorithm maps time-series data into graph nodes and connects pairs whose visibility line is unobstructed by intermediate data.
Results
Periodic, random, and fractal series map respectively to regular, random, and scale-free graphs, with fractal examples exhibiting power-law degree distributions.
Takeaways & Limitations
The method builds a bridge between complex-network theory and time-series analysis, enabling network measures to characterize series from a new point of view.
Takeaways & Limitations
The paper studies only undirected graphs, and binary adjacency can make quantitatively different series share the same visibility graph.
Abstract
from arXiv · showhide
In this work we present a simple and fast computational method, the visibility algorithm, that converts a time series into a graph. The constructed graph inherits several properties of the series in its structure. Thereby, periodic series convert into regular graphs, and random series do so into random graphs. Moreover, fractal series convert into scale-free networks, enhancing the fact that power law degree distributions are related to fractality, something highly discussed recently. Some remarkable examples and analytical tools are outlined in order to test the method's reliability. Many different measures, recently developed in the complex network theory, could by means of this new approach characterize time series from a new point of view.
Resumen
The visibility algorithm maps time series to graphs whose topology preserves structural properties such as periodicity, randomness, and fractality. Network analysis then characterizes series while revealing distinctions among fractal and random dynamics, with limitations from binary, undirected representations.
- Method: The visibility algorithm links two time-series data points when the line between them does not intersect any intermediate data height.Each time-series datum becomes a node, and visibility determines graph connectivity.
- Periodic series: Periodic series map to regular graphs whose discrete degree distributions reflect the series periods.The graph inherits the regularity produced by periodic repetition of a pattern.
- Random series: Random series retain their random nature in the visibility graph, whose degree-distribution shape depends on the generating random process.For the uniform random example, rare large values act as hubs and produce an exponential tail rather than a purely Poisson distribution.
- Fractal series: Fractal series produce power-law degree distributions and scale-free visibility graphs across stochastic Brownian and deterministic Conway examples.The examples also differ in network scaling: Brownian motion shows logarithmic mean path length, whereas Conway shows a self-similar power-law relation.
- Limitations and extensions: The method preserves structural properties but loses quantitative information because its binary adjacency matrix can map distinct series to the same graph.Weighted networks are proposed to distinguish examples such as T1 and T2 quantitatively.
- Limitations and extensions: The paper studies undirected graphs; directed visibility graphs and applications including Hurst-exponent estimation are left for further work.A directed formulation would distinguish ingoing and outgoing connectivity and could test time-reversion invariance.
R(t)
The visibility graphs of the random series R(t) and Brownian motion exhibit distinct degree-distribution behavior. The Brownian graph additionally shows scale-free and Small-World characteristics.
- R(t): R(t) has a degree-distribution tail that is clearly exponential, reflecting hubs produced by large-value rare events.The series contains 10^6 values sampled from U[0,1].
- B C: The Brownian visibility graph follows P(k) ∼ k^-α with α = 2,00 ± 0,01.Its mean path length fits L(N) = 1,21 + 0,51 log(N).
- B C: The Brownian network combines scale-free degree distribution with Small-World behavior.The logarithmic scaling of mean path length supports the reported Small-World effect.
B C
Figure 5 presents an iterated fractal series and tracks two quantities, K_r and K_l, across fractal size. Their log-linear behavior is compared with approximations derived from the corresponding equations.
- B C: The left panel shows a fractal series generated by iterating the original A,B,C pattern for p = 10 steps.The construction is displayed as the series’ fractal form.
- B C: The right panel plots K_r and K_l as functions of fractal size.Circles represent K_r and squares represent K_l.
- B C: Because the plot is log-linear, the plotted relation between K_r, K_l, and fractal size is exponential.Straight lines show approximations deduced in equations (4,6).