# Enhanced Visual Feedback with Decoupled Viewpoint Control in Immersive
Humanoid Robot Teleoperation using SLAM

Yang Chen∗, Leyuan Sun∗, Mehdi Benallegue, Rafael Cisneros-Limón, Rohan P.
Singh, Kenji Kaneko,
Arnaud Tanguy, Guillaume Caron, Kenji Suzuki, Abderrahmane Kheddar, and Fumio
Kanehiro Yang Chen∗ and Leyuan Sun∗ are co-first authors and contributed
equally to this work. Corresponding author: Yang Chen.Y. Chen is with the
School of Integrative and Global Majors (SIGMA), University of Tsukuba, Japan.
<EMAIL_ADDRESS>Sun, R.P. Singh and F. Kanehiro are with
Department of Intelligent and Mechanical Interaction Systems, Graduate School
of Science and Technology, University of Tsukuba, Japan. G. Caron is with
Universite de Picardie Jules Verne, MIS lab, Amiens, France.All authors are
with CNRS-AIST JRL (Joint Robotics Laboratory), IRL, National Institute of
Advanced Industrial Science and Technology (AIST). son.leyuansun,
mehdi.benallegue, rafael.cisneros, rohan-singh, k.kaneko, guillaume.caron,
f-kanehiro @aist.go.jp; arnaud.tanguy<EMAIL_ADDRESS>Suzuki is with the
Faculty of Engineering and Center for Cybernetics Research, University of
Tsukuba, Japan<EMAIL_ADDRESS>
###### Abstract

In immersive humanoid robot teleoperation, there are three main shortcomings
that can alter the transparency of the visual feedback: (i) the lag between
the motion of the operator’s and robot’s head due to network communication
delays or slow robot joint motion. This latency could cause a noticeable delay
in the visual feedback, which jeopardizes the embodiment quality, can cause
dizziness, and affects the interactivity resulting in operator frequent motion
pauses for the visual feedback to settle; (ii) the mismatch between the
camera’s and the headset’s field-of-views (FOV), the former having generally a
lower FOV; and (iii) a mismatch between human’s and robot’s range of motions
of the neck, the latter being also generally lower. In order to leverage these
drawbacks, we developed a decoupled viewpoint control solution for a humanoid
platform which allows visual feedback with low-latency and artificially
increases the camera’s FOV range to match that of the operator’s headset. Our
novel solution uses SLAM technology to enhance the visual feedback from a
reconstructed mesh, complementing the areas that are not covered by the visual
feedback from the robot. The visual feedback is presented as a point cloud in
real-time to the operator. As a result, the operator is fed with real-time
vision from the robot’s head orientation by observing the pose of the point
cloud. Balancing this kind of awareness and immersion is important in virtual
reality based teleoperation, considering the safety and robustness of the
control system. An experiment shows that the effectiveness of our solution.

###### Index Terms:

VR teleoperation, humanoid, latency, immersive

##  I Introduction

Teleoperation technology is getting a renewed attention due to its potential
in transferring human’s intelligence and actions to a remote location, whose
interest is even more relevant due to the current Covid-19 outbreak. ANA
Avatar XPrize [1] is one of the robotics competitions encouraging this trend.
In teleoperation, a common setup consists of an operator equipped with a
master station to control, through network communication, a robot situated at
a remote location. For an immersive control of the robot’s head motion and
receiving a visual feedback from the robot, a wearable head-mounted display
(HMD) is the most common choice. One of the common issues faced in
teleoperation is the lag between operator’s and robot’s head motion due to
network communication delays or slow robot joint motion. The visual rendering
of the robot’s vision sensor (e.g., embedded stereo camera) is delayed.

Figure 1: Proposed tele-visualization. Top side: real scene, left-down side:
virtual scene, the real-time point cloud is shown in the area inside the red
dot line, the area outside denotes the constructed mesh, right-down side:
operator.

In an immersive experience, such rendering latency causes dizziness especially
when the operator moves her/his head fast [2]. If the viewpoint of HMD is
decoupled from the visual information or if its FOV is larger than that of the
camera, then there is a blank area that is not covered by the visual feedback
from the robot’s camera.

Furthermore, humanoid robots often have a lower range of motion w.r.t humans,
which may also limit the visual perception if the operator’s master station
does not constrain the operator head to match the robot’s head motion (a
highly impractical setup).

In order to deal with such shortcomings, we propose a decoupled viewpoint
solution using SLAM technology for humanoid teleoperation. Our idea is novel
and simple to understand: we are using a point cloud as real-time
visualization feedback, and a pre-constructed mesh that complement and enhance
real-time visual data in blank areas caused by the previously mentioned
shortcomings. The latter (tracking latency, robot’s joint range limits and
camera’s smaller FOV) are handled all at once. This is illustrated in Fig. 1.

The main contributions of our paper are listed as follows:

  1. 1.

We devised a decoupled viewpoint solution for a humanoid platform which allows
the operators to sustain visual feedback changes with low-latency when they
freely control their hidden view duplicate in an augmented reality
environment.

  2. 2.

Use a reconstructed mesh built by SLAM to complement the blank area caused by
the mismatch between FOVs, or the mismatch between range of neck joints or the
lag between operator’s and robot’s head motion.

  3. 3.

We propose an online calibration solution which could align the virtual HMD
and the virtual robot camera frame for the best visualization quality of the
point cloud.

##  II Related works

In this section, we introduce the SLAM technology used in humanoid robots and
the different televisualizations in VR teleoperation with a focus on robot
application.

SLAM in humanoids: Humanoid robots already use visual SLAM technology for
navigation in various environments thanks to their embedded cameras, e.g. [3].
Recently, [4] used the map built by SLAM not only for locomotion but also for
searching an object and estimating its pose by using point cloud registration.
[5] integrated dense SLAM to a QP control framework for localization and also
balancing a humanoid robot, which allows using visual odometry to make a
reaching plan adjustable online. Besides, SLAM is a fundamental technology
when humanoids are used in large-scale manufacturing settings, e.g., [6]. It
is used to provide precise localization to a humanoid within its environment,
build a semantic-reconstructed map, define the walking targets and so on.
These few examples only show that SLAM is already adopted in several humanoid
applications and is part of the humanoid basic planning and control
architecture. This work highlights another application of the existing
embedded SLAM in the humanoid embodied telepresence context.

With respect to televisualization works, we introduce a solution using first-
person-view for televisualization, which is a common choice to be applied on
humanoid platform, as it is more immersive than the third-person-view.

Stereo RGB fixed: Displaying real-time stereo RGB image from a stereo camera
by means of a VR HMD [7, 8] is the most common practice in VR teleoperation.
Compared with non-VR type, such as video streaming on an external monitor, the
HMD allows better immersive capabilities and is more suitable to estimate the
depth of objects present in the remote world. However, the latency between the
motion of operator’s and robot’s head induced by a fast motion of the former,
compromises the coherency of the visual feedback w.r.t sensory expectations
and may cause dizziness. Moreover, this problem compromises intuitive
interaction, as explained in Section I.

Decoupled viewpoint: Instead of directly mapping the stereo RGB image to the
operator both eyes, decoupled viewpoint means that the operator could realize
the an independent motion from the real-time robot’s head motion in VR
visualization. For example, when the operator moves the head quickly, the
direct mapping solution does not update visual feedback instantly, yet a naive
decoupled viewpoint will generate blank (empty) spaces in the image first and
the RGB or point cloud will move towards that space gradually with the speed
of the robot’s head movement. Theoretically, this solution could reduce the
dizziness compared with the direct mapping solution, since the operator could
realize that the head motion changes the visual feedback, even if there is
only a blank area being displayed. Yet, the latency in visual feedback display
in the HMD still exists. The most recent work we could find which applied a
decoupled viewpoint control is reported in [9, 10], and is developed by Team
NimbRo in the frame of ANA Avatar XPrize. Thanks to the wide-angle camera that
they use and the 6D DOF of their robot’s head, their solution could allow the
operator to freely control their perception in the VR device and the blank
space caused by a decoupled viewpoint could be complemented by a spherical
rendering method that they proposed. However, the limitation of spherical
rendering is that the entire scene is considered with a constant depth, or
otherwise, a distortion of image happens (as they reported).

Decoupled viewpoint with reconstructed mesh or CAD model: The closest solution
we found related to this concept is from Team
I-BOTICS111https://www.youtube.com/watch?v=mL9SyGfuqI4 for ANA Avatar XPrize
using RGB with a CAD model as televisualization feedback. The RGB image
provides real-time visual feedback, while the CAD model of the scene
complements the latency that causes the aforementioned blank area. Different
from this solution, we rather use a point cloud to fuse with the reconstructed
mesh built by using SLAM technology. The advantages of our solution are that
i) we do not need the knowledge of the environment since the mesh can be
reconstructed on-line when the robot explores the working area; and ii) the
visualization of point cloud fused (aligned) with the mesh has better
immersion properties compared to RGB with CAD and mesh; see Section III-C.

For other mobile platforms, a third-person-view is used. For example, in [11]
the operator can adjust the pose of the viewpoint manually; they also provide
a constructed mesh for visualization. However, there is no real-time
information to complement the mesh, and the mesh is updated with a low
frequency, making it difficult to handle dynamic scene. An intuitive interface
for bimanual robot teleoperation system was developed in [12]. RGB merged with
3D point cloud is used for televisualization. The system could track the
operator’s head motion to make him freely look around using the VR view.
However, the limitation of this solution is the need for additional operator
support to select these views’ positions.

For teleoperation of industrial robotic arms, the third-person-view is the
best choice, as a clear and complete observation is more important than
immersion. [13] proposed three viewpoints for the operator to select during
teleoperation. In the HMD, the operator could select freely to see the model
of robot arm from side, front, and top view. Another approach called Picture-
in-Picture (PiP) is also common, where video streams from multiple views are
displayed concurrently and placed next to each other [14, 15]. Both solutions
increase the cognitive burden for the operator. [16] provided a multi-visual
source merging solution where the local point cloud is projected to a global
stereo image nicely, providing additional information for grasping tasks.
However, in contrast to our solution, it requires an additional visual sensor.
In [17], the authors use a VR environment to compensate the difference of FOV
between HMD and camera. It has better immersion than not using anything but
the artificial environment cannot represent the true surroundings like our
reconstructed mesh. So far, the early work of a total VR-based decoupling is
reported in [18], but this solution cuts fully the operator from the real
perception even if features such as the manipulated objects are updated from
the real world.

##  III Methodology

###  III-A Robot Platform and VR Equipment

We use the HRP-4CR robot [19], an adult-size humanoid with realistic
appearance, which is an upgraded and ”refreshed” version of HRP-4C in [20]. A
ZED Mini camera (from Stereolabs Inc.) is mounted on the forehead of the
robot. On the operator side, an HTC Vive Pro Eye HMD (from HTC Corporation) is
worn by the operator to receive the visual information and transfer the
control command to the robot’s head at the same time. The joystick which is
mounted on a Valve Index controller (from Valve Corporation) is used for
controlling the locomotion of the robot.

Our method is general enough to apply to any other similar set-up with
humanoid, camera and HMD providing few coding adjustments.

###  III-B System architecture

The robot control unit is an Intel NUC computer, a Jetson Nano (from Nvidia
Corporation) is used for interfacing with the ZED Mini camera and streaming
the visual information over a wired-LAN. The operator station is driven by a
PC with specification (Intel i9-9900K 3.6 GHz, Nvidia RTX 2080Ti), mainly for
running Unity3D (the platform we used for building a virtual space). All
computers are connected by Ethernet. The system architecture is shown in Fig.
2. The communication protocol between NUC and Windows PC is ROS-
Sharp222https://github.com/siemens/ros-sharp.

Figure 2: System architecture.

###  III-C Conceptual evaluation of visual expressions

Compared to the method that fuses 3D mesh and 2D RGB image, fusing 3D point
cloud and 3D mesh would result (in theory) in a better merging visual effect.
As a result, one expects a better immersion for the operator. The difficulty
of fusing 2D RGB image and 3D mesh comes from the distortion of a 2D image
when observed from different viewpoints. A concept of visualization is
illustrated in Fig. 3, where there is a decoupled movement between the virtual
HMD camera and the virtual robot camera in a VR environment (virtual space).
Consider that the robot camera is capturing a 3D object such as a cube, then a
RGB image or point cloud can be generated in the virtual sapce, due to the 2D
property of the RGB image, the distortion can happen when it is observed from
the virtual HMD. The distortion can be much less if 3D point cloud are used
instead and if we assume the shape of point cloud is similar to the object
itself.

The fusion quality between 3D point cloud and 3D mesh relies on the quality of
the constructed mesh, the point cloud and the accuracy of odometry. Here we
use a state-of-art 3D construction method called ”Spatial Mapping”
333https://www.stereolabs.com/docs/spatial-mapping/ and ZED visual-inertial
odometry. With the odometry as a memory of the point cloud localization, the
alignment between the constructed mesh and point cloud can be accomplished
automatically. An expected fusion-effect example is shown in Fig. 1; compare
the real scene (top side) and the virtual scene (left-down side), there we see
that the mesh is well-fused with the real-time point cloud.

A fusion between the constructed mesh and the real-time point-cloud with an
additional decoupled viewpoint control method will be presented in Section
III-D. Using that method, the operator is able to intuitively control the
perspective to observe the environment as s/he wants, increasing the
immersion. However, in our tele-operation scenario, being aware of the
difference between self and robot is important, since there exists a
significant difference between a human and the avatar robot. Considering that
the operator moves the head quickly, the perspective also changes fast. If the
operator is not aware that the robot head motion is delayed, then the
operation may cause an accident, e.g. a robot collision with the environment.
Our proposed solution is to make the color of the constructed mesh a bit
different from the real color of the environment. Therefore, the operator can
distinguish the mesh and real-time point-cloud to achieve a balance between
awareness and immersion. This is also helpful when the environment is dynamic,
as the operator would put more trust on the real-time information instead of
the mesh.

Figure 3: Concept analysis. The virtual HMD should be able to see what the
real robot camera can see, in the scenario denoted above, the distortion could
happen.

###  III-D Construction of virtual space & teleoperation mapping

Figure 4: Teleportation mapping: the motion of the operator’s head, robot’s
head and ZED camera are mapped to the virtual space as depicted by the blue,
green and black lines.

The creation of a virtual space is necessary for the VR televisualization
system which we introduced in Section II. From the solution of Stereo RGB
fixed to decoupled viewpoint with reconstructed mesh or CAD model, the
complexity of the virtual space increases. Here we explain the key difference
between those solutions; specifically, we introduce the construction method of
our proposal, which lies on the category of decoupled viewpoint with
reconstructed mesh or CAD model.

For the stereo RGB fixed, the virtual space is the simplest situation: map the
image of each camera eye to each eye of the HMD. For the decoupled viewpoint,
we need to represent the decoupled motion of a robot camera and HMD in the
virtual space. For the decoupled viewpoint with reconstructed mesh or CAD
model, because we have the mesh as a world reference in the virtual space, not
only the relative relation between robot camera and HMD has to be represented
properly, but also the relation between robot camera, HMD and the mesh.

To better demonstrate the mapping relationship in our tele-visualization
system, we have separated the space into three parts: operator space, virtual
space, and robot space, as shown in Fig. 4. All frames are described in TABLE
I.

TABLE I: Frame definition

Virtual space | Operator and Robot space
---|---
Virtual HMD frame: H’ | HMD frame: H
Virtual ZED frame: Z’ | ZED frame: Z
Virtual tracking space frame: T’ | Tracking space frame: T
Virtual robot body frame: R’ | Robot body frame: R
World frame in virtual space: W’ | World frame: W
Mesh frame: S | Robot’s head frame: Rh
Base station frame: B |

The measurements are shown in Eq. 1: The description of the HMD frame in the
tracking space frame is $M_{H}^{T}=M_{B}^{T}\cdot M_{H}^{B}$, where
$M_{B}^{T}$ is a fixed value calibrated when we did the VR room setup
procedure, $M_{H}^{B}$ is a real-time measurement made by the base station
(from Valve Corporation), and $M_{H}^{T}$ represents the head movement of the
operator. The ZED pose relative to the robot body frame is
$M_{Z}^{R}=M_{Rh}^{R}\cdot M_{Z}^{Rh}$, which are measured from the forward
kinematics and the extrinsic respectively. $M_{Z}^{W}$ is measured by the ZED
visual-inertial odometry in world frame (using ZED SDK). Then,

$\mathbf{M}=[M_{H}^{T},M_{Z}^{R},M_{Z}^{W}]$ (1)

Those ones are also mapped from the operator and robot space to the virtual
space as shown below:

$\displaystyle\mathbf{M^{{}^{\prime}}}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbf{M},$ (2)
$\displaystyle\mathbf{M^{{}^{\prime}}}$
$\displaystyle=[M_{H^{{}^{\prime}}}^{T^{{}^{\prime}}},M_{Z^{{}^{\prime}}}^{R^{{}^{\prime}}},M_{Z^{{}^{\prime}}}^{W^{{}^{\prime}}}].$

In order to realize the decoupled motion between the virtual ZED frame and the
virtual HMD frame, we rely on Eq. 3, namely

$\displaystyle M_{Z^{{}^{\prime}}}^{H^{{}^{\prime}}}$
$\displaystyle=M_{T^{{}^{\prime}}}^{H^{{}^{\prime}}}\cdot
M_{R^{{}^{\prime}}}^{T^{{}^{\prime}}}\cdot
M_{Z^{{}^{\prime}}}^{R^{{}^{\prime}}}$ (3) $\displaystyle=M_{T}^{H}\cdot
M_{R^{{}^{\prime}}}^{T^{{}^{\prime}}}\cdot M_{Z}^{R},$

where $M_{R^{{}^{\prime}}}^{T^{{}^{\prime}}}$ is a static transformation which
can be calibrated in order to display point cloud in HMD properly,. The
details of the calibration will be discussed in Section 5. When there is no
mesh,
$M_{Z^{{}^{\prime}}}^{W^{{}^{\prime}}}=M_{R^{{}^{\prime}}}^{W^{{}^{\prime}}}\cdot
M_{Z^{{}^{\prime}}}^{R^{{}^{\prime}}}$,
$M_{T^{{}^{\prime}}}^{W^{{}^{\prime}}}=M_{R^{{}^{\prime}}}^{W^{{}^{\prime}}}\cdot
M_{T^{{}^{\prime}}}^{R^{{}^{\prime}}}$, and
$M_{H^{{}^{\prime}}}^{W^{{}^{\prime}}}=M_{R^{{}^{\prime}}}^{W^{{}^{\prime}}}\cdot
M_{T^{{}^{\prime}}}^{R^{{}^{\prime}}}\cdot
M_{H^{{}^{\prime}}}^{T^{{}^{\prime}}}$ can be determined by any given constant
value of $M_{R^{{}^{\prime}}}^{W^{{}^{\prime}}}$. As a result, we realize a
flow: the operator moves the head $\rightarrow$ the robot’s head follows this
movement with a motion delay $\rightarrow$ the point cloud in virtual space
moves together with the ZED frame with a network delay $\rightarrow$ the
visual feedback described in the HMD frame updates accordingly.

However, when there is a mesh, to align point cloud and mesh properly, instead
of being a constant value, $M_{R^{{}^{\prime}}}^{W^{{}^{\prime}}}$ should be
the odometry of robot’s body frame w.r.t. the world frame. Here, we rely on
the ZED visual-inertial odometry, and use Eq. 4 to realize

$M_{R^{{}^{\prime}}}^{W^{{}^{\prime}}}\stackrel{{\scriptstyle\text{def}}}{{=}}M_{R}^{W}=M_{Z}^{W}\cdot{M_{Z}^{R}}^{-1}.$
(4)

The precision of ZED visual-inertial odometry is studied in [21]. $M_{R}^{W}$
can also be obtained by other localization methods such as motion capture or
the kinematics-inertial odometry of the robot itself, but those methods either
require additional sensor or they are not precise enough for our requirements.
In the case of having a mesh, we have another flow for locomotion: the
operator controls the robot’s locomotion by joystick $\rightarrow$ the robot’s
body moves with a motion delay $\rightarrow$ the point cloud in virtual space
moves together with the ZED frame with a network delay $\rightarrow$ the
visual feedback described in the HMD frame updates accordingly.

###  III-E Online calibration

Figure 5: Calibration process for the best viewpoint of the point cloud
visualization: move the virtual tracking space frame from $T^{\prime}$ to
$T^{\prime\prime}$ in order to align $H^{\prime\prime}$ with $Z^{\prime}$.
$H^{\prime\prime}$ and $T^{\prime\prime}$ are the calibrated virtual HMD frame
and calibrated virtual tracking space frame during the calibration process.
After the calibration, $H^{\prime\prime}$ coincides with $Z^{\prime}$. Figure
6: Top: initialization calibration, bottom: calibration during experiment,
distortion shown in white rectangle caused by the operator shifting position
as shown in the red rectangle. Left represents before, right represents after
calibration.

We have realized the decoupled motion control for both virtual ZED frame and
virtual HMD frame by using Eq. 3; however, the height of users can be
different, or the user may also move the body slightly during operation. Both
factors cause a change of $M_{H^{{}^{\prime}}}^{T^{{}^{\prime}}}$, resulting
in the virtual HMD frame misalignment with respect to the virtual ZED frame.
The visualization of point cloud from different viewpoints should have a
similar effect as we analyzed in Section III-C. However, as the point cloud is
usually not generated perfectly, its visualization from an offset viewpoint
might cause a distortion as shown in Fig. 6. Furthermore, the misalignment can
cause the operator to misjudge the relative pose between objects and robot. In
order to visualize the point cloud correctly inside the FOV of the HMD, we
propose the online calibration method shown in Fig. 5. The calibration problem
is defined as bellow:

$\displaystyle M_{H^{{}^{\prime\prime}}}^{W^{{}^{\prime}}}$
$\displaystyle=M_{Z^{{}^{\prime}}}^{W^{{}^{\prime}}},$ (5)
$\displaystyle\textrm{s.t.}\quad
M_{T^{{}^{\prime\prime}}}^{H^{{}^{\prime\prime}}}$
$\displaystyle=M_{T^{{}^{\prime}}}^{H^{{}^{\prime}}},$

where $H^{{}^{\prime\prime}}$ and $T^{{}^{\prime\prime}}$ represent the
calibrated virtual HMD frame and calibrated virtual tracking space frame. The
relative pose between the virtual HMD frame and the virtual tracking space
frame is always decided by the localization based on the base station’s
measurement; so instead of changing the pose of the virtual HMD frame
directly, we move the virtual tracking space frame from $T^{{}^{\prime}}$ to
$T^{{}^{\prime\prime}}$ to align the calibrated virtual HMD frame with the
virtual ZED frame as decomposed by Eq. LABEL:equation8:

$\displaystyle M_{H^{{}^{\prime\prime}}}^{W^{{}^{\prime}}}$
$\displaystyle=M_{R^{{}^{\prime}}}^{W^{{}^{\prime}}}\cdot
M_{T^{{}^{\prime\prime}}}^{R^{{}^{\prime}}}\cdot
M_{H^{{}^{\prime\prime}}}^{T^{{}^{\prime\prime}}}$ (6)
$\displaystyle=M_{Z}^{W}\cdot{M_{Z}^{R}}^{-1}\cdot
M_{T^{{}^{\prime\prime}}}^{R^{{}^{\prime}}}\cdot M_{H}^{T}.$

We can obtain transformation from the $T^{\prime\prime}$ to $R^{\prime}$ by
using Eq.7, which is the one we need to update the alignment:

$\displaystyle M_{T^{{}^{\prime\prime}}}^{R^{{}^{\prime}}}$
$\displaystyle=M_{Z^{{}^{\prime}}}^{R^{{}^{\prime}}}\cdot
M_{T^{{}^{\prime\prime}}}^{Z^{{}^{\prime}}}$ (7) $\displaystyle=M_{Z}^{R}\cdot
M_{T^{{}^{\prime\prime}}}^{H^{{}^{\prime\prime}}}$
$\displaystyle=M_{Z}^{R}\cdot M_{T}^{H}.$

One example of the effect of calibration is shown in Fig. 6. There are also
more things to note: (1) The calibration can be activated by the operator
voluntarily pressing a trigger on the controller during tele-operation. (2)
The calibration usually only needs to be done when the operator has changed or
when the operator’s position changes too much during the tele-operation
process, as most of the time the point cloud looks good enough even with a
small misalignment. (3) The calibration can be activated at any moment and can
finish instantly during the operation. (4) It’s better to calibrate with a
looking forward posture and in a static status, with consideration for the
best effect on the decoupled viewpoint.

Figure 7: The latency caused by different rates of the low-pass filter.

###  III-F Low Pass Filter

Like other related works [9] [10] and [11], we also need to apply a low-pass
filter in order to increase the smoothness of motion and immersion of VR
experience. Before its implementation, we first analyze the source of noise.
The noise resulting from observing the point cloud from the HMD could be
analyzed by using Eq. 3, where all three values are stable measurements.
$M_{T}^{H}$ and $M_{R^{{}^{\prime}}}^{T^{{}^{\prime}}}$ are local measurements
on the Unity side, while $M_{C}^{Z}$ is measured on the controller PC and sent
by Rosbridge communication protocol through Ethernet to the Unity side. The
noise arises mostly from the last one due to the possible instability of
Rosbridge communication and the network.

The noise resulting from observing the mesh from the HMD can be analyzed by
Eq. 8. Compare it with Eq. 3. Here, $M_{S}^{W^{{}^{\prime}}}$ is a static
measurement on the Unity side, $M_{W}^{Z}$ is the ZED odometry measurement
sent through network but not by Rosbridge. The noise resulting from observing
the mesh could be larger than observing the point cloud due to the usage of
the ZED odometry.

$\displaystyle M_{S}^{H^{{}^{\prime}}}$
$\displaystyle=M_{W^{{}^{\prime}}}^{H^{{}^{\prime}}}\cdot
M_{S}^{W^{{}^{\prime}}}$ (8) $\displaystyle=M_{T}^{H}\cdot
M_{R^{{}^{\prime}}}^{T^{{}^{\prime}}}\cdot M_{Z}^{R}\cdot M_{W}^{Z}\cdot
M_{S}^{W^{{}^{\prime}}}$

In order to reduce the dizziness of the operator caused by the noise, we apply
a low-pass filter to the virtual tracking space frame.

In Fig. 7, we plot the comparison between the measurement before and after
applying the filter using different filter rates. We observe that the high
frequency component is removed and when we decrease the rate, the curve
becomes smoother, while the lag increases. In our experiment, we use a filter
rate of 0.2, such that the latency caused by the low-pass filter is approx. 60
ms. In the future, we will use a filter without delay, such as the
complementary filter [20], as the performance is more suitable for VR.

Figure 8: Common latency between the motion of operator’s and robot’s head:
approx. 0.5 s. Figure 9: Latency when the network was unstable: approx. 2 s.
Figure 10: Range of motion measurement

##  IV Experiment

Figure 11: Three solutions were compared during the experiment. In the first,
second and last columns, we show the image displayed in the HMD for the three
different solutions. For the point cloud with mesh (last column, first row),
the blue grid shows the user scanned area while the mesh is under
construction. In the second and third rows, we marked the real-time point
cloud by a red dot line. In the fourth column, from top to down, the displayed
images correspond to different operator’s motions. In cases of RGB and point
cloud, the operator turned to the left from static forward status and then
waited a bit for the real-time visual feedback. While in case of the point
cloud with mesh, the operator kept turning. The third column shows the robot’s
head motion, and due to the lag, the robot’ head motion does not change in the
second row, although the operator had turned his head.

###  IV-A Latency Measurement

We measured the main latency in the system between the motion of operator’s
and robot’s head. We could observe these two motions in Unity3D which is the
software where our virtual space is built. We ask the operator to turn the
head from left to right (approx. -75 deg to 75 deg). In Fig. 8, usually when
network is stable, we could see the latency is about 0.5 s. However, the
latency could increase to 2 s as depicted in Fig. 9 when the network became
unstable.

###  IV-B Range of Motion Measurement

One advantage of our system is that it is able to compensate the blank area
caused by the mismatch between the range of motions of human’s and robot’s
heads. The motion of both ZED and HMD are shown in Fig. 10. As expected, after
the operator approached the maximum angle of head motion, there were 20 deg of
gap between the human’s head and robot’s head in a static situation. In case
of the stereo RGB fixed solution, the operator would lose this information of
the environment. In case of our solution, the operator could see the pre-built
mesh. The qualitative result is shown in the next section.

###  IV-C Qualitative Evaluation

We compared our proposed solution with a common stereo RGB fixed solution
which is adopted by most of teams in the XPRIZE competition such as [22] [23]
as qualitative evaluation. Since our proposal mainly include two parts: one is
the decoupled representation in a virtual space, another one is to overlap the
point cloud with mesh, we evaluate this two parts separately. Seven
participants (males between their 20s and 40s) were asked to finish one small
task three times. The task was to tele-operate the robot to walk straight
forward or backward freely and, at the same time, they could turn the head
freely to observe the environment as they wanted. For each trial, different
visual feedback solutions were provided: stereo fixed viewpoint with RGB image
only, decoupled viewpoint with point cloud only or decoupled viewpoint with
point cloud and mesh, which correspond to the three solutions that we
explained in Section II. The experiment scene is shown in Fig. 11. For the
second and third solutions, the participants were able to calibrate the
viewpoint at any time during the operation. For the third solution, the
participants were asked to build the mesh right after we started the system,
and they could scan the area as much as they wanted. After building the mesh,
the point cloud always overlapped the constructed mesh. In order to reduce the
burden to the network, we set the point cloud resolution as HD720; however, we
also include the performance of point cloud HD1080 in a demo video
444https://www.youtube.com/watch?v=Jdiaosp_qH8.

The comparison snapshots of the three solutions are shown in Fig. 11. From the
solution of point cloud and point cloud with mesh, we could observe that when
the operator turned his head, the real time point cloud could track the center
of the HMD display with a delay. In the solution of point cloud with mesh, we
could see the fusion between the point cloud and the constructed mesh, as well
as that the mismatch between the ZED’s and HMD’s FOV is complemented by the
pre-built mesh. One interesting thing we found is that since the reconstructed
mesh could complement the blank area, the operators usually did not wait for
the real-time point cloud to come back to the center of the HMD’s FOV, but
they would keep intuitively moving their perspective, which significantly
increased the interaction efficiency with robot. This fact is represented in
Fig. 11: after turning the head a small angle, the operator kept turning his
head to a larger degree until he saw the blank area which was not covered by
mesh (also beyond the motion range of the robot’s head) as the last figure
shows in the last column.

##  V Conclusion and future work

In this work, we proposed a balanced-immersive tele-visualization solution
with decoupled viewpoint control and complementary visual feedback for
humanoid robot teleoperation. The proposed solution mainly contains two core
ideas. The first idea is to complement the real-time point cloud with a
constructed mesh, aligning them by applying visual-inertial odometry while
distinguishing them by changing the color of the mesh, resulting in a balanced
fusion effect. The second idea is to realize the decoupled movement between
robot’s and operator’s viewpoints in a virtual space to reduce the visual
latency. We achieved a balanced immersion by combining both ideas. We
evaluated both ideas by comparing against a standard stereo RGB fixed view
solution and verified the effectiveness of our proposal regarding the
provision of instant visual feedback, bigger FOV and bigger range of view (due
to a bigger range of human head motion). We also identified several
limitations that could be improved in the future. One limitation comes from
the quality of the reconstructed mesh and the odometry precision leading to a
misalignment between point cloud and mesh, which can be solved by a
continuously improved higher precision SLAM method, available nowadays. Also,
the real-time part should always be given a higher visual priority than the
constructed mesh. This could be achieved by using other rendering methods.
Another future work will be evaluate the proposed system with a complete user
study evaluated by questionnaire. Our proposal is most suitable for a humanoid
platform, but potentially it could also be applied to other robotic platforms,
especially those using human head motion to control a robot’s head with a
mounted camera.

## References

  * [1] 2022 XPRIZE Foundation, “Ana avatar xprize,” https://www.xprize.org/prizes/avatar, Last accessed on 2022-07-15.
  * [2] J. Zhao, R. S. Allison, M. Vinnikov, and S. Jennings, “The effects of visual and control latency on piloting a quadcopter using a head-mounted display,” in _2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)_. IEEE, 2018, pp. 2972–2979.
  * [3] A. Hornung, K. M. Wurm, and M. Bennewitz, “Humanoid robot localization in complex indoor environments,” in _2010 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2010, pp. 1690–1695.
  * [4] M. Tsuru, A. Escande, A. Tanguy, K. Chappellet, and K. Harada, “Online object searching by a humanoid robot in an unknown environment,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 2862–2869, 2021.
  * [5] A. Tanguy, P. Gergondet, A. I. Comport, and A. Kheddar, “Closed-loop RGB-D SLAM multi-contact control for humanoid robots,” _2016 IEEE/SICE International Symposium on System Integration (SII)_ , pp. 51–57, 2016.
  * [6] A. Kheddar, S. Caron, P. Gergondet, A. Comport, A. Tanguy, C. Ott, B. Henze, G. Mesesan, J. Englsberger, M. A. Roa, P.-B. Wieber, F. Chaumette, F. Spindler, G. Oriolo, L. Lanari, A. Escande, K. Chappellet, F. Kanehiro, and P. Rabaté, “Humanoid robots in aircraft manufacturing: The airbus use cases,” _IEEE Robotics Automation Magazine_ , vol. 26, no. 4, pp. 30–45, 2019.
  * [7] J. Nakanishi, S. Itadera, T. Aoyama, and Y. Hasegawa, “Towards the development of an intuitive teleoperation system for human support robot using a VR device,” _Advanced Robotics_ , vol. 34, no. 19, pp. 1239–1253, 2020.
  * [8] C. Wang, X. Chen, Z. Yu, Y. Dong, R. Zhang, and Q. Huang, “Intuitive and versatile full-body teleoperation of a humanoid robot,” in _2021 IEEE International Conference on Advanced Robotics and Its Social Impacts (ARSO)_ , 2021, pp. 176–181.
  * [9] M. Schwarz, C. Lenz, A. Rochow, M. Schreiber, and S. Behnke, “NimbRo avatar: Interactive immersive telepresence with force-feedback telemanipulation,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021, pp. 5312–5319.
  * [10] M. Schwarz and S. Behnke, “Low-latency immersive 6D televisualization with spherical rendering,” in _2020 IEEE-RAS 20th International Conference on Humanoid Robots (Humanoids)_ , 2021, pp. 320–325.
  * [11] P. Stotko, S. Krumpen, M. Schwarz, C. Lenz, S. Behnke, R. Klein, and M. Weinmann, “A VR system for immersive teleoperation and live exploration with a mobile robot,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2019, pp. 3630–3637.
  * [12] T. Rodehutskors, M. Schwarz, and S. Behnke, “Intuitive bimanual telemanipulation under communication restrictions by immersive 3D visualization and motion tracking,” in _2015 IEEE-RAS 15th International Conference on Humanoid Robots (Humanoids)_ , 2015, pp. 276–283.
  * [13] A. Naceri, D. Mazzanti, J. Bimbo, D. Prattichizzo, D. G. Caldwell, L. S. Mattos, and N. Deshpande, “Towards a virtual reality interface for remote robotic teleoperation,” in _2019 19th International Conference on Advanced Robotics (ICAR)_ , 2019, pp. 284–289.
  * [14] Y.-T. Lin, Y.-C. Liao, S.-Y. Teng, Y.-J. Chung, L. Chan, and B.-Y. Chen, “Outside-in: Visualizing out-of-sight regions-of-interest in a 360 video using spatial picture-in-picture previews,” in _Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology_ , 2017, pp. 255–265.
  * [15] D. Whitney, E. Rosen, E. Phillips, G. Konidaris, and S. Tellex, “Comparing robot grasping teleoperation across desktop and virtual reality with ros reality,” in _Robotics Research_. Springer, 2020, pp. 335–350.
  * [16] D. Wei, B. Huang, and Q. Li, “Multi-view merging for robot teleoperation with virtual reality,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 4, pp. 8537–8544, 2021.
  * [17] D. Sun, A. Kiselev, Q. Liao, T. Stoyanov, and A. Loutfi, “A new mixed-reality-based teleoperation system for telepresence and maneuverability enhancement,” _IEEE Transactions on Human-Machine Systems_ , vol. 50, no. 1, pp. 55–67, 2020.
  * [18] A. Kheddar, “Teleoperation based on the hidden robot concept,” _IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans_ , vol. 31, no. 1, pp. 1–13, 2001.
  * [19] R. Cisneros-Limó, M. Benallegue, K. Kaneko, H. Kaminaga, G. Caron, A. Tanguy, R. Singh, L. Sun, A. Dallard, C. Fournier, M. Tsuru, C. Yang, Y. Osawa, G. Lorthioir, F. Kanehiro, and A. Kheddar, “Team JANUS humanoid avatar: A cybernetic avatar to embody human telepresence,” in _RSS 2022 Workshop on ”Towards Robot Avatars: Perspectives on the ANA Avatar XPRIZE Competition”_ , 2022.
  * [20] K. Kaneko, F. Kanehiro, M. Morisawa, K. Miura, S. Nakaoka, and S. Kajita, “Cybernetic human HRP-4C,” in _2009 9th IEEE-RAS International Conference on Humanoid Robots_ , 2009, pp. 7–14.
  * [21] A. Alapetite, Z. Wang, J. P. Hansen, M. Zajaczkowski, and M. Patalan, “Real-world comparison of visual odometry methods,” 2020.
  * [22] B. Park, J. Jung, J. Sim, S. Kim, J. Ahn, D. Lim, D. Kim, M. Kim, S. Park, E. Sung, H. Lee, G. Park, J. Cha, J. Shin, and J. Park., “Team SNU’s avatar system for teleoperation using humanoid robot: ANA Avatar XPRIZE competition,” in _RSS 2022 Workshop on ”Towards Robot Avatars: Perspectives on the ANA Avatar XPRIZE Competition”_ , 2022.
  * [23] J. M. C. Marques, N. Patrick, Y. Zhu, N. Malhotra, and K. Hauser, “Commodity telepresence with the AvaTRINA Nursebot in the ANA Avatar XPRIZE semifinals,” in _RSS 2022 Workshop on ”Towards Robot Avatars: Perspectives on the ANA Avatar XPRIZE Competition”_ , 2022.


Criminal Networks Analysis in Missing Data scenarios through Graph Distances

Annamaria Ficara1,3, Lucia Cavallaro2*, Francesco Curreri1,3, Giacomo
Fiumara3‡, Pasquale De Meo4‡, Ovidiu Bagdasar2‡, Wei Song5‡, Antonio Liotta6‡

1 DMI Department, University of Palermo, Palermo, Italy

2 School of Computing and Engineering, University of Derby, UK

3 MIFT Department, University of Messina, Messina, Italy

4 DICAM Department, University of Messina, Messina, Italy

5 College of Information Technology, Shanghai Ocean University, Shanghai,
China

6 Faculty of Computer Science, University of Bozen-Bolzano, Bozen-Bolzano,
Italy

These authors contributed equally to this work.

‡These authors also contributed equally to this work.

¶Membership list can be found in the Acknowledgments section.

*<EMAIL_ADDRESS>
## Abstract

Data collected in criminal investigations may suffer from:  (i)
incompleteness, due to the covert nature of criminal organisations;  (ii)
incorrectness, caused by either unintentional data collection errors and
intentional deception by criminals;  (iii) inconsistency, when the same
information is collected into law enforcement databases multiple times, or in
different formats.  In this paper we analyse nine real criminal networks of
different nature (i.e., Mafia networks, criminal street gangs and terrorist
organizations) in order to quantify the impact of incomplete data and to
determine which network type is most affected by it. The networks are firstly
pruned following two specific methods:  (i) random edges removal, simulating
the scenario in which the Law Enforcement Agencies (LEAs) fail to intercept
some calls, or to spot sporadic meetings among suspects;  (ii) nodes removal,
that catches the hypothesis in which some suspects cannot be intercepted or
investigated.  Finally we compute spectral (i.e., Adjacency, Laplacian and
Normalised Laplacian Spectral Distances) and matrix (i.e., Root Euclidean
Distance) distances between the complete and pruned networks, which we compare
using statistical analysis. Our investigation identified two main features:
first, the overall understanding of the criminal networks remains high even
with incomplete data on criminal interactions (i.e., 10% removed edges);
second, removing even a small fraction of suspects not investigated (i.e., 2%
removed nodes) may lead to significant misinterpretation of the overall
network.

## Introduction

Criminal organizations are groups operating outside the boundaries of the law,
which make illegal profit from providing illicit goods and services in public
demand and whose achievements come at the cost of other people, groups or
societies [1]. Organised crime is referred to different terms including gangs
[2], crews [3], firms [4], syndacates [4], or Mafia [5]. In particular,
Gambetta [6] defines Mafia as a “territorially based criminal organization
that attempts to govern territories and markets” and he identifies the one
located in Sicily as the original Mafia.

Whatever term is used to call the organised crime, this involves relational
traits. For this reason, scholars and practitioners are increasingly adopting
a Network Science Analysis (SNA) perspective to explore criminal phenomena
[7]. SNA algorithms can produce relevant measurements and parameters
describing the role and importance of individuals within criminal
organizations, and SNA has been used to identify leaders within a criminal
organization [8] and to construct crime prevention systems [9].

Over the last decades, SNA has been employed increasingly by Law Enforcement
Agencies (LEAs). This increasing interest from law enforcement is due to SNA’s
ability to identify mechanisms that are not easily discovered at first glance
[10].

SNA relies on real datasets used as sources which allow to build networks that
are then examined [11, 12, 13, 14, 15, 9, 16, 17]. However, the collection of
complete network data describing the structure and activities of a criminal
organization is difficult to obtain.

In a criminal investigation, the individuals subjected to LEAs enquiries may
attempt to shield sensible information. Investigators then have to rely on
alternative methods and exercise special investigative powers allowing them to
gather evidence covertly from sources including phone taps, surveillance,
archives, informants, interrogations to witnesses and suspects, infiltration
in criminal groups. Despite significant advantages, such sources may also have
a number of drawbacks.

Also, while some individuals providing information during investigations are
reliable, others might attempt to deceive the investigations with the aim to
protect themselves, their associates, or to achieve a specific goal. For
instance, if actors are aware of being phone-tapped, they are more likely to
avoid to discuss of self-incriminating evidence. While the transcripts of
discussions between unsuspecting actors can be considered more reliable, the
information collected from taps must still be verified against other official
records related to the case. This is required since conversations among
criminals often involve lies or codes concealing the true nature of the
message [18]. Moreover, if police misses surveillance targets, central actors
may not appear with their actual role in the data, simply because their phones
end up not being tapped [5].

While the police seeks to validate the content of phone-taps, the offenders
may also check themselves whether the information received from the police
during conversations is accurate. Longer investigations and surveillance tend
to eventually expose subtle lies. On the other side, datasets may change with
time, due to the variable status of suspects, or to new information being
collected. The problem of actors lying is extended to data collected through
questionnaires or interviews as well. Information collected from
interrogations may not be reliable, with the risk of interviewees downplaying
or amplifying their real role, or simply not being representative of the
broader group.

Police decisions may even impact the design of an investigation. LEAs normally
start with some suspected individuals, and then expand their reach by adding
further actors. Not all the individuals linked to the central actors are
automatically added, as the investigation of all active criminal groups is not
possibile due to limited resources. Prosecution services must prioritise the
groups on which evidence gathering is easier. Hence, groups operating under
the police radar may be absent from the data collected, and this may generate
heavily distorted inferences about the network structure [19].

Incompleteness and incorrectness of criminal network data is then inevitable.
This is due to investigators dealing with data of different quality and
because in SNA there is currently no standard method to account for such
degrees of reliability.

LEAs often have to process lots of data, most of which is of little value.
When large volumes of raw data are collected from multiple sources, the risk
of inconsistency is also higher. The identification of relevant and important
information from datasets where this is mixed with irrelevant or unreliable
information, is referred to as the signal and noise problem. Analytical
techniques used in intelligence should then be able to cope with large
datasets and to effectively distinguish the signal from noise.

In summary, the data collected in criminal investigations regularly suffers
from:

  * •

Incompleteness, caused by the covert nature of criminal networks;

  * •

Incorrectness, caused by either unintentional errors in data collection or
intentional deception by criminals;

  * •

Inconsistency, when records of the same actors are collected into LEA
databases multiple times and not necessarily in a consistent way. This way,
the same actor may show up in a network as different individuals.

Criminal networks are very dynamic, as they constantly change over time. New
data or even different data collection methods are necessary to cover longer
time spans [20]. Another problem specific to SNA used for criminal networks
lies in data processing. Often, actors are represented by nodes, and their
associations or interactions by links. However, there is no SNA standard
methodology for transforming the raw data and the process depends on the
subjective judgement of the analyst. This may have to decide whom to include
or exclude from the network, when boundaries are ambiguous [20]. Also, data
conversion is often a labor-intensive and time-consuming process.

An interesting application of SNA is to compare networks by finding and
quantifying similarities and differences [21, 22, 23]. Network comparison
requires measures for the distance between graphs, which can be done using
multiple metrics. That is a non-trivial task which involves a set of features
that are often sensitive to the specific application domain. A few literature
reviews on the most common graph comparison metrics are available [24, 25, 26,
27]. In [28], such distance measures were exploited to quantify how much
artificial, but also realistic models can represent real criminal networks.

In this work, we adopt a SNA approach to assess the impact of incomplete data
in a criminal network. Our aim is to quantify how much information on the
criminal network is required, so that the accuracy of investigations is not
affected. Specifically, we analyse nine real criminal networks of different
nature, which are the result of different investigative operations over Mafia
networks, criminal street gangs and terrorist organizations. To quantify the
impact of incomplete data and to determine which network suffers mostly from
it, we adopt the following strategies:

  1. 1.

We pruned input networks by means of two specific methods, namely: random
edges removal and random nodes removal, which reflect the most common
scenarios of missing data arising in real investigations.

  2. 2.

We calculated the distance between the original (defined as complete as a
reference) network and its pruned version.

## Materials and methods

This section presents basic graph theory definitions and the distance metrics
used for comparing two graphs. We also describe the datasets used in our
experimental analysis, as well as the protocol followed to run our analysis.

### Background

#### Graph properties

A network (or graph) $G=\langle N,E\rangle$ consists of two finite sets $N$
and $E$ [29]. The set $N=\\{1,\dots,n\\}$ contains the nodes (or vertices,
actors), and $n$ is the size of the network, while the set $E\subseteq N\times
N$ contains the edges (or links, ties) between the nodes.

A network is called undirected if all its edges are bidirectional. If the
edges are defined by ordered pairs of nodes, then the network is called
directed. If an edge $(i,j)$ with $i,j\in N$ is weighted, then a positive
numerical weight $w_{ij}$ is associated; the unweighted edges have their
weight set to the default value $w_{ij}=1$.

Given an undirected network $G$, two nodes $i,j\in N$ are connected if there
is a path from $i$ to $j$: here a path $p$ is defined as a sequence of nodes
$i_{0},i_{1},\ldots,i_{k}$ such that each pair of consecutive nodes is
connected through an edge. The number of edges in a path $p$ starting at node
$i$ and ending at node $j$ is called path length. While there may be several
paths from the node $i$ to the node $j$, we are usually interested in the
shortest paths (i.e., those with the least number of edges), whose length
defines the distance $d_{ij}$ between $i$ and $j$. Of course, in undirected
networks we have $d_{ij}=d_{ji}$.

A graph $G$ is called connected if every pair of nodes in $G$ is connected,
and disconnected otherwise. If a network is disconnected, it fragments into a
collection of connected subnetworks, each of them called components.

Based on the number of edges $m$, a graph is called dense if $m$ is of the
same order of magnitude as $n^{2}$, or sparse if $m$ is of the same order of
magnitude as $n$. The density $\delta$ of an undirected graph is defined as

$\displaystyle\delta=\frac{2\lvert E\rvert}{\lvert V\rvert(\lvert
V\rvert-1)}=\frac{2m}{n(n-1)},$ (1)

that is the total number of edges over the maximum possible number of edges.

The degree $k_{i}$ of the node $i$ represents the number of adjacent edges,
while the degree distribution $p_{k}$ provides the probability that a randomly
selected node in the graph has degree $k$. Given a graph of $n$ nodes, $p_{k}$
is the normalised histogram given by

$\displaystyle p_{k}=\frac{n_{k}}{n},$ (2)

where $n_{k}$ is the number nodes of degree $k$.

The degree $k_{i}$ allows to compute the clustering coefficient $C_{i}$ of a
node $i$ [30], which captures the degree to which the neighbors of the node
$i$ link to each other, given by

$\displaystyle C_{i}=\frac{2L_{i}}{k_{i}(k_{i}-1)},$ (3)

where $L_{i}$ represents the number of links between the $K_{i}$ neighbors of
node $i$. The average of $C_{i}$ over all nodes defined the average clustering
coefficient $\langle C_{i}\rangle$, measuring the probability that two
neighbors of a randomly selected node link to each other.

Given a pair of graphs, say $G_{1}$ and $G_{2}$, we are often interested in
defining a measure of similarity (or, equivalently, distance) between them. In
what follows we review some methods one can use to compute the distance of two
graphs.

#### Spectral distances

Spectral distances allow to measure the structural similarity between two
graphs starting from their spectra. The spectrum of a graph is widely used to
characterise its properties and to extract information from its structure.

The most common matrix representations of a graph are the adjacency matrix
$A$, the Laplacian matrix $L$ and the normalised Laplacian $\mathcal{L}$.

Given a graph $G$ with $n$ nodes, its adjacency matrix $A$ is an $n\times n$
square matrix denoted by $A=(a_{ij})$, with $1\leq i,j\leq n$, where
$a_{ij}=1$ if there exists an edge joining nodes $i$ and $j$, and $a_{ij}=0$
otherwise.

For undirected graphs the adjacency matrix is symmetric, i.e.,
$a_{ij}$=$a_{ji}$.

The degree matrix $D$ is a diagonal matrix where $D_{ii}=k_{i}$ and $D_{ij}=0$
for $i\neq j$.

$\displaystyle{D_{ij}}=\begin{cases}k_{i}&\text{if }i=j\\\
0&\text{otherwise}\end{cases}$ (4)

The adjacency matrix and the degree matrix are used to compute the
combinatorial Laplacian matrix $L$, which is an $n\times n$ symmetric matrix
defined as

$\displaystyle L=D-A.$ (5)

The diagonal elements $L_{ii}$ of $L$ are then equal to the degree $k_{i}$ of
the node $i$, while off-diagonal elements $L_{ij}$ are $-1$ if the node $i$ is
adjacent to $j$ and 0 otherwise. A normalised version of the Laplacian matrix,
denoted as $\mathcal{L}$, is defined as

$\displaystyle\mathcal{L}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}},$ (6)

where the diagonal matrix $D^{-\frac{1}{2}}$ is given by

$\displaystyle{D^{-\frac{1}{2}}_{i,i}}=\begin{cases}\frac{1}{\sqrt{k_{i}}}&\text{if
}k_{i}\neq 0\\\ 0&\text{otherwise.}\end{cases}$ (7)

The spectrum of a graph consists of the set of the sorted eigenvalues of one
of its representation matrices. The sequence of eigenvalues may be ascending
or descending depending on the chosen matrix. The spectra derived from each
representation matrix may reveal different properties of the graph. The
largest eigenvalue absolute value in a graph is called the spectral radius of
the graph. If $\lambda^{A}_{k}$ is the $k^{th}$ eigenvalue of the adjacency
matrix $A$, then the spectrum is given by the descending sequence

$\displaystyle\lambda^{A}_{1}\geq\lambda^{A}_{2}\geq\dots\geq\lambda^{A}_{n}.$
(8)

If $\lambda^{L}_{k}$ is the $k^{th}$ eigenvalue of the Laplacian matrix $L$,
such eigenvalues are considered in ascending order so that

$\displaystyle
0=\lambda^{L}_{1}\leq\lambda^{L}_{2}\leq\dots\leq\lambda^{L}_{n}.$ (9)

The second smallest eigenvalue of the Laplacian matrix of a graph is called
its algebraic connectivity. Similarly, if we denote the $k^{th}$ eigenvalue of
the normalised Laplacian matrix $\mathcal{L}$ as $\lambda^{\mathcal{L}}_{k}$,
then its spectrum is given by

$\displaystyle
0=\lambda^{\mathcal{L}}_{1}\leq\lambda^{\mathcal{L}}_{2}\leq\dots\leq\lambda^{\mathcal{L}}_{n}.$
(10)

The spectral distance between two graphs is the euclidean distance between
their spectra [31]. Given two graphs $G$ and $G^{\prime}$ of size $n$, with
their spectra respectively given by the set of eigenvalues $\lambda_{i}$ and
$\lambda_{i^{\prime}}$, their spectral distance, according to the chosen
representation matrix, is computed as follows by the formula

$\displaystyle{d(G,G^{\prime})}=\sqrt{\sum_{i=0}^{n}(\lambda_{i}-\lambda_{i^{\prime}})^{2}}.$
(11)

Based on the chosen representation matrix and consequently its spectrum, the
most common spectral distances are the adjacency spectral distance $d_{A}$,
the Laplacian spectral distance $d_{L}$ and the normalised Laplacian spectral
distance $d_{\mathcal{L}}$.

If the two spectra are of different sizes, the smaller graph is brought to the
same cardinality of the other by adding zero values to its spectrum. In such
case, only the first $k\ll n$ eigenvalues are compared. Given the definitions
of spectra of the different matrices, the adjacency spectral distance $d_{A}$
compares the largest $k$ eigenvalues, while $d_{L}$ and $d_{\mathcal{L}}$
compare the smallest $k$ eigenvalues. This determines the scale at which the
graphs are studied, since comparing the higher eigenvalues allows to focus
more on global features, while the other two allow to focus more on local
features.

#### Matrix distances

Another class of distances between graphs is the matrix distance [32]. A
matrix of pairwise distances $d_{ij}$ between nodes on the single graph is
constructed for each as

$\displaystyle M_{ij}=d_{ij}.$ (12)

While most common distance $d$ is the shortest path distance, other measures
can also be used, such as the effective graph resistance or variations on
random-walk distances. Such matrices provide a signature of the graph
characteristics and carry important structural information. Matrices $M$ are
then compared using some norm or distance.

Given two graphs $G$ and $G^{\prime}$, with $M$ and $M^{\prime}$ being their
respective matrices of pairwise distances, the matrix distance between the $G$
and $G^{\prime}$ is introduced as:

$\displaystyle d(G,G^{\prime})=\|M-M^{\prime}\|,$ (13)

where $\|.\|$ is a norm to be chosen. If the matrix used is the adjacency
matrix $A$, the resulting distance is called edit distance.

The similarity measure used in this work is called DeltaCon [33]. It is based
on the root euclidean distance $\mathrm{d_{rootED}}$, also called Matsusita
difference, between matrices $S$ created from the fast belief propagation
method of measuring node affinities.

The DeltaCon similarity is defined as

$\displaystyle
sim_{DC}(G,G^{\prime})=\frac{1}{1+\mathrm{d_{rootED}}(G,G^{\prime}),}$ (14)

where $\mathrm{d_{rootED}}(G,G^{\prime})$ is defined as

$\displaystyle\mathrm{d_{rootED}}(G,G^{\prime})=\sqrt{\sum_{i,j}(\sqrt{S_{i,j}}-\sqrt{S^{\prime}_{i,j})}^{2}}.$
(15)

When used instead of the Euclidean distance,
$\mathrm{d_{rootED}}(G,G^{\prime})$ may even detect small changes in the
graphs. The fast belief propagation matrix $S$ is defined as

$\displaystyle S=[I+\varepsilon^{2}D-\varepsilon A]^{-1},$ (16)

where $\varepsilon=1/(1+max_{i}D_{ii})$ and it is assumed to be
$\varepsilon\ll 1$, so that S can be rewritten in a matrix power series as:

$\displaystyle S\approx I+\varepsilon A+\varepsilon^{2}(A^{2}-D)+\dots.$ (17)

Fast belief propagation is a fast algorithm and is designed to perceive both
global and local structures of the graph.

### Criminal networks data sources

Our analysis focuses on nine real criminal networks of different nature (see
Table 1). The first six networks relate to three distinct Mafia operations,
while the other three are linked to street gangs and terrorist organizations.

Table 1:  Criminal networks characterization. Investigation | Network | Source
---|---|---
| Name | Nodes | Edges |
Montagna Operation (Sicilian Mafia) 2003-2007 |  MN PC | Suspects |  Physical Surveillance Audio Surveillance | [15, 9, 16, 28, 34]
Infinito Operation (Lombardian ’Ndrangheta) 2007-2009 | SN | Suspects |  Physical and Audio Surveillance | [35, 36, 37, 38, 39]
Oversize Operation (Calabrian ’Ndrangheta) 2000-2009 |  WR AW JU | Suspects |  Audio Surveillance Physical Surveillance Audio Surveillance | [40, 41]
Swedish Police Operation (Stockholm Street Gangs) 2000-2009 | SV | Gang members | Physical Surveillance | [12, 42]
Caviar Project (Montreal Drug Traffickers) 1994-1996 | CV | Criminals | Audio Surveillance | [5]
Abu Sayyaf Group (Philippines Kidnappers) 1991-2011 | PK | Kidnappers | Attacks locations | [43]

The Montagna Operation was an investigation concluded in 2007 by the Public
Prosecutor’s Office of Messina (Sicily) focused on the Sicilian Mafia groups
known as Mistretta and Batanesi clans. Between 2003 and 2007 these families
infiltrated several economic activities including public works in the area,
through a cartel of entrepreneurs close to the Sicilian Mafia. The main data
source is the pre-trial detention order issued by the Preliminary
Investigation Judge of Messina on March 14, 2007.

The order concerned a total of 52 suspects, all charged with the crime of
participation in a Mafia clan as well as other crimes such as theft, extortion
or damaging followed by arson. From the analysis of this legal document we
built two weighted and undirected graphs: the Meeting network (MN) with 101
nodes and 256 edges, and the Phone Calls (PC) network with 100 nodes and 124
edges (see Table 2). In both networks, nodes are suspected criminals and edges
represent meetings (MN), or recorded phone calls (PC). These original datasets
have been already studied in some of our previous works [15, 9, 16, 28, 17]
and they are available on Zenodo [34].

The Infinito Operation was a large law enforcement operation against
’Ndrangheta groups (i.e., groups of the Calabrian Mafia) and Milan cosche
(i.e., crime families or clans) concluded by the courts of Milan and Reggio
Calabria, Italian cities situated in Northern and Southern Italy,
respectively. The investigation started 2003 is still in progress. On July 5,
2010, the Preliminary Investigations Judge of Milan issued a pre-trial
detention order for 154 people, with charges ranging from mafia-style
association to arms trafficking, extortion and intimidation for the awarding
of contracts or electoral preferences. The dataset was extracted from this
judicial act and is available as a $2$-mode matrix on the UCINET [44] website
(Link: https://sites.google.com/site/ucinetsoftware/datasets/covert-
networks/ndranghetamafia2). The Infinito Operation dataset was investigated by
Calderoni and his co-authors in several works [35, 36, 37, 38, 39]. From the
original $2$-mode matrix, we constructed the weighted and undirected graph
Summits Network (SN) with 156 nodes and 1619 edges (Table 2). Nodes are
suspected members of the ’Ndrangheta criminal organization. Edges are summits
(i.e., meetings whose purpose is to make important decisions and/or
affiliations, but also to solve internal problems and to establish roles and
powers) taking place between 2007 and 2009. This network describes how many
summits in common any two suspects have. Attendance at summits was registered
by police authorities through wiretapping and observations during this
operation.

The Oversize Operation is an investigation lasting from 2000 to 2006, which
targeted more than 50 suspects of the Calabrian ’Ndrangheta involved in
international drug trafficking, homicides, and robberies. The trial led to the
conviction of the main suspects from 5 to 22 years of imprisonment between
2007-2009. Berlusconi et al. [40] studied three unweighted and undirected
networks extracted from three judicial documents corresponding to three
different stages of the criminal proceedings (Table 2): wiretap records (WR),
arrest warrant (AW), and judgment (JU). Each of these networks has 182 nodes
which corresponding to the individuals involved in illicit activities. The WR
network has 247 edges which represent the wiretap conversations transcribed by
the police and considered relevant at first glance. The AW network contains
189 edges which are meetings emerging from the physical surveillance. The JU
network has 113 edges which are wiretap conversations emerging from the trial
and several other sources of evidence, including wiretapping and audio
surveillance. These datasets are available as three $1$-mode matrices on
Figshare [41].

Table 2:  Mafia networks properties. Network | MN | PC | SN | WR | AW | JU
---|---|---|---|---|---|---
weights | weighted | weighted | weighted | unweighted | unweighted | unweighted
directionality | undirected | undirected | undirected | undirected | undirected | undirected
connectedness | false | false | false | false | false | false
n. of nodes $n$ | 101 | 100 | 156 | 182 | 182 | 182
n. of isolated nodes $n_{i}$ | 0 | 0 | 5 | 0 | 36 | 93
n. of edges $m$ | 256 | 124 | 1619 | 247 | 189 | 113
n. of components $\lvert cc\rvert$ | 5 | 5 | 6 | 3 | 38 | 96
max avg. path length $\langle d\rangle$ for $cc$ | 3.309 | 3.378 | 2.361 | 3.999 | 4.426 | 3.722
max shortest path length $d$ | 7 | 7 | 5 | 8 | 9 | 7
density $\delta$ | 0.051 | 0.025 | 0.134 | 0.015 | 0.011 | 0.007
avg. degree $\langle k\rangle$ | 5.07 | 2.48 | 20.76 | 2.71 | 2.08 | 1.24
max degree $k$ | 24 | 25 | 75 | 32 | 29 | 13
avg. clust. coeff. $\langle C\rangle$ | 0.656 | 0.105 | 0.795 | 0.149 | 0.122 | 0.059

The Stockholm street gangs dataset was extracted from the National Swedish
Police Intelligence (NSPI), which collects and registers the information from
different kinds of intelligence sources to identify gang membership in Sweden.
The organization investigated here is a Stockholm-based street gang localised
in southern parts of Stockholm County, consisting of marginalised suburbs of
the capital. All gang members are male with high levels of violence, thefts,
robbery and drug-related crimes. Rostami and Mondani [12] constructed the
Surveillance (SV) network (Table 3). It contains data from the General
Surveillance Register (GSR) which covers the period 1995–2010 and aims to
facilitate access to the personal information revealed in law enforcement
activities needed in police operations. SV is a weighted network with 234
nodes that are gang members. Some of them were no longer part of the gang in
the period covered by the data and have been included as isolated nodes. The
link weight counts the number of occurrence of a given edge. This dataset is
available on Figshare [42].

Project Caviar [5] was a unique investigation against hashish and cocaine
importers operating out of Montreal, Canada. The network was targeted between
1994 and 1996 by a tandem investigation uniting the Montreal Police, the Royal
Canadian Mounted Police, and other national and regional law-enforcement
agencies from England, Spain, Italy, Brazil, Paraguay, and Colombia. In a
2-year period, 11 importation drug consignments were seized at different
moments and arrests only took place at the end of the investigation. The
principal data sources are the transcripts of electronically intercepted
telephone conversations between suspects submitted as evidence during the
trials of 22 individuals. Initially, 318 individuals were extracted because of
their appearence in the surveillance data. From this pool, 208 individuals
were not implicated in the trafficking operations. Most were simply named
during the many transcripts of conversations, but never detected. Others who
were detected had no clear participatory role within the network (e.g., family
members or legitimate entrepreneurs). The final Caviar (CV) network was
composed of 110 nodes. The $1$-mode matrix with weighted and directed edges is
available on the UCINET [44] website. (Link:
https://sites.google.com/site/ucinetsoftware/datasets/covert-networks/caviar).
From this matrix, we extracted an undirected and weighted network with 110
nodes which are criminals and 205 edges which represent the communications
exchanges between them (see Table 3). Weights are level of communication
activity.

Philippines Kidnappers data refer to the Abu Sayyaf Group (ASG) [43], a
violent non-state actor operating in the Southern Philippines. In particular,
this dataset is related to the Salast movement that has been founded by
Aburajak Janjalani, a native terrorist of the Southern Philippines in 1991.
ASG is active in kidnapping and other kinds of terrorist attacks. The
reconstructed $2$-mode matrix is available on UCINET [44] (Link:
https://sites.google.com/site/ucinetsoftware/datasets/covert-
networks/philippinekidnappings). From the $2$-mode matrix, we constructed a
weighted and undirected graph called Philippines Kidnappers (PK) (see Table
3). The PK network has 246 nodes and 2571 edges. Nodes are terrorist
kidnappers of the ASG. Edges are the terrorist events they have attended. This
network describes how many events in common any two kidnappers have.

Table 3:  Street gangs and terrorist networks properties. Network | SV | CV | PK
---|---|---|---
weights | weighted | weighted | weighted
directionality | undirected | undirected | undirected
connectedness | false | true | false
nr. of nodes $n$ | 234 | 110 | 246
nr. of isolated nodes $n_{i}$ | 12 | 0 | 16
nr. of edges $m$ | 315 | 205 | 2571
nr. of components $cc$ | 13 | 1 | 26
max avg. path length $\langle d\rangle$ for $cc$ | 3.534 | 2.655 | 3.034
max shortest path length $d$ | 6 | 5 | 9
density $\delta$ | 0.012 | 0.034 | 0.085
avg. degree $\langle k\rangle$ | 2.69 | 3.73 | 20.9
max degree $k$ | 34 | 60 | 78
avg. clustering coeff. $\langle C\rangle$ | 0.15 | 0.335 | 0.753

Useful information about Mafia, street gangs and terrorist networks is
provided in Tables 2 and 3, including edges weight and directionality,
connectedness, number of nodes including isolated ones, number of edges,
number of connected components, maximum average path length for each connected
component, maximum shortest path length, average degree, maximum degree and
the average clustering coefficient. The CV network seems to be the only fully
connected network (i.e., $\lvert cc\rvert=1$) and, for this reason, in all the
considered networks we chose to compute the average path length for the single
components and then to show the maximum value.

Fig 1: Degree Distributions. The degree distribution $p_{k}$ provides the
probability that a randomly selected node in each criminal network has degree
$k$. Same colors imply the networks belong to the same police investigation.

Then, we showed the degree distributions for each criminal network as a
normalised histogram (see Fig. 1). MN, PC, WR, AW, JU, SV and CV have similar
degree distributions in which most nodes have a relatively small degree $k$
with values around $0$, $1$ or $2$, while a few nodes have very large degree
$k$ and are connected to many other nodes. SN and PK are the only networks
having different degree distributions compared to other criminal networks, as
most of their nodes have large degree $k$. In particular, we note that most
nodes in PK are strongly connected and have a degree $k=57$.

### Design of Experiments

In this section we describe the technical details in the design of the
experiments conducted. To understand how much partial knowledge of a criminal
network may negatively affect the investigations, we have implemented several
tests.

Since we are trying to understand how much differences can be spotted based on
different types/amount of data missing, we set up the experiments by two main
strategies: random edges removal and nodes removal. The first case simulates
the scenario in which LEAs miss to intercept some calls or to spot sporadic
meetings among suspects (i.e., due to the delays in obtaining a warrant). By
nodes removal we mean that the selected nodes have been removed, jointly with
their incident edges, and afterwords they have been reinserted within the
networks as isolated nodes. Indeed, the second case catches the hypothesis in
which some suspects cannot be intercepted. For instance, if a criminal is
known to be a boss but there are not enough proofs to be investigated, then
that criminal can be identified as an isolated node with no incident edges.

Note that for a better comparison among the networks, the graphs have been all
considered as unweighted because both AW and JU are. Furthermore, all the
suspects showed as isolated nodes of the original network have been excluded.
In fact, our input parameter was the edge list of the graph, which does not
take into account nodes with no incident edges.

Algorithm 1 shows the pseudocode of our approach. In order to obtain the
subgraphs, we started from the previously described datasets; then, we
converted them into graphs (i.e., $G$) and, lastly, we pruned them (i.e.,
$G^{{}^{\prime}}$) according to a prefixed fraction $torem=10\%$. We opted for
the 10% because the criminal networks considered are small, as they have a
total number of nodes lower than 250. Afterwards, we have computed the
spectral and matrix distances $d(G,G^{{}^{\prime}})$ between the original and
the pruned graphs. Each edges removal process has been repeated a fixed number
of times ($nrep=100$) and the results obtained have been averaged. Thus, the
averaged distances values $\langle X\rangle$ and their standard deviations
$\sigma$ have been computed.

Algorithm 1 Pseudocode for computing the distances

1:Parameter configuration: $nrep$, $torem$, and $check$

2:Read the dataset and covert it as graph $G$

3:if $check=True$ then

4: Isolate $torem$ of nodes

5:else

6: Remove $torem$ of random edges

7:end if

8:Compute $S(G)$

9:Compute the matrices $A(G)$, $L(G)$, $\mathcal{L}(G)$

10:for $torem$ do

11: for $nrep$ do

12: Create a pruned graph $G^{{}^{\prime}}$ and compute
$S^{{}^{\prime}}(G^{{}^{\prime}})$

13: Compute $\mathrm{d_{rootED}}(G,G^{{}^{\prime}})$,
$d_{A}(G,G^{{}^{\prime}})$, $d_{L}(G,G^{{}^{\prime}})$, and
$d_{\mathcal{L}}(G,G^{{}^{\prime}})$

14: end for

15: Compute $\langle X\rangle$, $\sigma$ $\forall$ $d(G,G^{{}^{\prime}})$
$\in$ $nrep$

16:end for

## Results

Here we present the results obtained from the network pruning experiments. The
distance analysis between the real and the pruned networks is reported
starting from the random edges removal approach (Fig. 2), moving to the
analysis on the networks after node pruning (Fig. 3). The plots show the
distances between the original graphs and their pruned versions up to 10% of
edges ($F_{e}$) and nodes ($F_{n}$), respectively.

In both removal processes, $d_{A}$ displays a saturation effect that makes the
results difficult to be interpreted. Indeed, with a fraction of approximately
the 2% of removed elements (i.e, nodes/edges), the growth became flatter.
Hence, this distance is not effective for highlighting the effects of missing
data on criminal networks. Furthermore, from this metric it might seem that
the two pruned networks of PK and SN show a greater deviation from their
original counterparts, but this is due to the inner structure of this metric,
which is highly influenced by the nodes’ degree. In fact, the average degree
of PK an SN (see Tables 2 and 3) is significantly higher (i.e., $\langle
k\rangle\simeq 21$) than the other networks herein studied (i.e., $1<\langle
k\rangle<4$); moreover, their different topology is also evident from their
degree distribution (see Fig. 1). This is the reason why these networks seem
to have a more significant detachment effect than others; however, they too
suffer the saturation effect mentioned above as they grow. A similar behavior
has also been encountered in $d_{L}$ and its explanation is the same.

On the other hand, the distance metric which more effectively catches the
damage caused by a significant amount of missing data is $d_{\mathcal{L}}$,
where distance growth is linear. Indeed, the effects of $\langle k\rangle$ are
smaller as this aspect is compressed by the structure of this distance metric.
It would seem that this metric is the most effective measure compared to other
spectral distances, in understanding how much lacking data affects the total
knowledge of the network. A similar trend was also found in
$\mathrm{d_{rootED}}$; however, for a better comparison between nodes and
edges removal processes, we analysed this last metric in more detail by
considering its $DeltaCon$ similarity $sim_{DC}$ (Fig. 4).

The figure shows the difference between the original and pruned networks as
the fraction of elements removed increases (i.e., $F_{e}$ for edges and
$F_{n}$ for nodes).

Before starting pruning, we have $sim_{DC}=1$. Afterwards, the drop start to
became more evident as the fraction $F$ increases. In addition, as expected,
the nodes removal process affects more significantly the networks. This means
that if the lack of data relates to sporadically missed wiretaps, or to just a
few random connections between suspects, then the network structure is not as
much misinterpreted as if the case when one suspect has not been tracked at
all. Indeed, pruning the network at its 2%, causes a $sim_{DC}\geq 0.8$ for
edges pruning, compared with a $sim_{DC}\simeq 0.2$ for the nodes ones.
Therefore, even when a small amount of suspects are not included in the
investigations, this can lead to a very different network. The exclusion of
the suspects could be voluntary or not. It highly depends on the overall
investigation process, starting from the very preliminary analysis, and up to
the judges’ decision to allow warrants, or to exclude data considered
irrelevant for the current investigation.

Fig 2: The removal effects of a fraction $F_{e}$ of edges by showing the
distances $d(G,G^{{}^{\prime}})$ between the original graphs with their pruned
versions. (A) Adjacency Spectral Distance $d_{A}$ (B) Laplacian Spectral
Distance $d_{L}$ (C) Normalised Laplacian Spectral Distance $d_{\mathcal{L}}$
(D) Root Euclidean Distance $\mathrm{d_{rootED}}$. Fig 3: The removal effects
of a fraction $F_{n}$ of nodes by showing the distances $d(G,G^{{}^{\prime}})$
between the original graphs with their pruned versions. (A) Adjacency Spectral
Distance $d_{A}$ (B) Laplacian Spectral Distance $d_{L}$ (C) Normalised
Laplacian Spectral Distance $d_{\mathcal{L}}$ (D) Root Euclidean Distance
$d_{rootED}$. Fig 4: DeltaCon similarity $sim_{DC}$ computation (A) Edges
removal process by the fraction $F_{e}$ (B) Nodes removal process by the
fraction $F_{n}$.

## Discussion

In this paper we analysed nine datasets of real criminal networks extracted
from six police operations to investigate on the effects of missing data. More
specifically, three of them rely on Mafia operations (i.e., Montagna,
Infinito, and Oversize) and the remaining ones refer to other criminal
networks such as street gangs, drug traffics, or terrorist networks (i.e.,
Stockholm street gangs, Caviar Project, Philippines Kidnappers).

Our study focused on a careful analysis of the datasets, in order to simulate
the events where some of the data is missing. In particular, two different
scenarios have been considered:  (i) random edges removal, which simulates the
case in which LEAs miss to intercepts some calls or to spot sporadic meetings
among suspects, and  (ii) nodes removal that catches the hypothesis in which
some suspects cannot be intercepted for some reason. For instance, if a
criminal is known to be a boss, but there are not enough proofs to be
investigated, then the criminal can be identified by an isolated node with no
incident edges on it.

In order to quantify the difference between the original network and its
pruned version, we computed several distance metrics, to the one which is most
sensitive. Hence, we computed the Adjacency, Laplacian and Normalised Spectral
distances (i.e., $d_{A}(G,G^{{}^{\prime}})$, $d_{L}(G,G^{{}^{\prime}})$, and
$d_{\mathcal{L}}(G,G^{{}^{\prime}})$, respectively) plus the Root Euclidean
Distance (i.e., $\mathrm{d_{rootED}}(G,G^{{}^{\prime}})$) because this metric
allows to compute the DeltaCon similarity (i,e., $sim_{DC}$), which can
quantify even small differences between two graphs in $[0,1]$. The pruning
process involved removing up to 10% of elements, that is the fraction $F_{e}$
of edges and $F_{n}$ of nodes. This percentage has been chosen as the networks
size was quite small (less than 250 nodes per each dataset).

Our analysis suggests that  (i) the spectral metric
$d_{\mathcal{L}}(G,G^{{}^{\prime}})$ is best at catching the expected linear
growth of differences with the incomplete graph against its complete
counterpart;  (ii) the nodes removal process is significantly more damaging
than random edges removal;  thus, it translates to a negligible error in terms
of graph analysis when, for example, some wiretaps are missing. Indeed, in
terms of $sim_{DC}$ drop, there is a 30% difference from the real network, for
a pruned version at 10%. On the other hand, it is crucial to be able to
investigate the suspects in time because excluding them from the investigation
could produce a very different network respect to the real one, that is up to
80% of $sim_{DC}$ drop on some networks.

A final consideration concerns the impossibility of conducting this type of
analysis through the use of Machine Learning, as it is currently practically
impossible to obtain a sufficient number of reliable and complete datasets of
real criminal networks in order to be able to conduct an appropriate training
of a Neural Network.

For the future, we plan to extend the analysis by considering weights as well.
This will allow to conduct a comparative analysis of the missing data effects
when not only the connections between nodes, but also their frequency is
known. Another interesting aspect to be considered is the network behaviour
after their pruning in both criminal and general social networks. Lastly,
using the future knowledge gained from the network analysis herein presented,
one could try to define an artificial network able to accurately simulate the
behavior of real criminal networks.

## References

  * 1. Finckenauer JO.  Problems of definition: What is organized crime?  Trends in Organized Crime. 2005;8(3):63–83.  doi:10.1007/s12117-005-1038-4.
  * 2. Thrasher FM.  The gang: A study of 1,313 gangs in Chicago.  University of Chicago Press; 2013.
  * 3. Adler PA.  Wheeling and dealing: An ethnography of an upper-level drug dealing and smuggling community.  Columbia University Press; 1993.
  * 4. Reuter P.  Disorganized crime: The economics of the visible hand.  MIT press Cambridge, MA; 1983.
  * 5. Morselli C.  Inside Criminal Networks.  Studies of Organized Crime. Springer New York; 2008.
  * 6. Gambetta D.  The Sicilian Mafia: The Business of Private Protection.  Cambridge: Harvard University Press; 1996.
  * 7. Campana P.  Explaining criminal networks: Strategies and potential pitfalls.  Methodological Innovations. 2016;9:205979911562274.  doi:10.1177/2059799115622748.
  * 8. Johnsen JW, Franke K.  Identifying Central Individuals in Organised Criminal Groups and Underground Marketplaces.  In: Shi Y, Fu H, Tian Y, Krzhizhanovskaya VV, Lees MH, Dongarra J, et al., editors. Computational Science – ICCS 2018. Cham: Springer International Publishing; 2018. p. 379–386.
  * 9. Calderoni F, Catanese S, De Meo P, Ficara A, Fiumara G.  Robust link prediction in criminal networks: A case study of the Sicilian Mafia.  Expert Systems with Applications. 2020;161:113666.  doi:10.1016/j.eswa.2020.113666.
  * 10. MORSELLI C, ROY J.  Brokerage qualifications in ringing operations.  Criminology. 2008;46:71 – 98.  doi:10.1111/j.1745-9125.2008.00103.x.
  * 11. Duijn PAC, Kashirin V, Sloot PMA.  The Relative Ineffectiveness of Criminal Network Disruption.  Scientific Reports. 2014;4(1):4238.  doi:10.1038/srep04238.
  * 12. Rostami A, Mondani H.  The Complexity of Crime Network Data: A Case Study of Its Consequences for Crime Control and the Study of Networks.  PLOS ONE. 2015;10(3):1–20.  doi:10.1371/journal.pone.0119309.
  * 13. Robinson D, Scogings C.  The detection of criminal groups in real-world fused data: using the graph-mining algorithm “GraphExtract”.  Security Informatics. 2018;7(1):2.  doi:10.1186/s13388-018-0031-9.
  * 14. Villani S, Mosca M, Castiello M.  A virtuous combination of structural and skill analysis to defeat organized crime.  Socio-Economic Planning Sciences. 2019;65(C):51–65.  doi:10.1016/j.seps.2018.01.00.
  * 15. Ficara A, Cavallaro L, De Meo P, Fiumara G, Catanese S, Bagdasar O, et al.  Social Network Analysis of Sicilian Mafia Interconnections.  In: Cherifi H, Gaito S, Mendes JF, Moro E, Rocha LM, editors. Complex Networks and Their Applications VIII. Cham: Springer International Publishing; 2020. p. 440–450.
  * 16. Cavallaro L, Ficara A, De Meo P, Fiumara G, Catanese S, Bagdasar O, et al.  Disrupting resilient criminal networks through data analysis: The case of Sicilian Mafia.  PLOS ONE. 2020;15(8):1–22.  doi:10.1371/journal.pone.0236476.
  * 17. Cavallaro L, Bagdasar O, De Meo P, Fiumara G, Liotta A.  In: Fortino G, Liotta A, Gravina R, Longheu A, editors. Graph and Network Theory for the Analysis of Criminal Networks. Cham: Springer International Publishing; 2021. p. 139–156.
  * 18. Campana P, Federico V.  Cooperation in criminal organizations: Kinship and violence as credible commitments.  Rationality and Society. 2013;25:263–289.  doi:10.1177/1043463113481202.
  * 19. Doreian P.  Doing Social Network Research, G. Robins Sage, London (2015).  Social Networks. 2015;43.  doi:10.1016/j.socnet.2015.04.007.
  * 20. Sparrow MK.  The application of network analysis to criminal intelligence: An assessment of the prospects.  Social Networks. 1991;13(3):251–274.  doi:https://doi.org/10.1016/0378-8733(91)90008-H.
  * 21. Squartini T, Mastrandrea R, Garlaschelli D.  Unbiased sampling of network ensembles.  New Journal of Physics. 2015;17(2):023052.  doi:10.1088/1367-2630/17/2/023052.
  * 22. Peixoto TP.  Reconstructing Networks with Unknown and Heterogeneous Errors.  Phys Rev X. 2018;8:041011.  doi:10.1103/PhysRevX.8.041011.
  * 23. Newman MEJ.  Estimating network structure from unreliable measurements.  Phys Rev E. 2018;98:062321.  doi:10.1103/PhysRevE.98.062321.
  * 24. Soundarajan S, Eliassi-Rad T, Gallagher B.  In: A Guide to Selecting a Network Similarity Method; 2014. p. 1037–1045.
  * 25. Emmert-Streib F, Dehmer M, Shi Y.  Fifty years of graph matching, network alignment and network comparison.  Information Sciences. 2016;346-347:180 – 197.  doi:https://doi.org/10.1016/j.ins.2016.01.074.
  * 26. Donnat C, Holmes S.  Tracking network dynamics: A survey using graph distances.  The Annals of Applied Statistics. 2018;12(2):971–1012.  doi:10.1214/18-AOAS1176.
  * 27. Tantardini M, Ieva F, Tajoli L, Piccardi C.  Comparing methods for comparing networks.  Scientific Reports. 2019;9(1):17557.  doi:10.1038/s41598-019-53708-y.
  * 28. Cavallaro L, Ficara A, Curreri F, Fiumara G, De Meo P, Bagdasar O, et al.  Graph Comparison and Artificial Models for Simulating Real Criminal Networks.  In: Benito RM, Cherifi C, Cherifi H, Moro E, Rocha LM, Sales-Pardo M, editors. Complex Networks and Their Applications IX. Cham: Springer International Publishing; 2021. p. 286–297.
  * 29. Barabási AL, Pósfai M.  Network science.  Cambridge: Cambridge University Press; 2016.  Available from: http://barabasi.com/networksciencebook/.
  * 30. Ficara A, Fiumara G, De Meo P, Liotta A.  In: Fortino G, Liotta A, Gravina R, Longheu A, editors. Correlations Among Game of Thieves and Other Centrality Measures in Complex Networks. Cham: Springer International Publishing; 2021. p. 43–62.
  * 31. Wilson RC, Zhu P.  A study of graph spectra for comparing graphs and trees.  Pattern Recognition. 2008;41(9):2833 – 2841.  doi:https://doi.org/10.1016/j.patcog.2008.03.011.
  * 32. Wills P, Meyer FG.  Metrics for graph comparison: A practitioner’s guide.  PLOS ONE. 2020;15(2):e0228728.  doi:10.1371/journal.pone.0228728.
  * 33. Koutra D, Vogelstein JT, Faloutsos C.  DELTACON: A Principled Massive-Graph Similarity Function.  Proceedings of the 2013 SIAM International Conference on Data Mining. 2013; p. 162–170.  doi:10.1137/1.9781611972832.18.
  * 34. Cavallaro L, Ficara A, De Meo P, Fiumara G, Catanese S, Bagdasar O, et al.. Criminal Network: The Sicilian Mafia. “Montagna Operation”; 2020.  doi:10.5281/zenodo.3938818.
  * 35. Calderoni F, Piccardi C.  Uncovering the Structure of Criminal Organizations by Community Analysis: The Infinito Network.  In: 2014 Tenth International Conference on Signal-Image Technology and Internet-Based Systems; 2014. p. 301–308.
  * 36. Calderoni F.  In: Masys AJ, editor. Identifying Mafia Bosses from Meeting Attendance. Cham: Springer International Publishing; 2014. p. 27–48.  Available from: https://doi.org/10.1007/978-3-319-04147-6_2.
  * 37. Calderoni F.  In: Predicting Organized Crime Leaders; 2015. p. 89–110.  Available from: http://hdl.handle.net/10807/68084.
  * 38. Calderoni F, Brunetto D, Piccardi C.  Communities in criminal networks: A case study.  Social Networks. 2017;48:116–125.  doi:https://doi.org/10.1016/j.socnet.2016.08.003.
  * 39. Grassi R, Calderoni F, Bianchi M, Torriero A.  Betweenness to assess leaders in criminal networks: New evidence using the dual projection approach.  Social Networks. 2019;56:23–32.  doi:https://doi.org/10.1016/j.socnet.2018.08.001.
  * 40. Berlusconi G, Calderoni F, Parolini N, Verani M, Piccardi C.  Link Prediction in Criminal Networks: A Tool for Criminal Intelligence Analysis.  PLOS ONE. 2016;11(4):1–21.  doi:10.1371/journal.pone.0154244.
  * 41. Piccardi C, Berlusconi G, Calderoni F, Parolini N, Verani M. Oversize network; 2016\.  doi:10.6084/m9.figshare.3156067.v1.
  * 42. Rostami A, Mondani H. Network complexity data; 2015.  doi:10.6084/m9.figshare.1297161.v1.
  * 43. Gerdes LM, Ringler K, Autin B.  Assessing the Abu Sayyaf Group’s Strategic and Learning Capacities.  Studies in Conflict & Terrorism. 2014;37(3):267–293.  doi:10.1080/1057610X.2014.872021.
  * 44. Borgatti S, Everett M, Freeman L.  UCINET for Windows: Software for social network analysis; 2002.