Towards a deeper understanding of the Visibility Graph Algorithm

Master thesis (2023)

Authors

T.J. Alers Electrical Engineering, Mathematics and Computer Science

Contributors

R.A.C.J. Noldus Network Architectures and Services - EEMCS (mentor)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Tim Alers
More Info
expand_more

Published Date

08-12-2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.