Towards a deeper understanding of the Visibility Graph Algorithm

Towards a deeper understanding of the Visibility Graph Algorithm

Alers, Tim (TU Delft Electrical Engineering, Mathematics and Computer Science)

Noldus, R.A.C.J. (mentor)

Delft University of Technology

Electrical Engineering

2023-12-08

The visibility graph has gained traction as a method for time series analysis. Through this method, it is possible to detect or quantify non-linear behavior in a myriad of fields and applications. This thesis explores the variations of visibility graphs, describes how they are used in literature and investigates what lies at the foundation of the transformation from time domain to graph domain. The algorithm for the construction of a visibility graph is used as the starting point. Through mathematical derivation, claims can be made regarding the degree metric of a visibility graph. The average degree for a discrete random time series is defined with high accuracy. Using the inequality sets that can be derived from the adjacency matrix of a visibility graph, certain patterns can be identified as being unattainable for a visibility graph. The information retention is investigated by comparing the Shannon Entropy of both a time series and the visibility graph that is constructed from it. The loss of information can be quantified, but only for short discrete series with low sampling depth. These findings are reported in this thesis, along with some insights that could be the subject of further research to deepen the understanding or enhance the use of the visibility graph algorithm.

Visibility Graph
Time series analysis
Information theory
Expected degree

http://resolver.tudelft.nl/uuid:13dfd949-b3cc-4ccf-b6be-5493cfd3a775

Student theses

master thesis

© 2023 Tim Alers