887
1 INTRODUCTION
With the rapid growth of global maritime trade, multi-
ship encounter scenarios in complex navigational
waters are becoming increasingly frequent, placing
higher demands on the timeliness and accuracy of
maritime supervision systems. These scenarios involve
not only direct navigational conflicts among ships but
also mutually constrained dynamic decision- making
processes. Their high complexity and uncertainty make
traditional two-ship encounter analysis methods
inadequate. Although the International Regulations for
Preventing Collisions at Sea (COLREGs) clearly define
two-ship encounter types such as head-on, crossing,
and overtaking situations, the dynamic interaction
characteristics of multi-ship encounters have yet to be
unified under a comprehensive theoretical framework.
Existing approaches still face significant limitations in
terms of scenario representation and relationship
modeling [1,2].
At present, research on ship encounter scenario
identification primarily focuses on two- ship
encounters. The main approaches can be categorized
into indicator-based methods and machine learning-
based methods. Indicator-based methods determine
the presence of an encounter relationship based on the
spatiotemporal interactions between two ships.
Commonly used indicators include ship domain [3],
velocity obstacles [4], relative distance, and relative
speed [5]. While these indicators can effectively
identify potential encounter relationships in simple
scenarios, they often involve high computational
complexity and are prone to misidentification in
special or complex situations [6]. On the other hand,
machine learning-based methods leverage large
volumes of historical ship movement data to uncover
potential encounter patterns, offering stronger
generalization and adaptability [7]. However, these
approaches typically rely heavily on labeled data,
suffer from limited interpretability, and may lack
Multi-ship Encounter Identification Using Community
Detection of Complex Network
Y. Li
1,2
, F. Yang
1,2
, P. Chen
1,2
, L. Chen
1,2
& J. Mou
1,2
1
Wuhan University of Technology, Wuhan, China
2
Hubei Key Laboratory of Inland Shipping Technology, Wuhan, China
ABSTRACT: With the increasing maritime traffic, the effective identification of multi-ship encounter scenarios
has become an urgent demand for maritime management. Traditional clustering-based methods tend to generate
identification errors in complex environments. This paper proposes a community detection-based approach for
recognizing multi-ship encounter scenarios. Community detection is a technique that discovers collective
behavior patterns through network topology analysis. In this study, we first construct a ship encounter network
model incorporating dynamic ship features such as positions and headings to characterize encounter
relationships among ships. Subsequently, we employ the Louvain community detection algorithm to identify
communities within the network, where each community represents a multi-ship encounter scenario. Finally, a
case study using real AIS data from the Yangtze River Estuary demonstrates that the proposed method can
effectively identify multi-ship encounter scenarios.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 19
Number 3
September 2025
DOI: 10.12716/1001.19.03.23
888
stability when dealing with highly dynamic and
uncertain environments.
Compared to two-ship encounter scenarios, multi-
ship encounters involve not only direct navigational
conflicts between ships but also mutual constraints in
navigational decision- making, characterized by high
complexity and uncertainty. In recent years, spatial
clustering methods have been widely applied to
identify multi-ship encounter scenarios. These
methods analyze the spatial distribution patterns of
ships to detect locally dense areas and identify
potential encounter groups. Common clustering
algorithms, such as DBSCAN [8,9] and K- means, have
demonstrated good performance in processing static or
near-static ship distribution data. However, these
approaches primarily rely on the geometric positions
of ships and fail to fully consider their motion
characteristics and dynamic interactions, making it
difficult to reveal the underlying structural
relationships and potential cooperative behaviors
among ships. Moreover, clustering-based methods
typically decompose multi-ship encounters into a set of
pairwise relationships for analysis, which, while
simplifying the complexity of scenario identification,
often overlook the intrinsic interactions among
multiple ships [10].
To more effectively characterize the complex
interactions among ships in multi-ship encounter
scenarios, this paper proposes a community detection-
based method for multi-ship encounter identification.
Unlike traditional clustering methods, community
detection originates from complex network analysis
and emphasizes the density and connectivity of
relationships within a network structure. In this
approach, a ship interaction network is constructed by
treating each ship as a node and defining the edge
weights based on dynamic parameters such as relative
position, speed, and heading. This results in a
weighted graph model that captures the dynamic
interaction patterns among multiple ships. On this
basis, community detection algorithms are applied to
identify high-density substructures within the
network, enabling the effective discovery of ship
groups that are in potential encounter states. The
arrangement of the article is as follows: Section 2
illustrates the methodology of this paper, a case study
is performed in section 3 to show the results of the
algorithm and the comparison. and Section 4 discusses
the proposed method. Section 5 makes a conclusion.
2 METHODOLOGY
In this study, the objective is to identify multi-ship
encounter scenarios within a given maritime region.
The study is divided into three main parts: (1) AIS data
preprocessing, (2) construction of the ship encounters
complex network, and (3) identification of ship
encounter scenarios by community detection. The
overview of the methodology is shown in Figure 1
Figure 1.The overview of the methodology
2.1 AIS processing
AIS data preprocessing primarily consists of three key
steps: decoding, anomaly detection, and interpolation.
First, the raw AIS data in NMEA format is decoded to
extract essential navigational information, including
MMSI, latitude, longitude, speed over ground, course
over ground, and timestamps. Next, a combination of
rule-based screening and statistical analysis is applied
to identify abnormal data, such as invalid coordinates,
sudden speed changes, abrupt course shifts, and
discontinuities in timestamps. Data points with
significant errors are either removed or flagged. To
enhance the completeness and temporal consistency of
ship trajectories, kinematic interpolation[11] is used to
fill short-term gaps, and the data is resampled to a
uniform time interval. This results in continuous,
smoothed, and high-quality trajectory data suitable for
multi-ship interaction analysis. The equations of
kinematic interpolation are as follow:
( )
( )
i
a t b m t t= + −
(1.1)
In this equation, b is a vector representing the initial
acceleration of the moving object at the starting time ti,
while m is a vector denoting the change in acceleration
over time. By integrating the acceleration function, the
velocity and position functions can be obtained as
follows:
(1.2)
Here, vi and xi are vectors representing the initial
speed and position. When the two endpoints pi and pj
of the trajectory segment to be interpolated are known,
their attribute values can be substituted to solve for b
and m.
889
2.2 Ship encounters complex network
To effectively characterize the dynamic interactions
between ships, this study constructs a ship encounter
network based on AIS trajectory data. The network is
modeled as a weighted undirected graph, where each
node represents a ship. The existence of edges is
determined by the proximity relationship between
ships, while the edge weights reflect the intensity of
potential encounter influence between ship pairs. The
construction process consists of two main steps: edge
existence determination and edge weight calculation.
Firstly, the distance between each pair of ships is
calculated. If the distance is less than 6 nautical miles,
the ships are considered to have a potential encounter
relationship; otherwise, no encounter is assumed
between them. The equation for calculating the
distance between two ships is as follows:
2
1 sin
7915.7lg tan
4 2 1 sin
arctan
cos
i j i j
e
ii
i
i
ji
x x x y y y
y e y
M
ey
x
MM
y
s
= − = −





−
=+



+






=


−

=
(1.3)
Where, xi; xj and yi; yj are the latitude and longitude
coordinates of ship i and ship j, x and y are the
differences in longitude and latitude between the two
ships, Mi is the meridian arc length at the location of
ship i;
is the relative bearing between the two ships; e
is the eccentricity of the Earth's ellipsoid; and s is the
distance between the two ships.
If the distance between two ships is less than 6
nautical miles, their relative approach rate is further
calculated. If the approach rate is less than zero, the
two ships are considered to be approaching each other,
indicating a potential encounter relationship;
otherwise, no encounter is assumed. The equation for
calculating the approach rate is as follows:
( )
cos ,
ij ij
ij ij ij ij
ij
DV
R V D V
D
= =
(1.4)
where
ij
D
and
ij
V
are the relative distance and
speed of ship i and ship j, respectively. Rij represents
the proximity rate between two ships.
Once the existence of an edge between two ships is
confirmed, the edge weight is calculated to quantify
the encounter intensity. The equation for computing
the edge weight is as follow:
3
12
ij
ij ij ij
w
ww
DV
= + +
(1.5)
where Dij and Vij are the relative distance and speed of
ship i and ship j,
ij is the angle of intersection of ship i
and ship j.
2.3 Identification of ship encounter scenarios by
community detection
In order to recognize the ship groups in the multi-ship
encounter scenario, this paper adopts Louvain
Community Detection to recognize the community
structure of the network based on the constructed ship
encounters complex network.
The Louvain algorithm[12] aims to maximize
modularity by identifying densely connected
subgroups within a network, where intra-community
connections are strong and inter- community
connections are sparse. The algorithm consists of two
main phases. In the first phase, each node is initially
assigned to its own community, and the algorithm
iteratively considers moving each node to the
community of one of its neighbors if such a move
results in a higher modularity. Once no further
improvement can be achieved locally, the second phase
begins. In this phase, the identified communities are
aggregated into "super-nodes" to construct a new
network. The process is then repeated on the newly
formed network until the overall modularity no longer
increases significantly. The equation for Modularity is
as follow:
( )
,
1
,
22
ij
ij i j
ij
kk
Q A c c
mm

=−


(1.6)
where Aij represents the edge weights between ships i
and j, ki and kj represent the total marginal rights of ship
i and ship j . m is the sum of the weights of all edges in
the network.
The Louvain algorithm identifies communities in
which nodes are densely connected internally but
sparsely connected to nodes in other communities. In
the context of maritime traffic, this implies that ships
within the same community are more likely to interact
and influence each other, while ships outside the
community have relatively limited impact. Each
detected community can therefore be interpreted as a
multi-ship encounter scenario.
3 CASE STUDY
3.1 Data description and processing
To validate the proposed methodology, we conducted
a case study using real-world Automatic Identification
System (AIS) data collected from the Yangtze River
Estuary, China. The dataset spans a 24-hour period
from May 27 to May 28, 2019. Figure 2 illustrates the
visualization of raw AIS trajectories within the study
area. The AIS data underwent rigorous preprocessing
to ensure reliability. First, erroneous entries were
removed. Anchored ships were filtered out by
retaining only ships with speeds between 2 and 20
knots. To address irregular sampling intervals in the
raw data, we implemented a kinematic interpolation
method. Specifically, trajectory gaps exceeding 2
seconds were filled, ensuring temporal consistency and
spatial continuity. Table 1 shows the AIS configuration
information for the case study
890
Table 1 Configuration of the case study
Item
Configuration
Area:
Yangtze River Estuary
Latitude:
122°E to123°E
Longitude:
30.5°N to 31.3°N
Time:
2019-05-20 16:00:00 to 05-21 15:59:59
Speed:
2 knots to 40 knots
Figure 2. AIS trajectories
3.2 The construction of ship encounters complex network.
In this study, we constructed a complex ship encounter
network to represent potential interactions among
ships within a specific region. The network was then
partitioned into distinct encounter communities, each
representing a multi-ship encounter scenario.
Throughout this paper, we refer to these scenarios as
multi-ship encounter communities.
In this case study, we first extracted AIS data
corresponding to the timestamp 2019-05- 21 09:31:58,
and set the encounter threshold to 6 nautical miles. The
distance between each pair of ships was calculated
using Equation (3). For ship pairs within this threshold,
their relative approach was determined based on
Equation (4). If a ship pair was determined to be
approaching each other, the encounter influence—i.e.,
the edge weight in the network—was computed using
Equation (5). In Equation (5), the weighting
coefficients, and are set to 0.3, 0.3, and 0.4, respectively.
The constructed ship encounter complex network is
illustrated in Figure 3.
In Figure 3, the link between the two ships only
indicates the existence of a encounter influence
between the two ships and does not represent the
magnitude of the encounter influence
Figure 3. Ship encounters complex network
3.3 The identification of multi-ship encounter scenario
After constructing the ship encounter complex
network, we applied the Louvain algorithm for
community detection to identify multi-ship encounter
scenario in the network. The modularity calculation
used in the Louvain algorithm is detailed in Equation
(6).
In the Louvain algorithm, the resolution parameter
controls the granularity of community division,
thereby revealing community structures at different
scales. This parameter needs to be selected according
to the actual situation; typically, the range is between
0.1 and 5.0. Smaller resolution values tend to identify
larger communities, while larger resolution values
tend to identify smaller communities. In this study, we
set the resolution to 1, and we consider the community
size obtained under this resolution to be appropriate.
Figure 4 shows the results of identifying a multi-
ship encounter scenario using community detection,
where each color represents one identified community,
i.e., a multi-ship encounter scenario
Figure 4. Identification of multi-ship encounter by
community detection
Table 2 provides the MMSI information of the ships
with the ships identified in the multi- ship encounter
communities, based on the community detection
method.
Table 2. MMSI in different multi-ship encounter
communities
Community
MMSI
0
219xxx000, 412xxx860, 413xxx750, 13xxx650, 413xxx290,
413xxx820, 413xxx780, 413xxx110, 413xxx430,
413xxx000, 563xxx900,
5
354xxx000, 412xxx720, 412xxx520, 412xxx440,
413xxx000,413xxx770, 413xxx620, 413xxx650,
413xxx630, 413xxx890, 414xxx260, 414xxx230,
4
351xxx000, 354xxx000, 412xxx290, 412xxx690,
412xxx580, 413xxx370 413xxx770, 413xxx810,
413xxx490, 413xxx110, 413xxx040, 413xxx070,
413xxx000, 413xxx920, 413xxx040, 413xxx330,
414xxx000, 477xxx900, 538xxx255, 538xxx202,
538xxx464, 564xxx000, 613xxx545, 636xxx895
11
412xxx450, 412xxx710, 413xxx770, 413xxx320,
413xxx050, 413xxx030, 413xxx170, 413xxx240
891
4 DISCUSSION
4.1 The validation of the methodology
In this section, we verify the effectiveness of our
proposed method by analyzing the topological
connection characteristics of each identified multi-ship
encounter community. First, we examined the
encounter connections within and between
communities, as shown in Figure 5.
Figure 5 presents a comparison of internal and
external connections for each community. The results
demonstrate that the number of internal connections
within communities is significantly higher than
connections between different communities, indicating
that our community partitioning successfully captures
dense connection patterns in the complex network of
ship encounters.
Figure 5. Comparison of encounter relations internal and
external in communities(scenario)
In real maritime traffic environments, these dense
connections indicate that ships within the same
community face encounter conflicts with multiple
ships simultaneously. These ships and their encounter
relationships collectively form a multi-ship encounter
scenario. This finding provides evidence that our
proposed method, based on complex network
community detection, effectively identifies areas with
dense ship encounters—specifically, the multi-ship
encounter scenarios existing in the region.
Figure 6. Distribution of connection strengths for internal
and external in communities
Furthermore, we analyzed the distribution of
connection strengths for each identified multi-ship
encounter community, as shown in Figure 6. The
average strength of internal connections was found to
be substantially higher than that of external
connections. This significant difference demonstrates
that encounter conflicts within each multi-ship
encounter community are considerably more intense
than conflicts between communities. In identifying
multi-ship encounter scenarios, ships belonging to the
same community exhibit more frequent and stronger
interactions, while interactions between ships from
different communities are notably weaker. This pattern
aligns closely with the characteristics of real-world
multi-ship encounters. The statistical features
illustrated in both figures collectively validate the high
accuracy and reliability of our proposed community
detection method in extracting multi-ship encounter
scenarios.
4.2 The comparision with DBSCAN
In this section, we use the DBSCAN algorithm to
recognize the multi-ship encounter scenarios in the
region, and compare the results with those of the
proposed method in this study, and the results are
shown in Figure 7.
Figure 7. The comparison of community detection and
DBSCAN
DBSCAN is a density-based clustering algorithm
that identifies clusters by evaluating the density of data
points. In Figure 6, to ensure consistency with the
parameters used in the community detection method,
the neighborhood radius was set to 6 nautical miles,
and the minimum number of points (MinPts) was set
to 2. As shown in the figure, DBSCAN is capable of
effectively identifying densely grouped ships.
892
However, it also highlights two key limitations: first,
the occurrence of density-connected clusters, where
ships that are spatially close but belong to different
traffic behaviors are incorrectly grouped together; and
second, the identification of noise points. These noise
points refer to isolated ships that do not meet the
density threshold, which may lead to the exclusion of
potential multi-ship encounter scenarios, resulting in
recognition errors.
In contrast, community detection methods such as
the Louvain algorithm do not rely on spatial density
but instead partition the network based on the
encounter relationships between ships. By optimizing
network modularity, the algorithm effectively
identifies tightly connected and frequently interacting
groups of ships, making it more suitable for analyzing
complex ship dynamics and potential multi-ship
encounters. Moreover, community detection
demonstrates stronger robustness and adaptability,
allowing it to reliably uncover meaningful encounter
clusters even in cases where the network structure is
complex or the spatial distribution is uneven.
5 CONCLUSIONS
In this study, we proposed a community detection-
based method for identifying multi- ship encounter
scenarios within a specific region using complex
networks. Specifically, after preprocessing the regional
AIS data, we divided it into time slices and represented
each ship as a node in the network. The encounter
influence between ship pairs—calculated based on
geographic distance, relative motion, and crossing
angle—was used as the weight of the edges. In this
way, a weighted complex ship encounter network was
constructed. We then applied the Louvain algorithm to
perform community detection, aiming to identify
encounter communities within the network. Each
community represents a multi-ship encounter scenario
in the region. Finally, a case study using real AIS data
from the Yangtze River Estuary was conducted, and
the results demonstrated that the proposed method can
effectively identify multi-ship encounter situations in
regional maritime traffic.
Finally, we further validated the effectiveness of the
proposed method by analyzing the internal and
external connectivity of the identified multi-ship
encounter communities. We also compared our
approach with DBSCAN, highlighting the strengths of
our method. While DBSCAN is capable of effectively
identifying dense clusters of ships, it may misclassify
noise points and suffer from the issue of density-
connected clusters. In contrast, the community
detection method based on the Louvain algorithm is
more robust in identifying complex multi- ship
encounter scenarios and provides clearer structural
insights. However, despite its advantages, the
proposed method also has certain limitations. The
accuracy of community detection largely depends on
the resolution parameter in the Louvain algorithm,
which requires careful tuning to balance the
granularity of the detected communities. Moreover,
although the method performs robustly in detecting
ship encounters under most conditions, it may struggle
in cases where ships are evenly distributed, making
community boundaries less distinct. Future work will
focus on enhancing the adaptability of the algorithm by
integrating additional factors to improve performance
in such scenarios.
ACKNOWLEDGMENT
This work is supported by the National Natural Science
Foundation of China under grants 52101402, 52271367, and
52271364. The historical AIS data is provided by the Wuhan
University of Technology.
REFERENCE
[1] Tian W, Zhu M, Han P, Li G, Zhang H. Pairwise ship
encounter identification and classification for knowledge
extraction. Ocean Eng 2024;294:116752.
[2] Zhen R, Riveiro M, Jin Y. A novel analytic framework of
real-time multi-vessel collision risk assessment for
maritime traffic surveillance. Ocean Eng 2017;145:492–
501.
[3] Deng F, Jin L, Hou X, Wang L, Li B, Yang H. COLREGs:
Compliant Dynamic Obstacle Avoidance of USVs Based
on the Dynamic Navigation Ship Domain. J Mar Sci Eng
2021;9.
[4] Du L, Goerlandt F, Banda OAV, Huang Y, Wen Y, Kujala
P. Improving stand-on ship’s situational awareness by
estimating the intention of the give-way ship. Ocean Eng
2020;201:107110.
[5] Ma X, Shi G, Shi J, Liu J. A framework of marine collision
risk identification strategy using AIS data. J Navig
2023;76:525–44.
[6] Zhu J, Gao M, Zhang A, Hu Y, Zeng X. Multi-Ship
Encounter Situation Identification and Analysis Based on
AIS Data and Graph Complex Network Theory. J Mar Sci
Eng 2022;10.1536
[7] Zeng X, Gao M, Zhang A, Zhu J, Hu Y, Chen P, et al.
Trajectories prediction in multi-ship encounters: Utilizing
graph convolutional neural networks with GRU and Self-
Attention Mechanism. Comput Electr Eng
2024;120.109679.
[8] Huang C, Wang X, Wang H, Kong J, Zhou J. A novel
regional ship collision risk assessment framework for
multi-ship encounters in complex waters. Ocean Eng
2024;309:118583.
[9] Lyu H, Ma X, Tan G, Yin Y, Sun X, Zhang L, et al.
Identification of Complex Multi-Vessel Encounter
Scenarios and Collision Avoidance Decision Modeling for
MASSs. J Mar Sci Eng 2024;12.1289.
[10] Cheng Z, Chen P, Mou J, Chen L. Novel collision risk
measurement method for multi- ship encounters via
velocity obstacles and temporal proximity. Ocean Eng
2024;302.117585.
[11] Long J. Kinematic interpolation of movement data. Int J
Geogr Inf Sci 2015;30:1–15. [12] Blondel V, Guillaume J,
Lambiotte R. Fast unfolding of communities in large
networks: 15 years later. J Stat Mech-Theory Exp
2024;2024.