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 well stick with this simple one. Lets 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
