Message Boards Message Boards

Visibility Graphs: Dualism of Time Series and Networks

Posted 12 years ago
From a recent Complex System article [1] I found out about interesting mapping between Graphs and Time Series that currently gaining more and more attention. The main idea is being able to apply time series analysis methods to networks and vice versa. There is a hope of gaining new insights into familiar objects by approaching from different side. I thought it would be interesting to implement a toy example in Mathematica. I consider the simplest Horizontal Visibility Graph (HVG) algorithm which can be simply explained with the figure below.



   1. Every event in time series correspond to a vertex in the graph
   2. Two events are connected by edge in the graph if all events between them in time series a smaller then them in magnitude

There are other more complex mapping algorithms (see references at the end), but we’ll stick with this simple one. Let’s consider three different types of time series to see what kind of networks they can produce:
   1. Deterministic system: Cellular Automaton rule 54 with complex type 4 behavior
   2. Stochastic system: Geometric Brownian Motion random process
   3. Empirical system: Financial data of GE stock price
dataS = {FromDigits[#, 2] & /@
   CellularAutomaton[54, RandomInteger[1, 200], 49],
   RandomFunction[GeometricBrownianMotionProcess[0, .1, 2], {1, 50, 1}][[2, 1, 1]],
   FinancialData["GE", "Jan. 1, 2000"][[All, 2]][[1 ;; 50]]};

ListPlot[#, Filling -> Bottom, AspectRatio -> 1/10, FillingStyle -> Thick, PlotStyle -> PointSize[.008],
Axes -> {True, False}, GridLines -> {None, Automatic}, Ticks -> {Range[81], None}, ImageSize -> 800] & /@ dataS


Define the mapping function
fied[m_, n_, data_] := If[(Min[#[[m]], #[[n]]] > Max[#[[m + 1 ;; n - 1]]]) &@data, m \[UndirectedEdge] n]
Compute the edges of the graph
edgesS = Cases[Flatten[Table[fied[m, n, #], {m, Length[#]}, {n, m + 1, Length[#]}]], _ \[UndirectedEdge] _] & /@ dataS;
Build the graph and highlight vertexes based on vertex degree and the shortest path between initial and final events.
gS = Graph[#, GraphLayout -> "LayeredDigraphEmbedding"] & /@ edgesS;
gSH = HighlightGraph[#, VertexList[#],
VertexSize -> Thread[VertexList[#] -> Rescale[VertexDegree[#]]],
ImageSize -> {Automatic, 500}, VertexLabels -> "Name"] & /@ gS;

HighlightGraph[#, PathGraph[FindShortestPath[#, 1, 50]], GraphHighlightStyle -> "Thick"] & /@ gSH

I used LayeredDigraphEmbedding which kind of preserves chronological order of the series laying out networks nicely. I hope you enjoyed this little mapping and may apply a similar method for your own research. There are inverse mappings too - see the reference. Please feel free to share your ideas on the subject or possible algorithm optimization.

   [1] Discriminating Chaotic Visibility Graph Eigenvalues, Vincenzo Fioriti et al, Complex Systems, Vol 21, No 3, p193
   [2] From time series to complex networks: The visibility graph
   [3] Duality between Time Series and Networks
   [4] Some related arXiv.org papers
POSTED BY: Vitaliy Kaurov
4 Replies

Dear Vitaliy,

I hope you are doing well!

I'm always a follower of your posts. I found an interesting paper related to this post. I am sure that it is interesting for you. Please see the enclosed file. Is it possible to study community detection for a sample time series like figure 1 using Mathematica?

I appreciate your time. Regards,

Attachments:
POSTED BY: M.A. Ghorbani
This is great!
Is the shortest path an upper envolope?
If yes, could you suggest an efficient way to plot it?
Could this be realted to the orher topic in duscussion in the wolfram community: peak detecting? I guess, a peak would be related with a node with high connectivity

Best regrads
Jesus
 
Fascinating. Thanks for sharing.
POSTED BY: Manuel Molano
This idea partially became a Demonstration: Horizontal Visibility Graphs for Elementary Cellular Automata




A time series can be formed from an evolution of a finite elementary cellular automaton (ECA). This can be done in a few different ways. We can consider every step of an ECA evolution to be a binary number and calculate its decimal form by counting digits from left to right or in reverse. We also could just sum the digits. These operations are reflected correspondingly in the control buttons "left," "right," and "sum."

The Demonstration constructs the horizontal visibility graph (HGV) for an ECA time series. An HVG maps a time series to a graph. Each event in the time series corresponds to a vertex in the graph. Two vertices are connected by an edge if the corresponding events in the time series are larger than all the events between them.

The goal of mapping time series to graphs is to apply powerful graph-theoretic methods to time series analysis. To illustrate this, let us consider a toy problem. Vertical posts of various heights are arranged along a straight line, and each can emit a horizontal signal from any point along its height. If a signal needs to be communicated from the first to the last post, what is the minimum set of posts necessary? While the posts are considered as a time series, the problem is solved as a graph-theoretic shortest-path algorithm. The solution is highlighted in yellow.
POSTED BY: Vitaliy Kaurov
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract