1. Visibility Graph Algorithm

visi.jpg
Figure1. Visibility Graph for time series X

Visibility Graph algorithm plots time series $X$ to its Visibility Graph. Lets assume the $i^th$ point of time series is $X_{i}$. In this graph two nodes or vertices($X_{m}$ and $X_{n}$) are supposed to be connected by a two-way edge if and only if the equation \eqref{eq:ve} is valid.

\begin{equation}
\begin{split}
X_{m+j} < X_{n} + (\frac{n - (m+j)}{n-m})\cdot(X_m - X_n) \end{split} \begin{split} \forall j \in Z^{+} and j < (n-m) \end{split} \label{eq:ve} \end{equation} It is shown in the Figure 1, that the nodes $X_{m}$ and $X_{n}$, where $m=i$ and $n=i+6$, are visible to each other only if the equation \eqref{eq:ve} is valid. It is evident that two sequential points of the time series can always see each other and thereby sequential nodes are always connected. 2. Power of Scale-freeness of Visibility Graph - PSVG The degree of a node or vertex in a graph \mbox{-} here Visibility Graph, is the number of connections or edges the node has with the rest of the nodes in the graph. The degree distribution $P(k)$ of a network is therefore defined as the fraction of nodes with degree $k$, with respect to the total number of nodes present in the network. So, if there are $n_k$ number of nodes in the network, having degree $k$ and total number of nodes in total in a network is $n$, then we define $P(k) = n_k/n$ for all possible values of $k$. As per Lacasa et al.[3],[2] and Ahmadlou et al.[1], the degree of scale-freeness of a Visibility Graph corresponds to the amount of fractality and complexity of the time series. According to the scale-freeness property of Visibility Graph, the degree distribution of its nodes should follow power-law, i,e, $P(k) \sim k^{-\lambda_p}$, where $\lambda_p$ is a constant and it is called the \textbf{Power of the Scale-freeness in Visibility Graph-PSVG}. Hence $\lambda_p$ or the PSVG corresponds to the amount of self-similarity, fractality and a measure of complexity of the time series. As the fractal dimension measures the amount of self-similarity of a time series, $\lambda_p$ indicates the FD \mbox{-} Fractal Dimension of the signal[3],[2],[1]. It is also observed that there is an inverse linear relationship between PSVG-$\lambda_p$ and Hurst exponent of the associated time series[2]. 2.1. Scale freeness and positive plane As the visibility graph is an algorithm that maps a time series into a graph, the methods of complex network analysis can also be applied to characterize time series from a brand new viewpoint. Graph theory techniques are applied for quantifying long-range dependence and fractal nature in time series. Thereby the analysis ultimately does not depend on the particular data point values. However, it is tough to calculate the visibility if the series has negative values The time series thereby should be converted to positive planes as the above algorithm is valid for positive $x$ values in the time series. This can be achieved by adding a specific constant value to each data point so that there are no negative values in the resulting dataseries.

References
  1. M. , H. and A. , "Improved visibility graph fractality with application for the diagnosis of Autism Spectrum Disorder", "Physica A: Statistical Mechanics and its Applications" "391"(0000), no. "20", 4720---4726.
  2. .. , B. , J. and J. , The visibility graph: A new method for estimating the Hurst exponent of fractional Brownian motion, EPL (Europhysics Letters) 86(2009), no. 3, 30001.
  3. L. Lacasa, B. Luque, F. Ballesteros, J. Luque and J. Nuno, From time series to complex networks: The visibility graph, Proceedings of the National Academy of Sciences 105(2008), no. 13, 4972---4975.