Canonical Horizontal Visibility Graphs are uniquely determined by their degree sequence
arXiv:1605.05222 · doi:10.1140/epjst/e2016-60164-1
Abstract
Horizontal visibility graphs (HVGs) are graphs constructed in correspondence with number sequences that have been introduced and explored recently in the context of graph-theoretical time series analysis. In most of the cases simple measures based on the degree sequence (or functionals of these such as entropies over degree and joint degree distributions) appear to be highly informative features for automatic classification and provide nontrivial information on the associated dynam- ical process, working even better than more sophisticated topological metrics. It is thus an open question why these seemingly simple measures capture so much information. Here we prove that, under suitable conditions, there exist a bijection between the adjacency matrix of an HVG and its degree sequence, and we give an explicit construction of such bijection. As a consequence, under these conditions HVGs are unigraphs and the degree sequence fully encapsulates all the information of these graphs, thereby giving a plausible reason for its apparently unreasonable effectiveness.
References in corpus (12)
- The structure and function of complex networks
- From time series to complex networks: the visibility graph
- Testing time series irreversibility using complex network methods
- A characterization of horizontal visibility graphs and combinatorics on words
- Analytical properties of horizontal visibility graphs in the Feigenbaum scenario
- Sequential visibility-graph motifs
- Unveiling temporal correlations characteristic to phase transition in the intensity of a fibre laser radiation
- Horizontal Visibility graphs generated by type-I intermittency
- On the degree distribution of horizontal visibility graphs associated to Markov processes and dynamical systems: diagrammatic and variational approaches
- Fully Developed Turbulence in the view of Horizontal Visibility Graphs
- Visibility graph analysis of solar wind velocity
- Quasiperiodic graphs: structural design, scaling and entropic properties
Cited by in corpus (11)
- Complex network approaches to nonlinear time series analysis
- Visibility graphs for image processing
- Visibility graphs and symbolic dynamics
- Visibility graphs of random scalar fields and spatial data
- On the spectral properties of Feigenbaum graphs
- Advancing Through Terrains
- Haros graphs: an exotic representation of real numbers
- On the degree distribution of Haros graphs
- Horizon Visibility Graphs and Time Series Merge Trees are Dual
- Chaotic renormalization group flow and entropy gradients over Haros graphs
- Counting Horizontal Visibility Graphs