Visibility Graphs

What is a Graph?
Formally the defination of a graph is as follows:
A graph G is an ordered triple (V(G), E(G), t/!G) consisting of a nonempty set V( G) of vertices, a set E(G), disjoint from V(G), of edges, and an incidence function t/Ja that associates with each edge of G an unordered pair of (not necessarily distinct) vertices of G. If e is an edge and u and t' are vertices such that t/!G(e) - UV, then e is said to join u and v; the vertices Ii and 'v 'are called the ends of e.

This is just a more robust and mathematical way of defining the nodes/vertices of a graph and their corresponding edges

In simpler terms we can say that a graph is a mathematical way of visualizing networks or relations. A graph will always contain vertices connected by edges

An example of a graph can be found below

What is a Visibility Graph?
Formally we can define a visibilty graph such that:
Given a set S = {s1, s2,…, sn} of vertical line segments, s1, sj see each other if there is a horizontal line segment which intersects them, but does not intersect any other line segment between them. A visibility graph G of vertices {v1, v2,…, vn} is put into a one-to-one correspondence with S, such that si corresponds to v1, and edge {vi, vj} exists in G iff si, sj see each other
Putting it simply, Edges between nodes or vertices are only drawn if the nodes "see each other", this means if and only if a straight line can be drawn between two nodes without the edge instersecting other lines

An example of a vsisbility graph can be found below

What are the uses of visibility graphs?
A few real world applications of visibility graphs include:

1. Robot motion planning
   In the field of robotics, visiblity graphs helps to map nodes and find shortest paths among a set of obstacles in a plane
2. Signal processing and Pattern recognition
   • Used to extract rhythmic self-similarities from standard deviations series in audio signals for music genre classification
   • They can be adapted to analyze spatial patterns in scalar fields, which aids in image classification and texture recognition
3. Time series analysis
   Time series data can be taken and inputted into an algorithm which can covert this time series into a visibility graph which then is used to study the data in the time sereies

A Deeper Dive into Time series analysis

Intention behind the work
Visibility graph (VG) analysis translates sequential time-series data into a complex network. By treating data points as nodes and connecting them based on their relative "visibility" (acting as an unbroken line-of-sight over a landscape), the series' underlying deterministic dynamics, periodicity, and fractal properties can be analyzed using network topology.

in a paper published in 2008 [From time series to complex networks:The visibility graph] underlines the algorithm and methods of converting a time series into a graph

The paper outlines that a visibility graph has the following three properties,

• Undirected The edges between nodes have no direction, which is different from the sequential time series.

• Connected There is no isolated node in the network as the visibility exists between every pair of neighbor data points.

• Invariant under affine transformations The rescaling and translation of horizontal and vertical axes do not affect the visibility criterion and the structure of the network.

The data in the time series is sequential, and the property of the time series is mainly analyzed from the historical data. The visibility between data points in the time series can be expressed as the connection between nodes, and the properties in the series are also inherited by the network. In detail, periodic series, random series, and fractal series are mapped to regular network, random network, and scale-free network, respectively

Due to the strict mapping rule of HVG, HVG is a sub-network of VG when they are constructed by the same time series. In addition, the average degree of nodes in HVG is smaller than the average degree of nodes in VG, so the relationship between nodes is limited to the local structural property
In addition to the last two properties of VG, the horizontal visibility graph has three additional properties:

• Reversible and irreversible properties of the converting Information loss in the series caused by the binary adjacency matrix in unweighted networks can be avoided by using weighted networks to represent the time series.

• Directed and undirected properties of the converting Undirected networks are constructed by this algorithm, but directed networks can also be constructed by distinguishing the ingoing degree 𝑑in and outgoing degree 𝑑out.

• Geometric criteria difference HVG has “less visibility” than VG due to its strict geometric criteria, but it does not affect qualitative features of the network

Core Algorithm

There are two primary approches to convert a series into a graph

• Natural Visibility Graph (NVG): Two points ((t_i, x_i)) and ((t_j, x_j)) are connected by an edge if any intermediate data point ((t_k, x_k)) satisfies the geometrical line-of-sight criterion:

• Horizontal Visibility Graph (HVG): Two nodes are connected if their heights allow an unobstructed horizontal line of sight, meaning the criterion is (x_k \le \text{min}(x_i, x_j)) for all intermediate points. HVG calculations are computationally faster and structurally outerplanar

Methods of conversion using python

Fortunately for us there exists a python module that can take time series data and compute all the parameters for us and plot a visibility graph
For this i will be using the ts2vg python module and mathplotlib to produce all the graphs

An example of a natural VSG with input of the code (using a basic time series) and the image it produces can be seen below

Input:

Output:

Another Example of a horizontal VSG can be seen below:

Input:

Output:

A few more examples of vsisibility graphs generated by different data sets can be seen below

1. Sales data set
   input:

import matplotlib.pyplot as plt
import networkx as nx
import pandas as pd
import numpy as np
from ts2vg import NaturalVG

csv_file = "sales_data.csv"
column_name = "Sales"

df = pd.read_csv(r"C:\Users\Rishit Chib\Downloads\sales_data.csv")

time_series = df[column_name].values

g = NaturalVG()
g.build(time_series)

nxg = g.as_networkx()

pos = {i: (i, val) for i, val in enumerate(time_series)}

num_nodes = nxg.number_of_nodes()
num_edges = nxg.number_of_edges()
density = nx.density(nxg)
is_connected = nx.is_connected(nxg)

degrees = dict(nxg.degree())
degree_values = np.array(list(degrees.values()))
avg_degree = degree_values.mean()
max_degree = degree_values.max()
min_degree = degree_values.min()

degree_sequence = sorted(degree_values, reverse=True)

degree_centrality = nx.degree_centrality(nxg)
betweenness_centrality = nx.betweenness_centrality(nxg)
closeness_centrality = nx.closeness_centrality(nxg)
eigenvector_centrality = nx.eigenvector_centrality(nxg, max_iter=1000)

top_degree = sorted(degree_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
top_betweenness = sorted(betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
top_closeness = sorted(closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
top_eigenvector = sorted(eigenvector_centrality.items(), key=lambda x: x[1], reverse=True)[:5]

avg_clustering = nx.average_clustering(nxg)
transitivity = nx.transitivity(nxg)  

if is_connected:
    avg_shortest_path = nx.average_shortest_path_length(nxg)
    diameter = nx.diameter(nxg)
else:
    largest_cc = max(nx.connected_components(nxg), key=len)
    subgraph = nxg.subgraph(largest_cc)
    avg_shortest_path = nx.average_shortest_path_length(subgraph)
    diameter = nx.diameter(subgraph)

assortativity = nx.degree_assortativity_coefficient(nxg)

print("=" * 60)
print("VISIBILITY GRAPH — NETWORK ANALYSIS SUMMARY")
print("=" * 60)
print(f"Nodes: {num_nodes}")
print(f"Edges: {num_edges}")
print(f"Density: {density:.4f}")
print(f"Connected: {is_connected}")
print(f"Average degree: {avg_degree:.2f}")
print(f"Max degree: {max_degree} (node/time index: {max(degrees, key=degrees.get)})")
print(f"Min degree: {min_degree}")
print(f"Average clustering coefficient: {avg_clustering:.4f}")
print(f"Transitivity: {transitivity:.4f}")
print(f"Average shortest path length: {avg_shortest_path:.4f}")
print(f"Diameter: {diameter}")
print(f"Degree assortativity: {assortativity:.4f}")
print()
print("Top 5 nodes by degree centrality:")
for node, val in top_degree:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print()
print("Top 5 nodes by betweenness centrality:")
for node, val in top_betweenness:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print()
print("Top 5 nodes by closeness centrality:")
for node, val in top_closeness:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print()
print("Top 5 nodes by eigenvector centrality:")
for node, val in top_eigenvector:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print("=" * 60)

analysis_df = pd.DataFrame({
    "time_index": range(num_nodes),
    "value": time_series,
    "degree": [degrees[i] for i in range(num_nodes)],
    "degree_centrality": [degree_centrality[i] for i in range(num_nodes)],
    "betweenness_centrality": [betweenness_centrality[i] for i in range(num_nodes)],
    "closeness_centrality": [closeness_centrality[i] for i in range(num_nodes)],
    "eigenvector_centrality": [eigenvector_centrality[i] for i in range(num_nodes)],
    "clustering_coefficient": [nx.clustering(nxg)[i] for i in range(num_nodes)],
})


from matplotlib.gridspec import GridSpec

fig = plt.figure(figsize=(16, 20), constrained_layout=True)
gs = GridSpec(4, 1, figure=fig, height_ratios=[1, 2, 1, 1])

ax0 = fig.add_subplot(gs[0])
ax1 = fig.add_subplot(gs[1])
ax2 = fig.add_subplot(gs[2])
ax3 = fig.add_subplot(gs[3])

ax0.plot(time_series, color="blue", marker="o", markersize=3, linewidth=1, label="Time Series Data")
ax0.set_title("Original Time Series", fontsize=13, fontweight="bold")
ax0.set_ylabel("Values")
ax0.grid(True, linestyle="--", alpha=0.6)
ax0.legend(loc="upper right", fontsize=9)

ax1.set_title("Corresponding Visibility Graph Network", fontsize=13, fontweight="bold")
node_colors = [degree_centrality[n] for n in nxg.nodes()]
nodes_drawn = nx.draw_networkx_nodes(
    nxg, pos, ax=ax1,
    node_size=30,
    node_color=node_colors,
    cmap="viridis",
)
nx.draw_networkx_edges(
    nxg, pos, ax=ax1,
    edge_color="gray",
    width=0.6,
    alpha=0.3,
)
ax1.set_xlabel("Time Index / Node Index")
ax1.set_ylabel("Node Heights")
ax1.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)
ax1.grid(True, linestyle="--", alpha=0.4)

y_range = time_series.max() - time_series.min()
ax1.set_ylim(time_series.min() - 0.1 * y_range, time_series.max() + 0.1 * y_range)
cbar = fig.colorbar(nodes_drawn, ax=ax1, fraction=0.025, pad=0.01)
cbar.set_label("Degree Centrality", fontsize=9)

ax2.hist(degree_values, bins=30, color="steelblue", edgecolor="black", alpha=0.7)
ax2.set_title("Degree Distribution", fontsize=13, fontweight="bold")
ax2.set_xlabel("Degree")
ax2.set_ylabel("Frequency")
ax2.grid(True, linestyle="--", alpha=0.6)

ax3.plot(list(degree_centrality.keys()), list(degree_centrality.values()),
          color="darkorange", marker=".", markersize=3, linewidth=1)
ax3.set_title("Degree Centrality Over Time", fontsize=13, fontweight="bold")
ax3.set_xlabel("Time Index")
ax3.set_ylabel("Degree Centrality")
ax3.grid(True, linestyle="--", alpha=0.6)

plt.show()

Output:

2. Electricity Production
   input:

import matplotlib.pyplot as plt
import networkx as nx
import pandas as pd
import numpy as np
from ts2vg import NaturalVG

csv_file = "Electric_Production.csv"
column_name = "Value"

df = pd.read_csv(r"C:\Users\Rishit Chib\Downloads\Electricity Production\Electricity Production\Electric_Production.csv")

time_series = df[column_name].to_numpy(copy=True, dtype=np.float64)

g = NaturalVG()
g.build(time_series)

nxg = g.as_networkx()

pos = {i: (i, val) for i, val in enumerate(time_series)}

num_nodes = nxg.number_of_nodes()
num_edges = nxg.number_of_edges()
density = nx.density(nxg)
is_connected = nx.is_connected(nxg)

degrees = dict(nxg.degree())
degree_values = np.array(list(degrees.values()))
avg_degree = degree_values.mean()
max_degree = degree_values.max()
min_degree = degree_values.min()

degree_sequence = sorted(degree_values, reverse=True)

degree_centrality = nx.degree_centrality(nxg)
betweenness_centrality = nx.betweenness_centrality(nxg)
closeness_centrality = nx.closeness_centrality(nxg)
eigenvector_centrality = nx.eigenvector_centrality(nxg, max_iter=1000)

top_degree = sorted(degree_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
top_betweenness = sorted(betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
top_closeness = sorted(closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
top_eigenvector = sorted(eigenvector_centrality.items(), key=lambda x: x[1], reverse=True)[:5]

avg_clustering = nx.average_clustering(nxg)
transitivity = nx.transitivity(nxg)  

if is_connected:
    avg_shortest_path = nx.average_shortest_path_length(nxg)
    diameter = nx.diameter(nxg)
else:
    largest_cc = max(nx.connected_components(nxg), key=len)
    subgraph = nxg.subgraph(largest_cc)
    avg_shortest_path = nx.average_shortest_path_length(subgraph)
    diameter = nx.diameter(subgraph)

assortativity = nx.degree_assortativity_coefficient(nxg)

print("=" * 60)
print("VISIBILITY GRAPH — NETWORK ANALYSIS SUMMARY")
print("=" * 60)
print(f"Nodes: {num_nodes}")
print(f"Edges: {num_edges}")
print(f"Density: {density:.4f}")
print(f"Connected: {is_connected}")
print(f"Average degree: {avg_degree:.2f}")
print(f"Max degree: {max_degree} (node/time index: {max(degrees, key=degrees.get)})")
print(f"Min degree: {min_degree}")
print(f"Average clustering coefficient: {avg_clustering:.4f}")
print(f"Transitivity: {transitivity:.4f}")
print(f"Average shortest path length: {avg_shortest_path:.4f}")
print(f"Diameter: {diameter}")
print(f"Degree assortativity: {assortativity:.4f}")
print()
print("Top 5 nodes by degree centrality:")
for node, val in top_degree:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print()
print("Top 5 nodes by betweenness centrality:")
for node, val in top_betweenness:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print()
print("Top 5 nodes by closeness centrality:")
for node, val in top_closeness:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print()
print("Top 5 nodes by eigenvector centrality:")
for node, val in top_eigenvector:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print("=" * 60)

analysis_df = pd.DataFrame({
    "time_index": range(num_nodes),
    "value": time_series,
    "degree": [degrees[i] for i in range(num_nodes)],
    "degree_centrality": [degree_centrality[i] for i in range(num_nodes)],
    "betweenness_centrality": [betweenness_centrality[i] for i in range(num_nodes)],
    "closeness_centrality": [closeness_centrality[i] for i in range(num_nodes)],
    "eigenvector_centrality": [eigenvector_centrality[i] for i in range(num_nodes)],
    "clustering_coefficient": [nx.clustering(nxg)[i] for i in range(num_nodes)],
})


from matplotlib.gridspec import GridSpec

fig = plt.figure(figsize=(16, 20), constrained_layout=True)
gs = GridSpec(4, 1, figure=fig, height_ratios=[1, 2, 1, 1])

ax0 = fig.add_subplot(gs[0])
ax1 = fig.add_subplot(gs[1])
ax2 = fig.add_subplot(gs[2])
ax3 = fig.add_subplot(gs[3])

ax0.plot(time_series, color="blue", marker="o", markersize=3, linewidth=1, label="Time Series Data")
ax0.set_title("Original Time Series", fontsize=13, fontweight="bold")
ax0.set_ylabel("Values")
ax0.grid(True, linestyle="--", alpha=0.6)
ax0.legend(loc="upper right", fontsize=9)

ax1.set_title("Corresponding Visibility Graph Network", fontsize=13, fontweight="bold")
node_colors = [degree_centrality[n] for n in nxg.nodes()]
nodes_drawn = nx.draw_networkx_nodes(
    nxg, pos, ax=ax1,
    node_size=30,
    node_color=node_colors,
    cmap="viridis",
)
nx.draw_networkx_edges(
    nxg, pos, ax=ax1,
    edge_color="gray",
    width=0.6,
    alpha=0.3,
)
ax1.set_xlabel("Time Index / Node Index")
ax1.set_ylabel("Node Heights")
ax1.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)
ax1.grid(True, linestyle="--", alpha=0.4)

y_range = time_series.max() - time_series.min()
ax1.set_ylim(time_series.min() - 0.1 * y_range, time_series.max() + 0.1 * y_range)
cbar = fig.colorbar(nodes_drawn, ax=ax1, fraction=0.025, pad=0.01)
cbar.set_label("Degree Centrality", fontsize=9)

ax2.hist(degree_values, bins=30, color="steelblue", edgecolor="black", alpha=0.7)
ax2.set_title("Degree Distribution", fontsize=13, fontweight="bold")
ax2.set_xlabel("Degree")
ax2.set_ylabel("Frequency")
ax2.grid(True, linestyle="--", alpha=0.6)

ax3.plot(list(degree_centrality.keys()), list(degree_centrality.values()),
          color="darkorange", marker=".", markersize=3, linewidth=1)
ax3.set_title("Degree Centrality Over Time", fontsize=13, fontweight="bold")
ax3.set_xlabel("Time Index")
ax3.set_ylabel("Degree Centrality")
ax3.grid(True, linestyle="--", alpha=0.6)

plt.show()

Output:

3. Gold production over the last 10 years
   Input:

import matplotlib.pyplot as plt
import networkx as nx
import pandas as pd
import numpy as np
from ts2vg import NaturalVG

csv_file = "gold_historical_data.csv"
column_name = "Adj Close"

df = pd.read_csv(r"C:\Users\Rishit Chib\Downloads\Gold_price_last_10_years\Gold_price_last_10_years\gold_historical_data.csv")

time_series = df[column_name].to_numpy(copy=True, dtype=np.float64)

g = NaturalVG()
g.build(time_series)

nxg = g.as_networkx()

pos = {i: (i, val) for i, val in enumerate(time_series)}

num_nodes = nxg.number_of_nodes()
num_edges = nxg.number_of_edges()
density = nx.density(nxg)
is_connected = nx.is_connected(nxg)

degrees = dict(nxg.degree())
degree_values = np.array(list(degrees.values()))
avg_degree = degree_values.mean()
max_degree = degree_values.max()
min_degree = degree_values.min()

degree_sequence = sorted(degree_values, reverse=True)

degree_centrality = nx.degree_centrality(nxg)
betweenness_centrality = nx.betweenness_centrality(nxg)
closeness_centrality = nx.closeness_centrality(nxg)
eigenvector_centrality = nx.eigenvector_centrality(nxg, max_iter=1000)

top_degree = sorted(degree_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
top_betweenness = sorted(betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
top_closeness = sorted(closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
top_eigenvector = sorted(eigenvector_centrality.items(), key=lambda x: x[1], reverse=True)[:5]

avg_clustering = nx.average_clustering(nxg)
transitivity = nx.transitivity(nxg)  

if is_connected:
    avg_shortest_path = nx.average_shortest_path_length(nxg)
    diameter = nx.diameter(nxg)
else:
    largest_cc = max(nx.connected_components(nxg), key=len)
    subgraph = nxg.subgraph(largest_cc)
    avg_shortest_path = nx.average_shortest_path_length(subgraph)
    diameter = nx.diameter(subgraph)

assortativity = nx.degree_assortativity_coefficient(nxg)

print("=" * 60)
print("VISIBILITY GRAPH — NETWORK ANALYSIS SUMMARY")
print("=" * 60)
print(f"Nodes: {num_nodes}")
print(f"Edges: {num_edges}")
print(f"Density: {density:.4f}")
print(f"Connected: {is_connected}")
print(f"Average degree: {avg_degree:.2f}")
print(f"Max degree: {max_degree} (node/time index: {max(degrees, key=degrees.get)})")
print(f"Min degree: {min_degree}")
print(f"Average clustering coefficient: {avg_clustering:.4f}")
print(f"Transitivity: {transitivity:.4f}")
print(f"Average shortest path length: {avg_shortest_path:.4f}")
print(f"Diameter: {diameter}")
print(f"Degree assortativity: {assortativity:.4f}")
print()
print("Top 5 nodes by degree centrality:")
for node, val in top_degree:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print()
print("Top 5 nodes by betweenness centrality:")
for node, val in top_betweenness:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print()
print("Top 5 nodes by closeness centrality:")
for node, val in top_closeness:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print()
print("Top 5 nodes by eigenvector centrality:")
for node, val in top_eigenvector:
    print(f"  Time index {node} (value={time_series[node]:.2f}): {val:.4f}")
print("=" * 60)

analysis_df = pd.DataFrame({
    "time_index": range(num_nodes),
    "value": time_series,
    "degree": [degrees[i] for i in range(num_nodes)],
    "degree_centrality": [degree_centrality[i] for i in range(num_nodes)],
    "betweenness_centrality": [betweenness_centrality[i] for i in range(num_nodes)],
    "closeness_centrality": [closeness_centrality[i] for i in range(num_nodes)],
    "eigenvector_centrality": [eigenvector_centrality[i] for i in range(num_nodes)],
    "clustering_coefficient": [nx.clustering(nxg)[i] for i in range(num_nodes)],
})


from matplotlib.gridspec import GridSpec

fig = plt.figure(figsize=(16, 20), constrained_layout=True)
gs = GridSpec(4, 1, figure=fig, height_ratios=[1, 2, 1, 1])

ax0 = fig.add_subplot(gs[0])
ax1 = fig.add_subplot(gs[1])
ax2 = fig.add_subplot(gs[2])
ax3 = fig.add_subplot(gs[3])

ax0.plot(time_series, color="blue", marker="o", markersize=3, linewidth=1, label="Time Series Data")
ax0.set_title("Original Time Series", fontsize=13, fontweight="bold")
ax0.set_ylabel("Values")
ax0.grid(True, linestyle="--", alpha=0.6)
ax0.legend(loc="upper right", fontsize=9)

ax1.set_title("Corresponding Visibility Graph Network", fontsize=13, fontweight="bold")
node_colors = [degree_centrality[n] for n in nxg.nodes()]
nodes_drawn = nx.draw_networkx_nodes(
    nxg, pos, ax=ax1,
    node_size=30,
    node_color=node_colors,
    cmap="viridis",
)
nx.draw_networkx_edges(
    nxg, pos, ax=ax1,
    edge_color="gray",
    width=0.6,
    alpha=0.3,
)
ax1.set_xlabel("Time Index / Node Index")
ax1.set_ylabel("Node Heights")
ax1.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)
ax1.grid(True, linestyle="--", alpha=0.4)

y_range = time_series.max() - time_series.min()
ax1.set_ylim(time_series.min() - 0.1 * y_range, time_series.max() + 0.1 * y_range)
cbar = fig.colorbar(nodes_drawn, ax=ax1, fraction=0.025, pad=0.01)
cbar.set_label("Degree Centrality", fontsize=9)

ax2.hist(degree_values, bins=30, color="steelblue", edgecolor="black", alpha=0.7)
ax2.set_title("Degree Distribution", fontsize=13, fontweight="bold")
ax2.set_xlabel("Degree")
ax2.set_ylabel("Frequency")
ax2.grid(True, linestyle="--", alpha=0.6)

ax3.plot(list(degree_centrality.keys()), list(degree_centrality.values()),
          color="darkorange", marker=".", markersize=3, linewidth=1)
ax3.set_title("Degree Centrality Over Time", fontsize=13, fontweight="bold")
ax3.set_xlabel("Time Index")
ax3.set_ylabel("Degree Centrality")
ax3.grid(True, linestyle="--", alpha=0.6)

plt.show()

Output:

Method of Analysis

Represent local States with visibility graphs

Let a window with size s slide along a time series, {y1, y2, …, yN}. The covered segments read as follows;

We propose the visibility graph as the tool to extract structural information embedded in the segments. The resulting visibility graphs can capture the key structural characteristics of the corresponding segments, and consequently are taken as the description of the local sates in different time durations.

Now we map the segment Yk to a visibility graph. Each data value is considered to be a node. Two nodes are connected if they can see each other, namely, a straight visibility line exists between them. Formally, two arbitrary data values ya and yb are visible to each other if each point yc between them satisfies the criterion;

The constructed visibility graph can be represented with an adjacency matrix, gk, whose element gk(a − k + 1, b − k + 1) equals 1(0) if ya and yb are visible (invisible). Here, the identification numbers of the nodes corresponding to ya and yb are assigned to be a − k + 1 and b − k + 1, to be sure they are in the interval of [1, s]. This results into an s by s matrix for the kth segment. Covering the whole series, a set of adjacency matrices, G = {g1, g2, …, gN−s+1} is obtained.

State transfer network

Here, we define a state transfer network to describe transfer probabilities between distinguishable local states. In the time series, if a state at time b occurs immediately after another state at time a, then we construct a directional link from ga to gb. Accordingly, the link means a transfer from one state to the other state. By using this procedure a state chain with directional links is attained, which reads;

Here we find out all the distinguishable states. Let us scan through G comparing each state with the others. If any two states are identical (their adjacency matrices are the same) one replaces the later one with the the reference state. For instance, if g1 = g4, the state g4 is replaced with g1. This process is done iteratively for all states. The survival states are unique states, which are defined to be nodes. We reckon the number of links between each pair of the nodes (survival states), which is the weight of the link between them. By this procedure, the time series is mapped further to a network of distinguishable states (visibility graphs), called state transfer network, with edge direction being the transfer direction and edge weight being the transfer times.

Properties of the state transfer network

Herein, we are interested in several properties of the state transfer network, including,

Occurring frequency. The occurring frequency of a node in the duration of recording is herein called degree. A hub node means its occurrence number is significantly larger compared with that of the other nodes. Though hubs are clearly observed, the behavior may be common even in null models hence holding less non-trivial characteristics. If the occurring frequency of a node in the original time series is significantly larger than that in a shuffled time series, the node is called motif, which can be used as a global representative of the time series.

Transmission probability. Strong correlation usually exists in time series, which means occurrence of a state depends strongly on the previous states rather than its occurring stochastically. We expect there exist significant large link weights between some hubs or motifs, which can be greatly helpful in short-term prediction, i.e, based upon the state at present time one predicts what will happen at the next time step.

Long-term persistence. A large amount of research works have reported the self-similar structures of time series in diverse research fields . This kind of fractal behavior makes it possible for us to predict behaviors of complex systems in macroscopic time scales. We will show that the fractal structure can be displayed by the occurring positions of some motifs on time series.\

Why use visibility graph to measure local states?

It should be pointed out that using visibility-graph as being state representative is not a trivial selection. Obviously, rather than the visibility-graph we have alternative methods to extract the state information. For example, one can simply compare the values of successive elements in a segment and record the increasing, keeping unchanged, and decreasing with +1, 0, and −1, respectively. By this way each segment is symbolized to a series of discrete values.

The advantages of the visibility-graph include,
(1) It can capture precise information of a state. Comparing with the symbolizing procedure, the visibility-graph can extract detailed information of sub-segments at different scales in each segment, at the same time keeps reasonably simple. On the contrary, the symbolizing procedure can only reserve the immediate increase/decrease information
(2) It can be used in analyzing non-stationary time series. A stochastic process, e.g., the fractional Brownian motion, is generally non-stationary, which makes the probability distribution function of the phase vector (series segment) time-dependent .
Accordingly, if we use an improper solution to represent states (e.g., the original phase vector in multi-dimensional phase space), the estimations of transfer probabilities (the links) between the states may change with time. Fortunately, this non-stationary effect is eliminated effectively by using visibility graph. Because a segment is very short, its trend can be mainly described with a straight line. Accordingly, visibility graph for the corresponding de-trended segment is identical with that for the original segment, called invariance under affine transformations

Refrences

• https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0143015#sec002
• https://www.sciencedirect.com/science/article/pii/0012365X87901907
• https://pmc.ncbi.nlm.nih.gov/articles/PMC9628348/#Sec2
• https://www.emergentmind.com/topics/visibility-graph-analysis-vga
• https://www.semanticscholar.org/reader/c06412a06f3c4c1bacfed5ec0165d866ea10048a
• https://arxiv.org/pdf/0810.0920
• https://youtu.be/bA1I4Upzxgc?si=u46s6KuQjmD1buga
• https://github.com/CarlosBergillos/ts2vg
• https://youtu.be/M1zQXfKIiJ4?si=m8tHGK1dsoeW2HE0
• http://www.youtube.com/@DiestelGraphTheory