The availability of a large amount of Automatic Identification System (AIS) data has fostered many studies on maritime vessel trafic during recent years, often representing vessels and ports relationships as graphs. Although the continuous research efort, only a few works explicitly study the evolution of such graphs and often consider coarse-grained time intervals. In this context, our ultimate goal is to fill this gap by providing a systematic study in the graph evolution by considering voyages over time. By mining the arrivals and departures of vessels from ports, we build a graph consisting of vessel voyages between ports. We then provide a study on topological features calculated from such graphs with a strong focus on their temporal evolution. Finally, we discuss the main limitations of our approach and the future perspectives that will spawn from this work.
Maritime transportation represents 90% of international trade
volume and plays a paramount role in today’s economy, in terms
of cargo shipping, passenger transportation, leisure navigation,
and fishing operation[
This allows the study of the interplay of all the components in the complex maritime network, and it is even more important for understanding the evolution over time of that interplay.
A central concept for the analytical study of vessel routes is
the Global Shipping Network (GSN), in which nodes are ports
and edges are the routes between ports of cargo ships. Figure 1
illustrates the GSN resulting from the vessels’ routes of 2017 in
the American coast using the MarineCadastre.gov dataset [
Since the automatic identification system (AIS) for vessels was
made mandatory in 2004 [
The main goal of our analysis is to provide a systematic study of the evolution aspect regarding maritime vessel routes, with the purpose of identifying recurrent patterns in their evolution. The analysis is based on publicly available data and with a defined and well-documented data model. This aspect is fundamental for the reproducibility of our analysis and its expansion and updating of results when new data arrives. Also, it considers the two necessary dimensions of time and layers (i.e., the evolution of the network can be observed for multiple types of vessels, such as cargo and passengers).
Such an ambitious objective has some inherent challenges that must be tackled. First, the analysis of AIS datasets typically presents a Big Data challenge: the datasets are usually vast, and data can arrive at a high rate. For example, ExactEarth alone claims to consistently track 165,000 vessels and compiling over 7,000,000 AIS messages daily1, but data still need to be processed in a reasonable time.
Second, the purpose of any network analysis is to abstract the complexity of a system in order to extract meaningful information that is not directly available when the individual components are examined separately. Therefore, the definition of a network that encompasses time information is a complex task. Suitable approaches need to be carefully selected to study the evolving network.
The contributions of this work can be outlined as the following: • We propose an approach that uses AIS data to extract connections between ports derived from the vessels’ movements. From these connections (or voyages), we build graphs in which the vertices correspond to the ports, whereas the edges or links correspond to the vessel voyage between two diferent ports. In addition, each edge has a semantic defined by the vessels’ type. • We study several topological properties of the temporal graphs generated from vessels’ movements and how these features evolve over time. Specifically, we investigate features relative to graphs dimension, ability to form clusters, and geographical spatiality. • We design and run an extensive analysis using a real dataset with AIS Data collected from vessels navigating in the U.S. coastal area. In our experiments, we investigate the aspect of stationarity of the time series of the topological properties of the graph and discuss the obtained insights.
The rest of the paper is organized as follows. Section 2 discusses related works. Section 3 introduces some concepts used through the paper. In Section 4, we describe our approach for deriving time-series of topological properties from graphs based on vessels’ visits to ports. We perform some analysis in Section 5 and draw conclusions envisioning future works in Section 6. 2
The work done in [
The work of [
A study of topological changes in the maritime trade network
is shown in [
In [
The work of [
Following a similar idea of building GSNs, but with focus on
anomaly detection, the work of [
Diferently from [
Vessels report their location through AIS messages while
navigating. A vessel may send AIS messages with a frequency that varies
from a few seconds to a few minutes, depending on the type of
message. When they are at the underway, they may send AIS
messages every 2 to 10 seconds, while when they are at anchor,
this time window can increase to every 3 minutes [
Graphs have some properties useful to unravel interesting
information about the dynamism between two and more entities. In
particular, in the context of a voyages graph, the topological
properties of the graph can help us identify relevant characteristics
within a network that would not have meaningful information if
the individual entities were examined separately [
Definition 3.1. (AIS Message): An AIS Message me is a tuple (x, y, t, c) that represents the GPS coordinate (x, y) at a time stamp t assigned to a vessel e of type c. We define M as the set of all AIS messages.
Definition 3.2. (Port): A Sea Port p is represented as a tuple (id, x, y), where x and y are the latitude and longitude coordinates of its geographical center, and id is the code that identifies the port. We also define the spatial function α (p, r ) that defines a circular area of radius r centered on the coordinates of port p.
Definition 3.3. (Visit): Given a radius r , we formally define a visit v = (p, me , t ) of the vessel e to a port p when it exists at least one me ∈ M at time t whose coordinates x and y are in the area defined by α (p, r ).
Definition 3.4. (Voyage): A voyage vj = (v1, v2) is a pair of visits, such that v1(p) , v2(p) and v1(e) = v2(e) and v1(t ) < v2(t ) and they are consecutive (there is no visits to other ports between them for the same vessel). The ports of v1 and v2 are called respectively origin and destination ports. The duration of the voyage vj(d) is the time of the last visit of e in the origin port and the time of first visit in the destination port.
Definition 3.5. (Voyage Graph): The Voyage Graph (VG) is a graph G = (V , E) built according to a set of voyages V J , in which V contains all the ports in V J and E contains an edge for each unique pair of ports in V J .
Definition 3.6. (Voyage Graph Snapshot): The Voyage Graph Snapshot (VGS) Gw = (V , E)w is an extension of the VG that includes a temporal time window w used to create the snapshot of the graph. This interval is used to select the AIS messages that will be used to build the snapshot Gw of VG G.
Algorithm 1: Trips Graph Snapshot Extraction
Input : M: AIS Messages divided into areas w: Time window size s: Time shifting r: Radius
P: Set of ports Output : G: set of Voyage Graph Snapshots
Init : G ← ∅; V ← ∅ 1 V ← Visits(Ai , P, r); 2 R1 ← Voyages(V); 3 R2 ← Clean(R1); 4 foreach b ∈ Buckets(w, s) do 5 G ← G + Graph(R2, b); 6 return G 4
This section describes the procedural methodology that we use to transform raw AIS data to a set of time series observations on the topological features of voyage graphs. We first describe the algorithm to build the voyage graph from the source data, then which features we extract from the graph, and finally how we create the time series. 4.1
Building the set of voyage graph snapshot directly from the original data would be possible, but also very unpractical. The dataset has a lot of noise, entries are not ordered in time, and much information is redundant. Therefore, we applied an incremental approach to process the data. First, we exploit the fact that the original dataset is already divided into geographical areas (i.e., the zones of the MarineCadastre.gov dateset, see Section5). For each area, we remove redundant information (e.g., subsequent entries for the same vessel in the same port, with the same timestamp) and compute the set of visits. Second, we compute the set of voyages using the visits, removing incorrect and noisy voyages. Third, from the voyages we can determine the graph and the snapshot according to the time window considered. This incremental process has several advantages: (i) graphs building is very fast, as the set of voyages is practically an edge list; (ii) the costly cleaning process is done only once, and from the clean collection of voyages it is possible to build multiple graphs; and (iii) it is interesting to study visits and voyages without transforming them into a graph.
The pseudocode in Algorithm 1 illustrates the steps that extract all the voyage graph snapshots (G0, . . . , Gn ) for a given set of AIS Messages M. Besides M, the algorithm also receives as parameters a Radius r , a set of ports P , a time window size w, and a shifting s. The shifting parameter s indicates the number of days to move forward the time window for each successive graph. For example, with s = 10, if the first time window starts on the 1st of January, the second starts at the 10th of January, and so on.
The algorithm starts by extracting the set of visits V (see definition 3.3) from M in each geographical area Ai in the original dataset with the function V isits() (line 1). This function returns V ⊂ Ai , such that V contains the AIS records transmitted inside the area α (p, r ) (see definition 3.2) for each port p ∈ P . Depending on r , there could be overlapping port areas such that the same AIS record results transmitted inside multiple ports. In these cases, we discriminate by associating the record to the closest port.
In turn, V feeds the function V oyaдes() that extracts the voyages of the vessels (line 2). The underlying assumption is that if a vessel e is seen at the port po ∈ P at time t0 and e is also seen at the port pf at time t1 and t1 > t0, then we record a voyage (definition 3.4).
The set of voyages is then cleaned by the function Clean() (line 3), to retain only the valid voyages. AIS data inevitably contains noise due to many reasons, including malfunctions, errors in transmission, and malicious use. In our context, such noise and mistakes translate into incorrect voyages. To remove them, we performed two cleaning actions. First, we removed those entries having null or invalid data in relevant fields (typically position or vessel type). For example, several incorrect entries had a vessel identifier, called Maritime Mobile Service Identity (MMSI), whose value is composed only by zeroes, which may indicate a placeholder for missing MMSI. We then removed the voyages that, depending on their duration (vjd ) and length, imply an impossible speed for a vessel. We set the length of a voyage by computing the geodesic distance between starting and arrival ports. The geodesic distance is the minimum distance between two points on earth, which can be used as the shortest possible maritime voyage. By using the length and the duration, we compute the estimated average speed based and removed those voyages whose speed exceeds 60 knots (which is still very high speed, but we left some margin to cope with a possible degree of approximation in the data). We did not remove the slow speed voyages as we cannot estimate how long is the actual maritime route between two ports with respect to the geodesic distance.
Finally, the algorithm builds the set of Voyage Graphs (definition 3.5) thought the function Graph() using the clean set of voyages R2 (line 5). This function uses the ports as vertices and the voyages as edges to build the graph. It considers the function Bucket () that creates all the possible time windows for the parameters w and s. 4.2
In order to study the evolution of the voyages graph, we employ
a set of graph metrics that are related to the diferent aspects
we wish to evaluate, called Topological Voyage Graph Features
(TVGs). In this paper, we studied only global network metrics
(i.e., related to the whole graphs). We used the networkx library
[
An important metric in studying and comparing graphs is the dimensions of the graph. To this end, we have considered the order (i.e., amount of nodes/ports in the graph) (fn ) and the size (i.e., amount of edges) (fe ). Semantically, these two measures are connected. A higher order and size can indicate an increased overall vessel trafic, and/or the tendency to perform less conservative routes, as more ports are involved. Inversely, a lower order and size can indicate a decreased overall vessel trafic, and/or the tendency to perform more conservative routes, as less ports are involved.
A relevant aspect is the identification of cohesive subgroups of ports in the graph, as a way to identify those ports that share a strong tie in the trafic for a particular vessel type. The number of Connected Components (CC, fc ) is the number of subgraphs in which any node is connected to each other by edges, and which is not connected to another subgraph. The number of Connected Components (fc ) indicates how much the graph represents a 1000 I 800 S eSM600 u iunq 400 200 0 5000 t4000 n u co3000 seg ya2000 o v 1000 0 0.6 0.5 e0.4 g a t n ce0.3 r e P 0.2 0.1 0.0 tug tow cargo tanker passenger sailing global scale activity (low CC number), rather than composed by a set of not connected and local activities (high CC number). The Average Clustering coeficient ( fa ), is the average of local clustering of nodes. The local clustering of each node in the graph is the fraction of triangles (set of 3 vertices such that any two of them are connected by an edge) that exist over all possible triangles in its neighborhood. In other words, this coeficient represents the probability that two neighbors of a node are neighbors themselves, and can serve to evaluate how many voyages happen around the same set of ports.
Another essential metric for the maritime networks is the
extension of their geographical spatiality, as the distance between
ports can be directed linked with various cost aspects as fuel
consumption, maintenance rates, and insurance costs [
0.61 0.44 0.23 0.26 Unique MMSI
Routes Count
A time-series is a collection of observations made sequentially
over the time [
In particular, we build time-series of the TVG features. For this purpose, we use Algorithm 1 to return the set of Voyages Graph Snapshot G, compute the TVGs for each one of the graph дi ∈ G and store them as separated time-series Tj where j indicate the TVG feature (i.e. number of nodes (fn ), number of edges (fe ), average clustering (fa ), number of strongly connected components (fc ), the average (fd ) and weighted average (fw ) link distance.
Let f unctionj be the function that compute the topological metric of a given graph д indicated by the index j, for instance if j is equal to fn then f unctionj computes the number of edges on the graph д. Also, let I be the set of existing temporal buckets in G and let J be the set of TVG features.
We then formalize the TVG time-series (T f ) with the following equations:
Tj B { f unctionj (дi ) | дi ∈ G, i ∈ I, j ∈ J } where:
J B { fn, fe , fa, fc , fd , fw }
I B {w1, w2, ..., wn } 5
In this section, we present the experiments conducted to assess the stationary behavior of the TVG features. We perform such analysis for the diferent spectrum of types of vessels. In the experiments, to build the Voyage Graph Snapshot using Algorithm 1, we assign respectively the values r = 5km, s = 10days, and w = 30days.
Our source of AIS data is the MarineCadastre.gov dataset [
Additionally, we use the Sea-Ports dataset [
The experiments conducted aim to answer the following research questions comprehensively. Our research question can be summarized as the following: Are the TVG time series stationary? Stationarity is an essential characteristic of a time series. A time series is said to be stationary if its statistical properties do not change over time. In other words, it has constant mean and variance, and covariance is independent of time. Section 5.2 address this research question. To address this research question, we will use a statistical test designed to comment on whether a time series is stationary explicitly. 5.1
Figure 2 shows, in percentage, the amount of unique MMSIs and route counts by vessel type and for the whole dataset. In the original dataset, there are several vessel categories: cargo, passenger, sailing, military, fishing, tanker, and tug tow. Interestingly, for cargo and tanker, a relevant percentage of unique MMSI correspond to a much lesser portion of total voyages. This is expected as these types of vessels perform less but longer voyages concerning other vessel types. By comparison, tug boats with 26% unique vessels have 61% of total routes. Unlike cargo and tankers, these routes are very short and relative to the vessels moving between nearby ports.
Among all categories, military and fishing account only for 1% of the total voyages, meaning that there are too little data to build meaningful graphs for these categories. We also did not consider tug tows as their routes mostly regard only two ports resulting in not interesting graphs. Therefore, from now on, we consider only the following categories: cargo (which also includes tanker) passenger, and sailing.
Figure 3 top and bottom show the amount of unique MMSIs respectively and voyages count for each vessel type and for each month in the period considered. Looking at cargo and tug tows, we can notice an evident pattern of less naval trafic in the winter periods (for example, from February to March 2016), in which both the number of unique MMSI and voyages has a clear drop. The drops are also visible (especially for cargo) in the same period of 2015 and 2017. Also, it interesting to notice the similarity in the trend of the cargo and tug tow, which can be explained by the fact the tug boats are mostly used to help large vessels, such as cargoes, into ports.
Figure 4 shows the graph resulting from cargo vessels in the northeast US in February-2016 (Figure 4 a) and August-2016 (Figure 4 b). It is clear from the graph that the trafic is more abundant during the summer because of the better climatic conditions. The graphs also show the complete halt of voyages in the great lakes during winter due to the formation of ice in the lakes.
Figure 5 shows the extracted time-series using the MarineCadastre.gov dataset for the features: number of nodes, number of edges, number of connected components, and average clustering, average distances and weighted average distance. For each TGV feature, we consider four diferent series: passenger, sailing, cargo, and all. 5.2
In this section, we address our research question of
investigating the (non) stationary behavior of the TVGs. A time series is
stationary if they do not have a trend or seasonal efects. This
means that the statistics calculated on the time series, such as
the mean, variance, and auto-correlation of the observations are
consistent over time [
There are diferent methods to verify whether a time series
is stationary or not. Statistical tests are widely used to analyze
if the requirements of stationary are met or have been violated.
Here, we adopted the Augmented Dickey-Fuller Test [
The null hypothesis of the test is that the time series is not stationary. The alternative hypothesis (rejecting the null hypothesis) is that the time series is stationary. When interpreting the p-value from this test, values below a threshold (such as 5% or 1%) suggests to reject the null hypothesis, i.e., the time-series is stationary. While, p-values above the threshold suggests to do not to reject the null hypothesis, meaning that the time-series is non-stationary.
We performed an ADF test on the TVG Time-series extracted from our dataset. The idea is that the more negative (lower) this ADF statistic, the more likely we have a stationary time-series or does not have time-dependent structure. We report the ADF test results on Table 1. The table reports for each TVG feature, and for each serie, the ADF-Statistic, the p-value and the critical values (1%, 5%, and 10%).
By looking at the results of each TGV feature, it is possible to see that most of the series have statistic values lower than the critical value of 1%, except the features avg_clustering, for the Serie sailing (ADF statistic equals to -2.851), and #cc, for the Serie passenger (ADF statistic equals to -3.431). This indicates weak evidence against the null hypothesis, so for these 2 cases, considering critical values at 1% level, these two TVG time-series are non-stationary.
Therefore, our analysis using the MarineCadastre.gov dataset suggests that there is a stationary characteristic over the time of the vessel’s voyages in the USA coast for the diferent considered vessels’ type (i.e., all, sailing, cargo and passenger). This characteristic has been presented in most of the investigated TGVs time-series, and it implies that the voyage graphs at diferent ranges of time points keep constant on average, without showing significant trends or seasonality during the years of 2015 and 2017. all cargo passenger sailing all cargo passenger sailing all cargo passenger sailing all cargo passenger sailing all cargo passenger sailing all cargo passenger sailing -9.355 -9.831 # nodes # edges avg_distance -3.494 -3.494 -3.494 -3.494 -3.494 -3.497 -3.494 -3.494 -3.494 -3.494 -3.494 -3.494 -2.889 -2.889 -2.889 -2.889 -2.889 -2.889 -2.889 -2.892 -2.889 -2.889 -2.891 -2.889 -2.889 -2.891 -2.889 -2.889 -2.889 -2.889 -2.889 -2.890 -2.889 -2.889 -2.889 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.583 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582 -2.582
This paper presented an analysis of the evolution of networks made by voyages of vessels between ports, based on several topological features of the network so-called Topological Voyage Graph Features (TVGs). The networks were built in a bottom-up and data-driven fashion, considering 3 years of AIS data of the US coastal waters. The analysis unraveled insights about the stationarity of several features over time, including the number of nodes and edges, clustering coeficient, and geodesic distance between the ports (nodes) of the network. The analysis was performed on the MarineCadastre.gov dataset containing vessels’ voyages in the USA coast. In particular, for this dataset, we found that for most of the TVGs, the time-series do not present any trend or seasonality behaviors.
We are aware of the limitations of applying our approach to a
single dataset that only covers the coast of the United States in a
relatively short time period of 3 years (2015 - 2017). In the future,
we plan to extend our study both in terms of the geographical
area covered (i.e., by including dataset from other countries and
possibly a worldwide network) and the time period. In addition,
the definition of the spatial area of ports can be improved to
increase the precision in voyages detection, in a way similar to the
one performed in [
The authors acknowledge the support of the H2020 EU Project MASTER (Multiple ASpects TrajEctoRy management and analysis) funded under the Marie Skłodowska-Curie grant agreement