carlosbergillos / ts2vg

Time series to visibility graphs.

ts2vg: Time series to visibility graphs

The Python ts2vg package provides high-performance algorithm implementations to build visibility graphs from time series data, as first introduced by Lucas Lacasa et al. in 2008 [1].

The visibility graphs and some of their properties (e.g. degree distributions) are computed quickly and efficiently even for time series with millions of observations. An efficient divide-and-conquer algorithm is used to compute the graphs whenever possible [3].

Installation

The latest released ts2vg version is available at the Python Package Index (PyPI) and can be easily installed by running:

pip install ts2vg

For other advanced uses, to build ts2vg from source Cython is required.

Supported graph types

Main graph types

• Natural Visibility Graphs (NVG) [1] (ts2vg.NaturalVG)
• Horizontal Visibility Graphs (HVG) [2] (ts2vg.HorizontalVG)

Available variations

Additionally, the following variations of the previous main graph types are available:

• Weighted Visibility Graphs (via the weighted parameter)
• Directed Visibility Graphs (via the directed parameter)
• Parametric Visibility Graphs [5] (via the min_weight and max_weight parameters)
• Limited Penetrable Visibility Graphs (LPVG) [4] [6] (via the penetrable_limit parameter)

Note that multiple graph variations can be combined and used at the same time.

Documentation

Usage and reference documentation for ts2vg can be found at carlosbergillos.github.io/ts2vg.

Basic usage

To build a visibility graph from a time series do:

from ts2vg import NaturalVG

ts = [1.0, 0.5, 0.3, 0.7, 1.0, 0.5, 0.3, 0.8]

vg = NaturalVG()
vg.build(ts)

edges = vg.edges

The time series passed (ts) can be any one-dimensional iterable, such as a list or a numpy 1D array.

By default, the input observations are assumed to be equally spaced in time. Alternatively, a second 1D iterable (xs) can be provided for unevenly spaced time series.

Horizontal visibility graphs can be obtained in a very similar way:

from ts2vg import HorizontalVG

ts = [1.0, 0.5, 0.3, 0.7, 1.0, 0.5, 0.3, 0.8]

vg = HorizontalVG()
vg.build(ts)

edges = vg.edges

If we are only interested in the degree distribution of the visibility graph we can pass only_degrees=True to the build method. This will be more efficient in time and memory than storing the whole graph.

vg = NaturalVG()
vg.build(ts, only_degrees=True)

ks, ps = vg.degree_distribution

Directed graphs can be obtained by using the directed parameter and weighted graphs can be obtained by using the weighted parameter:

vg1 = NaturalVG(directed="left_to_right")
vg1.build(ts)

vg2 = NaturalVG(weighted="distance")
vg2.build(ts)

vg3 = NaturalVG(directed="left_to_right", weighted="distance")
vg3.build(ts)

vg4 = HorizontalVG(directed="left_to_right", weighted="h_distance")
vg4.build(ts)

For more information and options see: Examples and API Reference.

Interoperability with other libraries

The graphs obtained can be easily converted to graph objects from other common Python graph libraries such as igraph, NetworkX and SNAP for further analysis.

The following methods are provided:

• as_igraph()
• as_networkx()
• as_snap()

For example:

vg = NaturalVG()
vg.build(ts)

g = vg.as_networkx()

Command line interface

ts2vg can also be used as a command line program directly from the console:

ts2vg ./timeseries.txt -o out.edg

For more help and a list of options run:

ts2vg --help

Contributing

ts2vg can be found on GitHub. Pull requests and issue reports are welcome.

License

ts2vg is licensed under the terms of the MIT License.

References

[1]	(1, 2) Lucas Lacasa et al., "From time series to complex networks: The visibility graph", 2008.

[2]	Lucas Lacasa et al., "Horizontal visibility graphs: exact results for random time series", 2009.

[3]	Xin Lan et al., "Fast transformation from time series to visibility graphs", 2015.

[4]	T.T Zhou et al., "Limited penetrable visibility graph for establishing complex network from time series", 2012.

[5]	I.V. Bezsudnov et al., "From the time series to the complex networks: The parametric natural visibility graph", 2014

[6]	Qi Xuan et al., "CLPVG: Circular limited penetrable visibility graph as a new network model for time series", 2021

ts2vg's Issues

help getting started

I am playing around with ts2vg and I am having a hard time with the plotting using igraph.
I try to compute the natural vg for a short time series, but when trying to plot it I get this error:

Traceback (most recent call last):
  File "\anaconda3\envs\DK_01\lib\site-packages\IPython\core\interactiveshell.py", line 3398, in run_code
    exec(code_obj, self.user_global_ns, self.user_ns)
  File "<ipython-input-1-9a1fdcf342e8>", line 1, in <cell line: 1>
    ig.plot(nx_g, target='graph.pdf')
  File "\anaconda3\envs\DK_01\lib\site-packages\igraph\drawing\__init__.py", line 512, in plot
    result.save()
  File "\anaconda3\envs\DK_01\lib\site-packages\igraph\drawing\__init__.py", line 309, in save
    self._ctx.show_page()
igraph.drawing.cairo.MemoryError: out of memory

The file created is corrupted.

Here is my code:

import numpy as np
from ts2vg import NaturalVG
import igraph as ig

import matplotlib.pyplot as plt

# time domain
t = np.linspace(1, 40)
dt = np.diff(t)

# build series
x1 = np.sin(2*np.pi/10*t)
x2 = np.sin(2*np.pi/15*t)

y = x1 + x2

plt.plot(t, y, '.-')
plt.show()

# build HVG
g = NaturalVG()
g.build(y)

nx_g = g.as_igraph()

# plotting
ig.plot(nx_g, target='graph.pdf')

I am using ts2vg 1.0.0, igraph 0.9.11, and pycairo 1.21.0

Error while installing ts2vg due to Wheel

hello I get this error when trying to install ts2vg

Installing ts2vg...
Resolving ts2vg...
Installing...
⠧ Installing ts2vg...[31m[1mError: [0m An error occurred while installing [32mts2vg[0m!
Error text: Collecting ts2vg
Using cached ts2vg-1.2.1.tar.gz (643 kB)
Installing build dependencies: started
Installing build dependencies: finished with status 'done'
Getting requirements to build wheel: started
Getting requirements to build wheel: finished with status 'error'

[36m error: subprocess-exited-with-error

× Getting requirements to build wheel did not run successfully.
│ exit code: 1
╰─> [26 lines of output]
Traceback (most recent call last):
File
"/opt/homebrew/lib/python3.11/site-packages/pipenv/patched/pip/_vendor/pyproject_hooks/_in_process/_in_process
.py", line 353, in
main()
File
"/opt/homebrew/lib/python3.11/site-packages/pipenv/patched/pip/_vendor/pyproject_hooks/_in_process/_in_process
.py", line 335, in main
json_out['return_val'] = hook(**hook_input['kwargs'])
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File
"/opt/homebrew/lib/python3.11/site-packages/pipenv/patched/pip/_vendor/pyproject_hooks/_in_process/_in_process
.py", line 118, in get_requires_for_build_wheel
return hook(config_settings)
^^^^^^^^^^^^^^^^^^^^^
File
"/private/var/folders/4c/zgw8q2mx7plgt4ndx3mdg5zw0000gn/T/pip-build-env-bag7tkml/overlay/lib/python3.11/site-p
ackages/setuptools/build_meta.py", line 338, in get_requires_for_build_wheel
return self._get_build_requires(config_settings, requirements=['wheel'])
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File
"/private/var/folders/4c/zgw8q2mx7plgt4ndx3mdg5zw0000gn/T/pip-build-env-bag7tkml/overlay/lib/python3.11/site-p
ackages/setuptools/build_meta.py", line 320, in _get_build_requires
self.run_setup()
File
"/private/var/folders/4c/zgw8q2mx7plgt4ndx3mdg5zw0000gn/T/pip-build-env-bag7tkml/overlay/lib/python3.11/site-p
ackages/setuptools/build_meta.py", line 335, in run_setup
exec(code, locals())
File "", line 49, in
File "", line 43, in main
File
"/private/var/folders/4c/zgw8q2mx7plgt4ndx3mdg5zw0000gn/T/pip-build-env-bag7tkml/overlay/lib/python3.11/site-p
ackages/Cython/Build/Dependencies.py", line 973, in cythonize
module_list, module_metadata = create_extension_list(
^^^^^^^^^^^^^^^^^^^^^^
File
"/private/var/folders/4c/zgw8q2mx7plgt4ndx3mdg5zw0000gn/T/pip-build-env-bag7tkml/overlay/lib/python3.11/site-p
ackages/Cython/Build/Dependencies.py", line 816, in create_extension_list
for file in nonempty(sorted(extended_iglob(filepattern)), "'%s' doesn't match any files" %
filepattern):
File
"/private/var/folders/4c/zgw8q2mx7plgt4ndx3mdg5zw0000gn/T/pip-build-env-bag7tkml/overlay/lib/python3.11/site-p
ackages/Cython/Build/Dependencies.py", line 114, in nonempty
raise ValueError(error_msg)
ValueError: 'ts2vg/utils/pairqueue.pyx' doesn't match any files

note: This error originates from a subprocess, and is likely not a problem with pip.
error: subprocess-exited-with-error

× Getting requirements to build wheel did not run successfully.
│ exit code: 1
╰─> See above for output.

note: This error originates from a subprocess, and is likely not a problem with pip.
[0m
✘ Installation Failed

FR: CLPVG

Feature Request to add LPVG and CLPVG
Ref: https://aip.scitation.org/doi/10.1063/5.0048243

How to construct a direct visibility graph

Hi!

I want to apply this method to construct a direct visibility graph. How can I do this?

Thanks!

Problem running example code in Jupyter; Install of ts2vg via %pip or %conda fails with same error

Hello Carlos,

Kindly, I am trying to run the example in a freshly installed Anaconda setup on a Mac M1.

I have created a new Jupyter Notebook, poasted the code but I keep getting this error:

%pip install ts2vg
from ts2vg import NaturalVG
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
ccccccccc
# 1. Generate random time series (Brownian motion)
rng = np.random.default_rng(110)
ts = rng.standard_normal(size=200)
ts = np.cumsum(ts)

# 2. Build visibility graph
g = NaturalVG(directed=None).build(ts)
nxg = g.as_networkx()

# 3. Make plots
fig, [ax0, ax1, ax2] = plt.subplots(ncols=3, figsize=(12, 3.5))

ax0.plot(ts)
ax0.set_title("Time Series")

graph_plot_options = {
    "with_labels": False,
    "node_size": 2,
    "node_color": [(0, 0, 0, 1)],
    "edge_color": [(0, 0, 0, 0.15)],
}

nx.draw_networkx(nxg, ax=ax1, pos=g.node_positions(), **graph_plot_options)
ax1.tick_params(bottom=True, labelbottom=True)
ax1.plot(ts)
ax1.set_title("Visibility Graph")

nx.draw_networkx(nxg, ax=ax2, pos=nx.kamada_kawai_layout(nxg), **graph_plot_options)
ax2.set_title("Visibility Graph")

Collecting ts2vg
  Using cached ts2vg-1.2.2.tar.gz (618 kB)
  Installing build dependencies ... done
  Getting requirements to build wheel ... error
  error: subprocess-exited-with-error
  
  × Getting requirements to build wheel did not run successfully.
  │ exit code: 1
  ╰─> [22 lines of output]
      Traceback (most recent call last):
        File "/Users/lwadmin/anaconda3/lib/python3.10/site-packages/pip/_vendor/pep517/in_process/_in_process.py", line 351, in <module>
          main()
        File "/Users/lwadmin/anaconda3/lib/python3.10/site-packages/pip/_vendor/pep517/in_process/_in_process.py", line 333, in main
          json_out['return_val'] = hook(**hook_input['kwargs'])
        File "/Users/lwadmin/anaconda3/lib/python3.10/site-packages/pip/_vendor/pep517/in_process/_in_process.py", line 118, in get_requires_for_build_wheel
          return hook(config_settings)
        File "/private/var/folders/9y/0tf_ch392nd_z9n63ynbj93m0000gn/T/pip-build-env-jlhi4th5/overlay/lib/python3.10/site-packages/setuptools/build_meta.py", line 341, in get_requires_for_build_wheel
          return self._get_build_requires(config_settings, requirements=['wheel'])
        File "/private/var/folders/9y/0tf_ch392nd_z9n63ynbj93m0000gn/T/pip-build-env-jlhi4th5/overlay/lib/python3.10/site-packages/setuptools/build_meta.py", line 323, in _get_build_requires
          self.run_setup()
        File "/private/var/folders/9y/0tf_ch392nd_z9n63ynbj93m0000gn/T/pip-build-env-jlhi4th5/overlay/lib/python3.10/site-packages/setuptools/build_meta.py", line 338, in run_setup
          exec(code, locals())
        File "<string>", line 46, in <module>
        File "<string>", line 40, in main
        File "/private/var/folders/9y/0tf_ch392nd_z9n63ynbj93m0000gn/T/pip-build-env-jlhi4th5/overlay/lib/python3.10/site-packages/Cython/Build/Dependencies.py", line 973, in cythonize
          module_list, module_metadata = create_extension_list(
        File "/private/var/folders/9y/0tf_ch392nd_z9n63ynbj93m0000gn/T/pip-build-env-jlhi4th5/overlay/lib/python3.10/site-packages/Cython/Build/Dependencies.py", line 816, in create_extension_list
          for file in nonempty(sorted(extended_iglob(filepattern)), "'%s' doesn't match any files" % filepattern):
        File "/private/var/folders/9y/0tf_ch392nd_z9n63ynbj93m0000gn/T/pip-build-env-jlhi4th5/overlay/lib/python3.10/site-packages/Cython/Build/Dependencies.py", line 114, in nonempty
          raise ValueError(error_msg)
      ValueError: 'ts2vg/graph/_base.pyx' doesn't match any files
      [end of output]
  
  note: This error originates from a subprocess, and is likely not a problem with pip.
error: subprocess-exited-with-error

× Getting requirements to build wheel did not run successfully.
│ exit code: 1
╰─> See above for output.

note: This error originates from a subprocess, and is likely not a problem with pip.
Note: you may need to restart the kernel to use updated packages.
---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 2
      1 get_ipython().run_line_magic('pip', 'install ts2vg')
----> 2 from ts2vg import NaturalVG
      3 import networkx as nx
      4 import numpy as np

ModuleNotFoundError: No module named 'ts2vg'

Horizontal Visibility Graph

Hi,

is there a possibility to add the horizontal visibility graph as well?

error while importing "from ts2vg import NaturalVG"

I also tried to downgrade numpy library

---

ValueError Traceback (most recent call last)
Input In [2], in <cell line: 1>()
----> 1 from ts2vg import NaturalVG

File ~/.local/lib/python3.9/site-packages/ts2vg/init.py:2, in
1 from ts2vg._version import version
----> 2 from ts2vg.graph.natural import NaturalVG
3 from ts2vg.graph.horizontal import HorizontalVG
5 all = [
6 'NaturalVG',
7 'HorizontalVG',
8 ]

File ~/.local/lib/python3.9/site-packages/ts2vg/graph/natural.py:3, in
1 from typing import Optional
----> 3 from ts2vg.graph._natural import _compute_graph as _compute_graph_dc
4 from ts2vg.graph._natural_penetrable import _compute_graph as _compute_graph_pn
5 from ts2vg.graph.base import VG

File ts2vg/graph/_natural.pyx:1, in init ts2vg.graph._natural()

ValueError: numpy.ufunc size changed, may indicate binary incompatibility. Expected 232 from C header, got 216 from PyObject

Plot visibility graph using ts2vg

Hi, I want show the specific graph structure in a figure. Can ts2vg plot visibility graph? How to plot a figure just like this:

Do you have a plan to add this function?

Problems with examples

The example in the library is to input a piece of series data, how do I add time series data? Are there any time limits?

Disaster

After 4 months of solid operation, the sample example completely fell apart. The time series is displayed ok. Everything else is also in ruins. Not only are there no axis descriptions, but there are absolutely no usable graphs. I am greatly disappointed. Josef

Installation fails for python 3.11 environment

I am trying to install using pip install ts2vg within an anaconda environment and the install fails when trying to build the wheel, output:

Collecting ts2vg
  Using cached ts2vg-1.1.1.tar.gz (392 kB)
  Installing build dependencies ... done
  Getting requirements to build wheel ... error
  error: subprocess-exited-with-error

  × Getting requirements to build wheel did not run successfully.
  │ exit code: 1
  ╰─> [26 lines of output]
      Traceback (most recent call last):
        File "C:\Users\jruby\Anaconda3\envs\ts_graph\Lib\site-packages\pip\_vendor\pep517\in_process\_in_process.py", line 363, in <module>
          main()
        File "C:\Users\jruby\Anaconda3\envs\ts_graph\Lib\site-packages\pip\_vendor\pep517\in_process\_in_process.py", line 345, in main
          json_out['return_val'] = hook(**hook_input['kwargs'])
                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        File "C:\Users\jruby\Anaconda3\envs\ts_graph\Lib\site-packages\pip\_vendor\pep517\in_process\_in_process.py", line 130, in get_requires_for_build_wheel
          return hook(config_settings)
                 ^^^^^^^^^^^^^^^^^^^^^
        File "C:\Users\jruby\AppData\Local\Temp\pip-build-env-y5h9bj_v\overlay\Lib\site-packages\setuptools\build_meta.py", line 338, in get_requires_for_build_wheel
          return self._get_build_requires(config_settings, requirements=['wheel'])
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        File "C:\Users\jruby\AppData\Local\Temp\pip-build-env-y5h9bj_v\overlay\Lib\site-packages\setuptools\build_meta.py", line 320, in _get_build_requires
          self.run_setup()
        File "C:\Users\jruby\AppData\Local\Temp\pip-build-env-y5h9bj_v\overlay\Lib\site-packages\setuptools\build_meta.py", line 335, in run_setup
          exec(code, locals())
        File "<string>", line 36, in <module>
        File "<string>", line 31, in main
        File "C:\Users\jruby\AppData\Local\Temp\pip-build-env-y5h9bj_v\overlay\Lib\site-packages\Cython\Build\Dependencies.py", line 970, in cythonize
          module_list, module_metadata = create_extension_list(
                                         ^^^^^^^^^^^^^^^^^^^^^^
        File "C:\Users\jruby\AppData\Local\Temp\pip-build-env-y5h9bj_v\overlay\Lib\site-packages\Cython\Build\Dependencies.py", line 816, in create_extension_list
          for file in nonempty(sorted(extended_iglob(filepattern)), "'%s' doesn't match any files" % filepattern):
        File "C:\Users\jruby\AppData\Local\Temp\pip-build-env-y5h9bj_v\overlay\Lib\site-packages\Cython\Build\Dependencies.py", line 114, in nonempty
          raise ValueError(error_msg)
      ValueError: 'ts2vg/utils/pairqueue.pyx' doesn't match any files
      [end of output]

  note: This error originates from a subprocess, and is likely not a problem with pip.
error: subprocess-exited-with-error

× Getting requirements to build wheel did not run successfully.
│ exit code: 1
╰─> See above for output.

note: This error originates from a subprocess, and is likely not a problem with pip.

I have been able to reproduce this issue on both a windows 10 machine and an Ubuntu VM both with fresh environments. I have successfully installed in python 3.10 envs.