# A Unified Framework for Underwater Metaverse with Optical Perception

Jingyang Cao, Mu Zhou, Jiacheng Wang, Guangyuan Liu, Dusit Niyato, , Shiwen
Mao, , Zhu Han, , and Jiawen Kang J. Cao is with the School of Communications
and Information Engineering, Chongqing University of Posts and
Telecommunications, China and with the School of Computer Science and
Engineering, Nanyang Technological University, Singapore (e-mail:
N2308615A@e.ntu.edu.sg). M. Zhou is with the School of Communications and
Information Engineering, Chongqing University of Posts and Telecommunications
(e-mail: zhoumu@cqupt.edu.cn). J. Wang, G. Liu, and D. Niyato are with the
School of Computer Science and Engineering, Nanyang Technological University,
Singapore (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>). S. Mao is
with the Department of Electrical and Computer Engineering, Auburn University,
Auburn, AL, 36849-5201 USA (e-mail<EMAIL_ADDRESS>Zhu Han is with the
Department of Electrical and Computer Engineering, University of Houston,
Houston, TX 77004 USA (e-mail<EMAIL_ADDRESS>J. Kang is with the School
of Automation, Guangdong University of Technology, China (e-mail:
<EMAIL_ADDRESS>
###### Abstract

With the advancement of AI technology and increasing attention to deep-sea
exploration, the underwater Metaverse is gradually emerging. This paper
explores the concept of underwater Metaverse, emerging virtual reality systems
and services aimed at simulating and enhancing virtual experience of marine
environments. First, we discuss potential applications of underwater Metaverse
in underwater scientific research and marine conservation. Next, we present
the architecture and supporting technologies of the underwater Metaverse,
including high-resolution underwater imageing technologies and image
processing technologies for rendering a realistic virtual world. Based on
this, we present a use case for building a realistic underwater virtual world
using underwater quantum imaging-generated artificial intelligence (QI-GAI)
technology. The results demonstrate the effectiveness of the underwater
Metaverse framework in simulating complex underwater environments, thus
validating its potential in providing high-quality, interactive underwater
virtual experiences. Finally, the paper examines the future development
directions of underwater Metaverse, and provides new perspectives for marine
science and conservation.

###### Index Terms:

Underwater metaverse, quantum imaging, generative artificial intelligence,
underwater environment.

##  I Introduction

The COVID-19 pandemic, along with the growth of virtual entertainment and
quick progress in digital technology, has led to a profound transformation in
societal interaction. This sparks considerable interest in digital experiences
and greatly helps the developement of the Metaverse. The Metaverse, as a
digitally blended space that merges the virtual and the real, has become a new
platform for people to connect, communicate and entertain[1]. In this wave,
technology giants, such as Facebook, play a crucial role in Metaverse
construction, striving to build digital cities, natural landscapes, and
virtual social spaces.111https://www.facebook.com/business/metaverse Apple
Vision Pro seamlessly blends digital content with physical
space.222https://www.apple.com/apple-vision-pro/ However, these efforts
primarily focus on the development of the land Metaverse, overlooking another
dimension of underwater Metaverse exploration, which is a novel concept
focusing on creating and simulating underwater environments, encompassing
shallow seas, deep oceans, lakes, glaciers, and more. Through highly realistic
simulation technologies, it immerses users in a virtual underwater world,
offering a completely new approach to explore and experience marine
ecosystems.333https://www.metaocean.space//

The usefulness of the underwater Metaverse lies in its ability to create
unique immersive and interactive underwater experiences beyond the limitations
of physical reality. It enables people to explore, experience, and interact
with the marine environment and its ecological content in unprecedented ways.
In this virtual underwater world, users can embark on deep-sea adventures,
observe rare marine lives, and even conduct scientific research, with rich
experiences that may be difficult to obtain in the physical
world.444https://www.yaswaterworld.com/en/experiences/underwater-vr
Furthermore, there are many applications of the underwater Metaverse, such as
virtual restoration of underwater cultural heritage, virtual design for
underwater resource exploration, simulation of underwater disasters and rare
deep-sea creatures. Additionally, the underwater Metaverse fosters new forms
of social interaction, allowing people to collaborate in this virtual seabed
world. Its advantages are mainly reflected in the following aspects:

  * •

Overcoming Physical Limitations: Real underwater exploration faces severe
challenges from natural conditions such as extreme depth, pressure,
temperature and light, which are significant limitations for both humans and
equipment[2]. The Metaverse provides a safe, risk-free virtual environment,
allowing users to explore the deep-sea without constraints of the physical
world.

  * •

Educational and Research Tool: The underwater Metaverse can be a powerful tool
for education and research. In the form of digital twin, it can accurately
simulate underwater environments and physical conditions, which are crucial
for scientific experiments and other
fields.555https://digitaltwinocean.mercator-ocean.eu/ Maritime education can
leverage this platform to learn and study various marine phenomena and
biological behaviors.

Figure 1: Keywords clustering results and timeline distribution in underwater
research and Metaverse studies. Keyword clustering analysis highlights the
relationship between research directions and key terms. As shown in Fig. 1(A),
in Metaverse research, virtual reality interaction technology forms the
largest cluster and has an early stage in the field. The rise of blockchain
and artificial intelligence technologies have propelled the development of the
Metaverse’s structure and environment studies. Increasingly, there is a focus
on user experience, emphasizing enhanced interactivity, realism, and
engagement to create more immersive and captivating virtual environments. As
shown in Fig. 1(B), in underwater research, the clustering analysis identified
10 clusters, with underwater applications being the largest and earliest-
starting cluster. With the development of underwater networks and detectors,
there is growing focus on constructing reliable systems for underwater data
collection and analysis. Consequently, underwater image reconstruction,
digital twin, and visual analysis have become the main research subjects (Data
from Web of Science: https://www.webofscience.com).

  * •

Unlimited Exploration Range: The underwater Metaverse can create highly
realistic underwater environments, giving users a strong sense of immersion,
especially as they can explore areas that are difficult and impossible to
reach in the real world, such as deep-sea trenches and remote seabed
volcanoes.666https://www.marum.de/en/Discover/Virtual-Deep-Sea.html As human
exploration of oceans continues and interest in marine ecology grows, the
underwater Metaverse is becoming an important bridge connecting reality and
virtuality, nature and technology, offering endless possibilities for future
ocean exploration, military simulation, and environmental protection.

However, we are still far from realizing the underwater Metaverse vision. One
characteristic of underwater environments is the significant reduction of
light, especially in deep-sea areas. Low light conditions pose higher demands
on the imaging technology. This requires the underwater Metaverse to
accurately capture and reconstruct target images under harsh conditions,
including sensitive marine life and complex seabed terrain. However, existing
underwater imaging technologies are limited in capturing such details,
particularly in maintaining high resolution and clarity in low-light
conditions [3]. Additionally, the dynamic nature of underwater environments
adds to the challenge. Marine ecosystems are constantly changing, with
multiple factors such as water currents and biological activity, which
requires the underwater Metaverse to create a dynamic and highly interactive
virtual environment. Finally, with increasing attention to data privacy and
security, another significant challenge that we face is how to provide a rich
and engaging underwater Metaverse experience while protecting user privacy.
Facing these challenges, we conduct literature analysis to delve into the key
areas of underwater and Metaverse research, revealing the technological
advancements and potential directions in addressing these difficulties. Fig. 1
illustrates the emerging research topics related to underwater and the
Metaverse. Underwater research focuses on image reconstruction, digital twin
and vision, which are crucial for accurate marine simulation and analysis. In
Metaverse research, areas including artificial intelligence, user experience,
and environmental simulation lay the foundation for an interactive,
intelligent virtual underwater environment.

Overall, the contributions of this paper are as follows:

  * •

We propose the concept of underwater Metavers. Underwater Metaverse is a
virtual underwater world, it includes multiple aspects such as visual,
perception, data collection, and interaction in the underwater environments.
Then, we propose and design the first underwater Metaverse architecture. This
architecture focuses on several key factors such as engine and safety,
offering feasibility and operability for the comprehensive implementation of
the underwater Metaverse.

  * •

We propose the quantum imaging-generative artificial intelligence (QI-GAI)
technology. This technology uses quantum imaging to achieve high-precision and
high-fidelity capture of underwater objects under harsh conditions, overcoming
the limitations of existing imaging technologies in underwater environments.
On this basis, GAI is then used to simulate and generate a highly realistic
underwater environment. Through a case study, we verify the feasibility of the
proposed technology and provide strong support for future applications of the
underwater Metaverse.

  * •

We discuss some unresolved issues. The exploration of these issues provides
future research directions for academia and industry, to promote in-depth
development in the field of underwater Metaverse.

##  II The Underwater Metaverse: Defination, Applications, and Architecture

###  II-A Definition

The underwater Metaverse defined as a submerged extension of the digital
universe, which intricately weaves together complex and dynamic underwater
environments. It encompasses immersive, interaction, and boundless aquatic
virtual environments, explored through user-directed avatars in a deep-sea
setting. In the following, we explain each feature in this definition.

  * •

Immersive: An immersive experience in the underwater Metaverse makes users
feel fully absorbed in a virtual environment, achieved through high-quality
imagery and simulations of physical characteristics, creating a sensation of
truly exploring ocean environments.

Figure 2: We can divide underwater Metaverse framework into three key layers:
the Physical World, the Underwater Metaverse Engine, and the Virtual World.
Each of these layers not only carries out its unique functions and
responsibilities but also closely interconnects with each other, together
forming a complete ecosystem of the underwater Metaverse. The precision and
efficiency of the physical layer are crucial for constructing a virtual
environment with a strong sense of realism. The engine layer not only ensures
the dynamics and authenticity of the virtual world but also provides the
necessary computational support to facilitate complex virtual interactions.
The collaborative effort of rendering technology, digital avatars, and virtual
objects creates a richly diverse and highly interactive underwater world

  * •

Interaction: Interaction allows users to engage with virtual marine life,
explore underwater realms, and collaborate with each other, enhancing
engagement and making the experience more lively and realistic.

  * •

Dynamic: Dynamic refers to the continuous changing and active characteristics
of the virtual environment. Users can observe and experience varying
surroundings and conditions virtually.

  * •

Boundless: Boundless means exploring without the limitations of geography,
safety, and other real-world constraints, allowing users to freely navigate
through an unrestricted virtual marine landscape, from shallow waters to deep
seas, and even to places unreachable in reality.

###  II-B Applications of the Underwater Metaverse

Diving into the underwater Metaverse, we uncover four fascinating applications
that are revolutionizing our interaction with the marine world.

  * •

Virtual Restoration and Exhibition of Underwater Cultural Heritage: The
underwater Metaverse offers a unique way to explore and protect submerged
cultural heritage, such as ancient ships, sunken ships and submerged city
sites.777https://www.euronews.com/green/2023/07/25/photogrammetry-virtual-
reality-and-ecotourism-exploring-and-preserving-our-underwater-heri Utilizing
high-precision imaging and virtual reality technologies, these relics can be
accurately restored and presented to the public. This approach not only makes
remote and deep-sea sites more accessible but also provides a risk-free
environment for archaeological research. Through the underwater Metaverse, we
can recreate history, serving as a powerful tool for education and cultural
heritage restoration.

  * •

Virtual Planning and Design for Underwater Engineering and Resource
Exploration: The underwater Metaverse offers a robust tool for planning and
designing underwater engineering projects. Within this virtual environment,
engineers can simulate the construction process of seabed pipeline laying,
deep-sea mining, and other engineering works. This method allows for the early
detection of potential design issues and testing the performance of equipment
and structures under extreme deep-sea conditions. Additionally, resource
exploration in the underwater Metaverse, such as deep-sea mineral resources,
can assess potential resource locations and mining value without disturbing
the marine environment, providing key information for sustainable resource
utilization.

  * •

Underwater Disaster Simulation and Emergency Response Training: The underwater
Metaverse can be used to simulate marine disasters, such as tsunamis, seabed
earthquakes, and oil and gas leaks. In these virtual environments, rescue
teams can conduct emergency response training, study the potential impact of
disasters, and develop effective response strategies. For example, by
simulating oil and gas leak scenarios, different containment and cleanup
strategies can be tested, thus enhancing the efficiency and safety of real-
world disaster recovery.

  * •

Deep-Sea Rare Creatures Simulation: The underwater Metaverse, with its three-
dimensional modeling technology, can create realistic deep-sea environments,
including complex terrains like deep-sea trenches and hydrothermal vents. In
these simulated environments, rare deep-sea creatures such as deep-sea
octopuses, unique fish species, and other not fully studied organisms can be
virtually recreated. These simulations not only replicate the appearance of
these creatures but also include their behavioral patterns, habits, and
interactions with the environment.

###  II-C Underwater Metaverse Architecture

The architecture of the underwater Metaverse is presented in Fig. 2

####  II-C1 Physical-Virtual World Interaction

The relationship between these two layers is iterative and interactive. As
users engage with the virtual layer, their actions can trigger changes that
influence data collection and analysis in the physical layer, creating a
feedback loop. The integration ensures that virtual representation of
underwater objects and animals remains accurate and up-to-date to users
exploring the dynamic ocean environment. It includes:

  * •

Data Collection and Transmission: The physical layer forms the foundation of
the entire underwater virtual universe system. Various sensors and devices,
such as underwater cameras, sonar, and other measurement tools, are
responsible for collecting environmental data. The collected data is then
transmitted to the engine layer. In addition, underwater communications are
crucial for data transmission, including acoustic communication, optical
communication, and radio frequency communication. The engine layer, serving as
the center for data processing and analysis, transforms these physical data
into information usable in the virtual world.

  * •

User Interaction and Feedback: Users interact in the virtual world through
input devices such as VR, controllers, and haptic devices [4]. These devices
enable users to dive, explore, and interact with the virtual underwater
environment and other users. Actions of users within the virtual underwater
world are captured and processed by the engine layer, which can influence the
output of the engine layer, in turn, affect the operation of devices in the
physical world.

  * •

Two-Way Dynamic Interaction: User activities in the virtual world not only
affect the engine layer but can also be fed back to the physical world,
creating a two-way interaction mechanism. For example, user exploration
behaviors in the virtual underwater world can guide the path of submarines in
the ocean. Similarly, changes in the physical world (e.g., tides and current)
are instantly reflected in the virtual underwater world.

  * •

Augmented Reality and Integrated Experience: Elements of the physical and
virtual worlds can be combined in an augmented reality environment, providing
users with a richer and more intuitive interactive experience[5]. Users can
interact with virtual objects in a real environment, making underwater
exploration and research more vivid and interactive.

####  II-C2 Underwater Metaverse Engine

The engine layer is the core processing and analytical layer within the
framework of the underwater Metaverse, acting as a bridge between the physical
world and the virtual world. The primary task of this layer is to receive data
from the physical world layer, conduct in-depth analysis and processing, and
based on this, construct and maintain a dynamic underwater Metaverse virtual
environment. Specifically, it includes:

  * •

Artificial Intelligence: AI technology is used to process and analyze large
amounts of data collected from the underwater environment, including marine
biological activities and hydrogeological data. AI technology can identify
patterns, predict environmental changes, and automate decision-making
processes [6]. This technology helps optimize the construction and management
of the underwater Metaverse environment, improving the system’s responsiveness
and level of intelligence.

Figure 3: Underwater Metaverse technology and applications represent a
revolutionary advancement, combining key Metaverse technologies with ocean
exploration to offer an unprecedented way to understand and experience the
underwater world[5]. This field integrates various technologies such as VR,
AR, visual, AI, and generative algorithms to create a realistic and highly
interactive virtual underwater environment. With the continuous advancement of
technology and the growth of applications, the underwater Metaverse is
expected to play an increasingly important role in the future.

  * •

Digital Twin: Digital twin technology in the engine layer of the underwater
Metaverse is used to create an accurate digital replica of the physical
underwater environment.888https://ocean-twin.eu/digital-twins This includes
virtual models of marine terrain, underwater structures, and marine life. With
real-time and periodic updates, these digital twin models can reflect the
current state of the real environment, providing users with real-time
environmental information and a rich interactive experience.

  * •

Virtual Modeling: Virtual modeling is used to create and maintain various
elements in the virtual environment. This includes virtual marine creatures,
simulated water flow and lighting effects, and shallow and deep-water
environments. Advanced modeling technology ensures that the virtual
environment is not only visually realistic but also capable of interacting in
real-time with user’s actions and choices.

##  III Enabling Underwater Metaverse Technologies

The underwater Metaverse includes four key technologies: perception,
communications, processing and rendering, as shown in the Fig. 3

###  III-A Perception

In the underwater Metaverse, perception is primarily used for capturing and
interpreting environmental information. The imaging system of visual
perception is particularly critical as it directly affects our cognition and
understanding of the underwater world. It can be divided into three main
parts.

####  III-A1 Underwater Acoustic Imaging

Acoustic imaging is a method of detection and imaging using sound waves. This
technology is particularly effective in underwater environments, as sound
waves can travel long distances in water, detecting farther objects and
terrains [7]. Sonar technology works by emitting sound waves and capturing
their reflections, and analyzing the reflections to determine the location,
shape, and other characteristics of objects. The resolution of underwater
acoustic imaging depends on the frequency of the sound waves used. Higher
frequencies provide finer details, but at the cost of reduced detection range.
This technology has wide applications in underwater navigation, terrain
mapping, and detection of underwater life.

####  III-A2 Underwater Radio Imaging

Underwater radio imaging technology utilizes radio waves to detect and image
underwater environments. This technology primarily relies on the interaction
between radio waves and underwater objects [8], and its resolution is limited
by the propagation characteristics of radio waves in water. When radio waves
encounter underwater objects, their propagation characteristics change, such
as reflection, refraction and scattering, thereby creating specific signal
patterns at the receiver. Underwater radio imaging systems identify and image
underwater objects by analyzing these altered signals. This method is highly
effective for detecting the structure and characteristics of underwater
objects, such as their shape, size, and material, making it highly valuable
for applications in underwater navigation, communication, and other related
fields. In addition, this technology is suitable for shallow water or near-
surface applications.

####  III-A3 Underwater Quantum Imaging

Due to the absorption and scattering of light by water, its propagation in
water is severely affected, requiring light imaging technology to adapt to
this special environment. QI technology plays a significant role in this
aspect [9]. It utilizes the time-space correlation properties of entangled
photon pairs to enhance the accuracy and efficiency of imaging. Compared with
traditional underwater optical imaging, this technology shows significant
advantages in reducing noise and improving image clarity. These quantum
properties allow light imaging systems to capture high-quality images even in
very low light conditions, thus visually representing the underwater world
more accurately.

###  III-B Communications

In the construction of the underwater Metaverse, underwater communication
technology is the infrastructure for achieving interaction and immersive
experiences.

####  III-B1 Acoustic-based Underwater Communication

Underwater acoustic communication utilizes the propagation characteristics of
sound waves in water for data transmission. This
technology999https://acomms.whoi.edu/ is primarily used for long-distance
communication and data transfer in the underwater Metaverse, especially
suitable for extensive underwater environmental exploration. Information is
transmitted using modulation techniques such as Frequency Shift Keying (FSK),
Phase Shift Keying (PSK), and Orthogonal Frequency-Division Multiplexing
(OFDM). These techniques encode information by altering the frequency,
amplitude, and phase of sound waves. Taking into account the impact of
temperature, salinity and pressure variations on sound wave propagation in
underwater environments, the communication system uses sound velocity
profiling and multipath effect correction models to address unique underwater
challenges such as multipath effects and velocity profile changes, thereby
improving the accuracy and reliability of communication.

####  III-B2 RF-based Underwater Communication

Despite the significant limitations of underwater environments on RF signals,
under certain conditions, such as using low-frequency bands, RF communication
can still be effective over short distances. Key technologies[10] include
short-range radio wave propagation models, frequency selection, and modulation
techniques such as Amplitude Modulation (AM) and Frequency Modulation (FM).
Considering the attenuation characteristics of radio waves in water, the
system comprises efficient signal encoding and decoding techniques, along with
robust signal processing capabilities to overcome high attenuation and noise
in underwater environments. RF communication is particularly effective in
shallow water and near-surface applications, thus the algorithms also involve
optimizing transmission distance and power to achieve optimal underwater
communication performance.

####  III-B3 Optical-based Underwater Communication

Due to its high-speed and low-latency characteristics, underwater optical
communication technology101010https://www.shimadzu.com/underwater/index.html
offers significant advantages in transmitting high-quality video and image
data. This technology employs laser modulation techniques such as Pulse
Position Modulation (PPM), Pulse Width Modulation (PWM), and signal
enhancement techniques for optical receivers. Optical communication system
also includes beamforming and directional control techniques to minimize
propagation loss, due to the scattering and absorption of light waves in
water. In the underwater Metaverse, this communication technology is used for
fast and efficient data exchange, providing a more realistic and enriched
visual experience.

###  III-C Processing

In the underwater Metaverse, it is necessary to analyze and process data
collected from perception technologies such as acoustic imaging, radio
imaging, and quantum imaging. The purpose of this process is to extract useful
information from raw data to better understand and utilize the characteristics
of the underwater environment. In underwater settings, due to factors like
light attenuation, sound wave scattering, and electrical signal interference,
the processing of imaging data is particularly complex. Here are several
primary data processing techniques:

####  III-C1 Deep Learning in Underwater Acoustic Imaging

In underwater acoustic imaging, sound waves are used to detect underwater
environments, and deep learning can effectively process the acoustic data[11].
First, the underwater acoustic data needs to be preprocessed, which includes
noise filtering, contrast enhancement, and image normalization, to improve the
quality of the original underwater sonar images and make them more suitable
for training and prediction with deep learning models. Second, feature
extraction is performed. For example, Convolutional Neural Networks (CNNs) can
automatically extract and learn hierarchical features of images. Then, model
selection and training are conducted. For image classification, architectures
such as ResNet and VGG can be used. For object detection tasks, models like
Faster R-CNN, and Single Shot MultiBox Detector (SSD) are employed. Lastly,
post-processing is performed, which may include filtering, non-maximum
suppression and threshold setting, to enhance the accuracy and readability of
the final results.

####  III-C2 Time-Frequency Analysis in Underwater Radio Imaging

Time-Frequency Analysis technology[12] can effectively decompose underwater
radio signals and extract frequency components at different time instances by
combining time domain and frequency domain analysis. In the preprocessing
stage, frequency domain filtering can be employed, particularly utilizing
band-pass filters to eliminate high and low-frequency noises in the signal.
For the time-frequency analysis part, the sophisticated Continuous Wavelet
Transform (CWT) could be utilized, which is suitable for processing non-
stationary and time-variant signals. Then, the Hilbert-Huang Transform (HHT)
shall be employed to further improve the precision of time-frequency analysis.
Statistical methods can be used to extract key signal features, such as the
energy distribution and entropy of the signal, and Spectral Peak Tracking
(SPT) technology can be used to identify the main frequency components and
their trends. In the post-processing stage, the extracted features are
smoothed to eliminate noise interference, and data visualization techniques,
such as time-frequency plots and spectrograms, are used to intuitively present
the time-frequency characteristics of the signal. The advantage of this
technology lies in its enhanced signal resolution, especially for non-
stationary and rapidly changing underwater signals, which can more accurately
distinguish and identify various types of underwater objects and structures.

####  III-C3 Compressive Sensing in Underwater Quantum Imaging

In underwater QI, the image data typically produced are sparse in certain
transform areas, meaning that the majority of coefficients are close to or
equal to zero. In this process, it is necessary to design a measurement
matrix, such as a Gaussian random matrix and Bernoulli random matrix, to
perform underwater data acquisition. Signal reconstruction is the core of
compressed sensing[13], we can utilize optimization algorithms such as
Matching Pursuit (MP), Orthogonal Matching Pursuit (OMP), and Basis Pursuit
(BP) to recover the original signal and image from a limited number of
measurements. The goal is to minimize the sparsity of the reconstructed image
while maintaining consistency with the observed data. Finally, the
reconstructed data can be post-processed as needed, such as denoising and
filtering, to enhance the imaging quality and clarity. The advantage of this
method lies in its ability to efficiently reconstruct high-quality images from
fewer data measurements, which is particularly crucial for underwater
environments where data transmission and storage resources are limited,
significantly reducing the dependency on expensive and complex sensors.

###  III-D Rendering

Rendering technology can transform processed data into intuitive images and
scenes, thereby providing users with highly realistic virtual environments. In
the underwater Metaverse, rendering technology faces unique challenges, such
as the need to accurately simulate underwater optical properties, dynamic
environmental changes, and complex biological ecosystems. Here are several
main rendering techniques applied in the underwater Metaverse:

####  III-D1 Generative AI Driven Underwater Metaverse

Underwater images often suffer from quality issues like blurriness and color
deviation due to factors such as light attenuation and water scattering.
Generative AI technologies, including Generative Adversarial Networks (GANs)
and Variational Autoencoders (VAEs) are employed to reconstruct high-
resolution images from sparse data, effectively capturing complex details of
underwater environments, such as terrain and biological entities.

####  III-D2 Visual SLAM Driven Underwater Metaverse

Visual SLAM technology facilitates real-time localization and mapping in
underwater environments, accurately tracking the position and orientation of
devices while constructing detailed 3D
maps.111111https://www.maxstblog.com/post/types-of-slam-and-application-ex
This technology enhances the spatial accuracy of underwater imaging data,
providing a precise spatial reference. The combination of processed imaging
data with the maps generated by visual SLAM allows for the creation of
realistic underwater virtual environments. The precise localization
capabilities of visual SLAM, along with efficient data processing, enable the
development of an accurate and real-time underwater metaverse.

##  IV Case Study

###  IV-A Experimental Configuration

Due to light attenuation and interference from water impuriy, traditional
imaging technology is difficult to obtain high-quality images for rendering
underwater Metaverse targets, which has a significant impact on the visual
experience of users. Therefore, we utilize the underwater QI technology, as
shown in Fig. 4(a), which leverages entanglement, non-locality, and spatio-
temporal correlations to achieve high-resolution imaging under low-light
conditions, while also reducing the effects of water scattering and
absorption. This technology not only improves the quality of underwater
imaging but also captures more details in complex underwater environments,
such as the deep-sea and turbid waters.

Figure 4: (a) is a schematic diagram of underwater entangled photon quantum
imaging. (b) shows the loaded modulation pattern in DMD. In the quantum image,
the white squares indicate areas on the DMD that remain open. Only reference
photons in the open areas can be scanned by the DMD and collected by the
single-photon detector. (c) and (d) represent the constructed imaging optical
path and the underwater quantum imaging experimental setup.

To validate the underwater quantum imaging, we conduct tests in an
experimental environment. We set up an entangled QI platform based on
compressed sensing and simulate the underwater environment, as shown in Fig.
4(c). This platform includes an entangled light source, signal and reference
optical paths, a water tank, a Digital Micromirror Device (DMD), and two
single-photon detectors for receiving entangled photons. In particular, we set
up a water tank on the signal light path, so that the signal light can
vertically pass through the water tank and directly illuminate the target
object [9], as shown in Fig. 4(d). We simulate deep and shallow marine
environments, thereby more accurately testing the effectiveness of our
proposed imaging technology. Due to the equipment limitations, we use cards to
simulate the targets. Then we reconstruct the image by obtaining coincidence
count values of the real target. Through this method, the number of required
measurements can be significantly reduced while maintaining high-quality image
reconstruction.

###  IV-B Performance Analysis

Figure 5: The impact of GAI steps on generated content. The images on the left
are the input underwater quantum light source and classical light source
images, and the image on the right is the corresponding generated content. As
can be seen, more steps trigger more natural content, showing fuller details
and contours, as shown in the green box.

We then analyze image generation, using the virtual avatar of a shark in the
underwater Metaverse as an example, to demonstrate how QI-GAI specifically
supports the underwater Metaverse. The generated results are displayed in Fig.
5. We use the ControlNet model121212https://github.com/lllyasviel/ControlNet
and the steps are set to 20. From the results, we can see that the diffusion
model (GAI) can effectively generate virtual avatars based on underwater
target data and instruction sets. With the increase in inference steps, the
image quality can be significantly improved. Specifically, when only one
inference step is executed, the generated content is merely noise, as shown by
the result corresponding to step 1 in Fig. 5. As the number of inference steps
increases, the shape begins to gradually emerge, and its details correspond to
the real target. For example, in the results of the first row, as the steps
increase, the details of the object gradually are enriched, and the background
details are also gradually refined. Therefore, the model can generate images
based on quantum images and user instructions, confirming the effectiveness of
the QI-GAI technology, which can provide support for the underwater Metaverse.

Moreover, we compare images generated using underwater quantum light sources
and classical light sources. We set two groups of DMD with different bundled
pixel values, $80\times 80$ and $180\times 180$, respectively. From the
results in the second column, we can see that the resolution of underwater
quantum imaging is higher than that of classical light sources, showcasing
better underwater imaging results, and higher bundled pixel images have higher
resolution. However, if the bundled pixel value is set too high, it can lead
to lower image resolution due to the introduction of more stray photons. From
the avatar images generated in the seventh column, we can see that QI-GAI
generates better shark outlines and richer details, closer to the real target,
as shown by the details in the yellow frame. From the results in the first and
third rows, we can see that higher bundled pixel values display more shark
details, such as the shark fins shown in the red frame. However, the generated
shark forms vary, which can be guided by other parameters, e.g., environment
conditions and user preferences. Moreover, multimodality techniques can be
adopted for adjusting the variation.

##  V Future Directions

###  V-A Three-Dimensional Underwater Quantum Imaging

Due to the superior penetration capabilities of quantum light sources, QI is
highly effective in deep-water and low-visibility environments, which is of
significant importance for the exploration and research of the underwater
metaverse. However, the existing QI technology is limited to two dimensions.
Therefore, in the construction of the underwater Metaverse, underwater three-
dimensional QI technology is not only the key to achieving advanced visual
effects but also central to enhancing user experience. Technologically, three-
dimensional QI, utilizing the variance in flight times, can construct the
z-axis information, i.e., using the multidimensional characteristics of
quantum to increase the density of imaging information. Moreover, this imaging
technology requires overcoming the existing optical limitations, developing
quantum sensors and data processing algorithms that can operate stably under
extreme underwater conditions, and optimizing the extraction and analysis of
quantum information to ensure the accuracy and real-time updating of three-
dimensional models.

###  V-B Balance of Computing Resources

In future development of the underwater Metaverse, rational allocation and
optimization of computational resources are particularly crucial. Since the
underwater Metaverse involves real-time processing of massive data and complex
simulation modeling[14], it requires effective distribution of computational
tasks among various system nodes—including edge devices, underwater servers,
and cloud infrastructure. Such allocation aims to optimize the overall system
performance while reducing energy consumption, ensuring the sustainable
operation of the system. Furthermore, balancing computational resources also
involves algorithm optimization, hardware upgrades, and innovative design of
network architecture.

###  V-C Data Security and Ethics

In the underwater Metaverse, ensuring the protection of sensitive data from
cyber threats while safeguarding the privacy and rights of individuals and
entities will be an ongoing challenge. Due to the uniqueness of the underwater
environment, traditional methods of data encryption and security protocols may
no longer be applicable. Therefore, developing secure data-sharing algorithms
and protocols will be the key to ensuring the security of underwater data.
Furthermore, considering the potential impact of underwater activities on
marine ecosystems, establishing an ethical framework[15] for the collection
and use of underwater data becomes particularly important. This includes
taking into account the potential effects on marine life, ensuring compliance
with international environmental laws and guidelines, and maintaining the
integrity of the marine environment in scientific research, exploration, and
commercial activities. In this way, the underwater Metaverse can protect the
marine environment and respect the rights and interests of all relevant
stakeholders while innovating and advancing technology.

##  VI Conclusion

In this article, we presented an underwater Metaverse framework, focusing not
only on technology and security but also systematic guidance and operational
solutions for implementing the underwater Metaverse. We described four key
technologies for the underwater Metaverse construction. For each key
technology, we outlined the fundamental concepts and methods that could be
used to address related issues. Then, a case study of underwater Metaverse was
conducted using the proposed QI-GAI technology. The QI technology achieved
high-precision and high-fidelity object capture in severe underwater
environments, effectively overcoming the limitations of existing underwater
imaging technologies. Generative AI technology was used to simulate and
generate highly realistic underwater targets. This casew study not only
demonstrated the feasibility of our proposed concepts and technologies, but
also provided solid technical support for future applications in the
underwater metaverse. This is the first universal framework proposed to
combine underwater characteristics. Furthermore, the integration of underwater
quantum imaging and GAI technology for digital content generation is an
innovative experimental attempt. Finally, in future research, we will further
investigate specific technical issues in the process of perception with GAI,
moving towards an intelligent underwater Metaverse.

## References

  * [1] W. Y. B. Lim, Z. Xiong, D. Niyato, X. Cao, C. Miao, S. Sun and Q. Yang, “Realizing the metaverse with edge intelligence: A match made in heaven,” _IEEE Wireless Communications_ , vol. 30, no. 4, pp. 64–71, Aug. 2023.
  * [2] R. Liu, X. Fan, M. Zhu, M. Hou and Z. Luo, “Real-world underwater enhancement: Challenges, benchmarks, and solutions under natural light,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 30, no. 12, pp. 4861–4875, Dec. 2020.
  * [3] J. Li, P. Hu, W. Cui, T. Huang and S. Cheng, “Deepsea: a meta-ocean prototype for undersea exploration,” _Information Technology & Tourism_, vol. 25, no. 3, pp. 391–409, Aug. 2023.
  * [4] M. Xu, W. C. Ng, W. Y. Lim, J. Kang, Z. Xiong, D. Niyato, Q. Yang, X. Shen and C. Miao, “A full dive into realizing the edge-enabled metaverse: Visions, enabling technologies, and challenges,” _IEEE Communications Surveys & Tutorials_, vol. 25, no. 1, pp. 656–700, Nov. 2023.
  * [5] L. Lee, T. Braud, P. Zhou, L. Wang, D. Xu, Z. Lin and A. Kumar, “All one needs to know about metaverse: A complete survey on technological singularity, virtual ecosystem, and research agenda,” _arXiv preprint arXiv:2110.05352_ , 2021.
  * [6] J. Wang, H. Du, D. Niyato, Z. Xiong, J. Kang, S. Mao and X. Shen, “Guiding AI-Generated Digital Content with Wireless Perception,” _arXiv preprint arXiv:2303.14624_ , 2023.
  * [7] J. L. Sutton, “Underwater acoustic imaging,” _Proceedings of the IEEE_ , vol. 67, no. 4, pp. 554–566, Apr. 1979.
  * [8] I. I. Smolyaninov, Q. Balzano, M. Barry and D. Young, “Superlensing enables radio communication and imaging underwater,” _Scientific Reports_ , vol. 13, no. 1, pp. 1–7, Oct. 2023.
  * [9] J. Cao, W. Nie, and M. Zhou, “A high-resolution and low-cost entangled photon quantum imaging framework for marine turbulence environment,” _IEEE Network_ , vol. 36, no. 5, pp. 78–86, Sept. 2022.
  * [10] A. Palmeiro, M. Martín, I. Crowther and M. Rhodes, “Underwater radio frequency communications,” _in Proc. IEEE OCEANS 2011_ , Santander, Spain, Aug. 2011, pp. 1–8.
  * [11] H. Kulhandjian, N. Ramachandran, M. Kulhandjian and C. Amours, “Human activity classification in underwater using sonar and deep learning,” _in Proc. ACM Mobicom_ , Los Cabos, Mexico, Oct. 2019, pp. 1–5.
  * [12] V. C. Chen and H. Ling, “Time-frequency transforms for radar imaging and signal analysis,” _Artech House_ , 2002.
  * [13] Z. Hu, M. Zhou, W. Nie, X. Yang and J. Cao, “Cost-efficient Entangled Light Quantum Imaging Based on Compressed Sensing,” _in Proc. IEEE 10th Asia-Pacific Conference on Antennas and Propagation (APCAP)_ , Xiamen, China, Mar. 2022, pp. 1-2.
  * [14] J. Wang, H. Du, Z. Tian, D. Niyato, J. Kang and X. Shen, “Semantic-aware sensing information transmission for metaverse: A contest theoretic approach,” _IEEE Transactions on Wireless Communications_ , vol. 22, no. 8, pp. 5214–5228, Aug. 2023.
  * [15] A. Jobin, M. Ienca, E. Vayena. “The global landscape of AI ethics guidelines,” _Nature Machine Intelligence_ , vol. 1, no. 9, pp. 389–399, Sept. 2019.


# An Augmented Index-based Efficient Community Search
for Large Directed Graphs

Yankai Chen1 Jie Zhang2 Yixiang Fang3111Corresponding Author Xin Cao3&Irwin
King1
1Department of Computer Science and Engineering, The Chinese University of
Hong Kong
2School of Computer Science and Engineering, Nanyang technological university
3The University of New South Wales
{ykchen<EMAIL_ADDRESS><EMAIL_ADDRESS>{yixiang.fang,
<EMAIL_ADDRESS>
###### Abstract

Given a graph $G$ and a query vertex $q$, the topic of _community search_
(CS), aiming to retrieve a dense subgraph of $G$ containing $q$, has gained
much attention. Most existing works focus on undirected graphs which overlooks
the rich information carried by the edge directions. Recently, the problem of
community search over directed graphs (or CSD problem) has been studied Fang
et al., 2019b ; it finds a connected subgraph containing $q$, where the in-
degree and out-degree of each vertex within the subgraph are at least $k$ and
$l$, respectively. However, existing solutions are inefficient, especially on
large graphs. To tackle this issue, in this paper we propose a novel index
called _D-Forest_ , which allows a CSD query to be completed within the
optimal time cost. We further propose efficient index construction methods.
Extensive experiments on six real large graphs show that our index-based query
algorithm is up to two orders of magnitude faster than existing solutions.

##  1 Introduction

With the rapid development of information technologies, large graphs are
ubiquitous in various areas (e.g., social networks and biological science)
Ying et al., (2018). Finding communities over these graphs is fundamental to
many real applications, such as event organization, recommendation, and
network analysis. In recent years, the topic of _community search_ (CS) has
gained much attention (e.g., Sozio and Gionis, (2010); Cui et al., (2014);
Huang et al., (2014); Fang et al., 2019a ), which aims to find dense
communities containing the query vertex $q$ from a graph $G$ in an online
manner.

Earlier CS works (e.g., Sozio and Gionis, (2010); Cui et al., (2013, 2014);
Barbieri et al., (2015)) mainly focus on undirected graphs, where the graph
edges do not have directions. They often require the community to be a
connected subgraph satisfying a particular metric of structure cohesiveness
(e.g., each vertex within the community has a degree of $k$ or more). Later
on, the attributes (e.g., keywords Fang et al., 2017a , locations Fang et al.,
2017b , profiles Chen et al., (2019), and influence values Li et al., (2015))
of graphs have also been considered for CS. However, all these works ignore
the directions of edges in the graphs. As pointed out in Malliaros and
Vazirgiannis, (2013); Zhang et al., (2014), the ignorance of directions of
edges, failing to capture asymmetric relationships implied by the directions,
may lead to noise and inaccurate results.

Figure 1: A directed graph.

To remedy the issue above, Fang et al. Fang et al., 2019b  studied the problem
of CS over directed graphs, or CSD problem. Specifically, given a query vertex
$q$ of a directed graph $G$, and two integers $k$ and $l$, it aims to find a
maximum connected subgraph containing $q$, where the in-degree and out-degree
of each vertex within the subgraph are at least $k$ and $l$, respectively. For
example, in Figure 1, let $q$=$B$ and $k$=$l$=2; then, the subgraph $C_{1}$
will be returned; if $k$=$l$=3, then the subgraph $C_{2}$ is the answer. The
minimum degree constraints have also been used in the ($k$, $l$)-core
Giatsidis et al., (2011), or the maximum subgraph in which each vertex’s in-
degree and out-degree are at least $k$ and $l$, respectively. Note that the
($k$, $l$)-core may not be a connected subgraph.

To answer a CSD query, an online method is to iteratively peel vertices that
do not satisfy the degree constraints until finding the subgraph satisfying
both the connectivity and minimum degree constraints. Obviously, this
iterative approach could be costly. To improve efficiency, Fang et al. Fang et
al., 2019b  develop indexes, which pre-compute all the ($k$, $l$)-cores and
then organize them compactly. Given a CSD query, they first find the ($k$,
$l$)-core using the indexes, and then compute the maximum connected subgraph
containing $q$ from the ($k$, $l$)-core. Clearly, since this maximum connected
subgraph is often much smaller than the ($k$, $l$)-core, their solutions are
inefficient if the ($k$, $l$)-core is very large. For example, on a graph with
about 4 billion edges, they may take over 33 minutes to answer 200 queries as
shown by our experiments.

To facilitate efficient CSD queries, in this paper we develop a novel index
structure, called D-Forest, which not only compactly organizes all the ($k$,
$l$)-cores, but also takes the connectivity into consideration. Specifically,
we first compute all the ($k$, $l$)-cores sequentially where $k$ and $l$ range
from 0 to their maximum values. Then, for each value of $k$, we compute their
connected components and organize them into a tree structure, where each tree
node corresponds to a connected ($k$, $l$)-core. As a result, the index is a
forest, consisting of a list of trees. Given the D-Forest, to answer a CSD
query, we first find the $k$-th tree and then return the connected ($k$,
$l$)-core containing $q$. Clearly, the query takes the optimal query time
cost, i.e., $O(|C|)$, where $C$ is the set of vertices in the community. We
also discuss index maintenance for dynamic graphs and how to use D-Forest to
answer the query of a variant of the CSD problem, i.e., SCSD Fang et al.,
2019b . Experiments on six real large graphs show that our index construction
process takes comparable time cost with those of existing algorithms, and our
query algorithm takes only 14.4 seconds to answer 200 queries on a graph with
around 4 billion edges.

In summary, our main contributions are as follows:

  * •

We develop a novel index D-Forest, based on which a CSD query can be completed
in optimal time cost.

  * •

To build the D-Forest, we propose a basic algorithm, and an advanced algorithm
by introducing an auxiliary data structure called Core-based Union-Find (or
CUF).

  * •

We discuss the index maintenance for dynamic graphs, and how to answer the
SCSD query using D-Forest.

  * •

We perform extensive experiments on six real large graphs; results show that
our query algorithm is up to two orders of magnitude faster than existing
solutions.

##  2 Related Works

Community detection (CD). Generally, CD aims to detect all the communities
from an entire graph. Earlier classic solutions (e.g., Newman and Girvan,
(2004); Newman, (2004); Fortunato, (2010)) rely on edge-based analysis (e.g.,
modularity maximization) to discover these communities. However, most of them
focus on undirected graphs. Recent works start to detect communities from
directed graphs. In Leicht and Newman, (2008); Kim et al., (2010), the concept
of modularity maximization Newman, (2004) is extended for CD on directed
graphs. In Lancichinetti and Fortunato, (2009), authors introduced new
benchmark graphs to test CD methods over directed graphs. Yang et al. Yang et
al., (2010) introduced a new stochastic block model called PPL to find
communities in directed graphs; they also detected overlapped communities in
directed graphs Yang et al., (2014). Besides, there are also some local CD
methods (e.g., Flake et al., (2000); Ning et al., (2016)). A recent survey of
CD solutions on directed graphs can be found in Malliaros and Vazirgiannis,
(2013). However, as pointed out in Fortunato and Hric, (2016), CD is an ill-
defined problem with no clear universal definition of the objects that one
should be looking for. However, these CD methods are often time consuming,
especially on large graphs, and also it is not clear how they can be adapted
for online CS.

Community search (CS). CS finds the community from a large graph in a fast and
online manner, based on a query request. To measure the structure cohesiveness
of communities, the $k$-core metric is often employed, requiring that each
vertex of the community should have a degree of $k$ or more, where $k$ is a
given integer Batagelj and Zaversnik, (2003); Dorogovtsev et al., (2006);
Sozio and Gionis, (2010); Cui et al., (2014); Li et al., (2015); Fang et al.,
2017a ; Fang et al., 2017b ; Chen et al., (2019). Other cohesiveness metrics
have also been considered for CS, such as $k$-clique Yang et al., (2011); Cui
et al., (2013), $k$-truss Huang et al., (2014, 2015, 2016); Akbas and Zhao,
(2017); Huang and Lakshmanan, (2017); Ebadian and Huang, (2019) and $k$-ECC Hu
et al., (2017), pagerank-based Andersen and Lang, (2006); Kloumann and
Kleinberg, (2014), etc. A survey of CS over graphs can be found in Fang et
al., 2019a . However, most of these works focus on undirected graphs. A recent
work Fang et al., 2019b  has studied CS over directed graphs, but its
solutions are still inefficient for large graphs, calling for more efficient
CS approaches.

##  3 Problem Definition

We consider a directed graph $G(V,E)$ with a vertex set $V$ and an edge set
$E$. The sizes of $V$ and $E$ are respectively denoted by $n$ and $m$. The in-
degree and out-degree of a vertex $v$ in $G$ are denoted by $deg_{G}^{in}(v)$
and $deg_{G}^{out}(v)$. Next, we introduce the core model on directed graphs.

######  Definition 1 ($(k,l)$-core Giatsidis et al., (2011)).

Given a directed graph $G(V,E)$ and two non-negative integers $k$ and $l$, the
($k$,$l$)-core of $G$ is the largest subgraph $G^{\prime}$ of $G$, such that
$\forall v\in G^{\prime}$, $deg^{in}_{G^{\prime}}(v)\geq k$ and
$deg^{out}_{G^{\prime}}(v)\geq l$.

In the $(k,l)$-core, each vertex has at least $k$ in-neighbours and $l$ out-
neighbours, so it is well engaged in the subgraph especially when $k$ and $l$
are large. This implies that the $(k,l)$-core is a cohesive subgraph, and thus
can be used to model the cohesiveness of the community Fang et al., 2019b .
However, the ($k$, $l$)-core may not be a connected subgraph, so the
connectivity constraint should be further imposed to model the community. Note
that for simplicity, we denote a connected ($k$, $l$)-core by ($k$,
$l$)-$\widehat{core}$.

Based on the discussions above, Fang et al. Fang et al., 2019b  formally
introduced the problem of Community Search over Directed graphs (CSD) problem:

######  Problem 1 (CSD problem Fang et al., 2019b ).

Given a directed graph $G(V,E)$, a query vertex $q$, and two positive integers
$k$ and $l$, return the ($k$, $l$)-$\widehat{core}$ containing $q$.

For example, in Figure 1, the (1, 1)-core, (2, 2)-core, and (3, 3)-core are
marked in three different colors, where the (1, 1)-core has three connected
components. If $q$=$B$ and $k$=$l$=3, then the (3, 3)-$\widehat{core}$ $C_{2}$
is returned as the community.

##  4 Our Index-based Approach

To enable efficient CSD queries, in this paper we propose a novel index,
called D-Forest, which allows the targeted community to be retrieved directly
without examining the ($k$, $l$)-core. As a result, the query time cost is
optimal. Meanwhile, the index is space efficient since it takes $O(m)$ space
cost. In the following sections, we first give an overview of D-Forest, and
then present two algorithms to build D-Forest.

###  4.1 Index Overview

We begin with an interesting lemma.

######  Lemma 1 (Fang et al., 2019b ).

Given a directed graph $G$, for any ($k$, $l$)-core with $l\textgreater 0$, it
is a subgraph of the ($k$, $l$$-$$1$)-core, i.e., the ($k$, $l$)-core is
nested within the ($k$, $l$$-$$1$)-core.

By Lemma 1, we can conclude that for any specific value of $k$, all the ($k$,
$l$)-cores where $l$ ranges from 0 to its maximum value can be organized into
a chain such that each one is nested within its previous one. Similarly, the
nested property above holds for the connected components of ($k$, $l$)-cores;
that is, for any ($k$, $l$)-$\widehat{core}$ with $l\textgreater 0$, it is
nested within a particular ($k$, $l$–1)-$\widehat{core}$, so we can get a
chain for each ($k$, $l$)-$\widehat{core}$. Consequently, for each value of
$k$, we can build a tree structure called $k$-tree, by hierarchically
organizing all these chains, such that each subtree corresponds to a ($k$,
$l$)-$\widehat{core}$.

For example, all ($k$, $l$)-$\widehat{core}$s in Figure 1 can be organized
into 4 trees, as depicted in Figure 2, where the $k$-tree is built for the
value of $k$ and each subtree contains all the vertices of a particular ($k$,
$l$)-$\widehat{core}$. For instance, in the $1$-tree, the subtree rooted at
node 222In this paper, we use “node” to mean the “index tree node”. $p$, as
shown in the dashed box, contains vertices $\\{F,G,H\\}$ and $\\{A,B,C,D\\}$,
which are the vertices in the $(1,2)$-$\widehat{core}$. Note that the number
attached in each node indicates the value of $l$ for the corresponding ($k$,
$l$)-$\widehat{core}$ and we use the root node $t$ to keep the tree shape.

Figure 2: An example D-Forest index.

To summarize, in the $k$-tree, each node has four elements:

  * •

$parent$: a pointer to its parent node;

  * •

$childList$: a list of pointers to its child nodes;

  * •

$vSet$: a set of vertices, which are in the ($k$, $l$)-$\widehat{core}$ but
not in the ($k$, $l$–1)-$\widehat{core}$;

  * •

$coreNum$: the value of $l$ of the ($k$, $l$)-$\widehat{core}$, which
corresponds to the subtree rooted at this node.

To enable efficient locating of the ($k$, $l$)-$\widehat{core}$, for each
tree, we build an auxiliary map, where each key is a vertex and its value
points to the node containing the vertex in the tree. All proofs of lemmas are
attached in Appendix A.

######  Lemma 2 (Space cost).

Given a directed graph $G$, its D-Forest takes $O(m)$ space.

$\bullet$ Query algorithm. To answer a CSD query, we can first use the
auxiliary map to locate the tree node $p$ which contains $q$, then find the
root of the subtree corresponding to the ($k$, $l$)-$\widehat{core}$
containing $q$, and finally return the set $C$ of vertices in the subtree. We
denote the query algorithm above by IDX-Q.

######  Lemma 3 (Query cost).

Given a D-Forest, IDX-Q completes in the optimal time and space cost, i.e.,
$O(|C|)$.

Next, we present two index construction algorithms, which work in the top-down
and bottom-up manners, respectively.

###  4.2 A Top-Down Index Construction Method

In Fang et al., 2019b , an efficient algorithm of decomposing ($k$, $l$)-cores
for a graph is developed. It enumerates $k$ from 0 to its maximum value
$k_{\max}$, and for each $k$, it computes all the ($k$, $l$)-cores where $l$
ranges from 0 to its maximum value $l_{\max}$. Since D-Forest is comprised of
($k_{\max}$$+$$1$) trees, we can also enumerate $k$ from 0 to $k_{\max}$, and
for each specific $k$, we build the $k$-tree by the following the steps:

  1. 1.

compute the ($k$, $0$)-core, create a node with a set of vertices in ($k$,
$0$)-core, and initialize $l$=$1$;

  2. 2.

compute all the ($k$, $l$)-$\widehat{core}$s from the ($k$,
$l$$-$$1$)-$\widehat{core}$s;

  3. 3.

for each ($k$, $l$)-$\widehat{core}$, create a node $p$ ($p.vSet$ contains
vertices in ($k$, $l$)-$\widehat{core}$, $p$.$coreNum$=$l$), link $p$ to its
parent node $p^{\prime}$, and update $p^{\prime}.vSet$ as
$p^{\prime}.vSet\backslash p.vSet$;

  4. 4.

increase $l$ by 1, and repeat steps 2 and 3 until $l$ reaches its maximum
value.

Since the above method builds trees of D-Forest in a top-down manner, we
denote it by TopDown, the pseudocodes of which are shown in Algorithm 1.

Algorithm 1 Index construction algorithm: TopDown.

1:function build($G$)

2: $\mathcal{F}\leftarrow\emptyset$;

3: for $k\leftarrow 0$ to $k_{\max}$ do

4: $map\leftarrow\emptyset$, compute $(k,0)$-core and create root node $t$;

5: for $l\leftarrow 1$ to $l_{\max}$ do

6: $S\leftarrow$ compute $(k,l)$-$\widehat{core}$s from
$(k,l-1)$-$\widehat{core}$s;

7: for each $(k,l)$-$\widehat{core}$ in $S$ do

8: create a node $p$ and $p.coreNum\leftarrow l$;

9: $p.vSet\leftarrow$ vertices in this $(k,l)$-$\widehat{core}$;

10: locate $p$’s parent node $p^{\prime}$, link $p^{\prime}$ and $p$;

11: $p^{\prime}vSet\leftarrow p^{\prime}vSet\backslash p.vSet$;

12: for $v$ in $p^{\prime}vSet$ do $map.$put($v,p^{\prime}$);

13: $\mathcal{F}$.add($\langle t$, $map\rangle$);

14: return $\mathcal{F}$;

######  Lemma 4.

Given a directed graph $G$, the time cost of building D-Forest using TopDown
is $O(m^{2})$.

###  4.3 A Bottom-Up Index Construction Method

While TopDown is easy to implement, it may suffer from the low efficiency
issue, as shown in Lemma 4. To further improve the efficiency, we propose
another more efficient index construction method BottomUp, by introducing an
auxiliary data structure called Core-based Union-Find (or CUF), which builds
the trees in a bottom-up manner. Next, we first give an overview of BottomUp,
and then introduce the details.

$\bullet$ Overview of BottomUp. Unlike TopDown, BottomUp enumerates the values
of $k$ from $k_{\max}$ to 0, and builds each tree in a bottom-up manner (i.e.,
create leaf nodes at first and root node at last). Meanwhile, when building
the $k$-tree, it exploits the information generated in building
($k$+$1$)-tree.

Algorithm 2 Index construction algorithm: BottomUp.

1:function build($G$)

2: $\mathcal{F}\leftarrow\emptyset$, $pre[\text{ }]\leftarrow\emptyset$,
$cur[\text{ }]\leftarrow\emptyset$, $\Psi\leftarrow\emptyset$;

3: for $k\leftarrow k_{\max}$ to $0$ do

4: $map\leftarrow\emptyset$, $\mathcal{P}\leftarrow\emptyset$;

5: $cur[\text{ }]\leftarrow\textsc{decompose($G$, $k$)}$;

6: $V_{0},\cdots,V_{l_{\max}}$ $\leftarrow$ group vertices of $cur[\text{ }]$;

7: for $l\leftarrow l_{\max}$ to $0$ do

8: BuildALevel($k$, $l$, $V_{l}$, $pre[\text{ }]$, $cur[\text{ }]$, $map$,
$\mathcal{P}$, $\Psi$);

9: create root node $t$ and link to nodes in $\mathcal{P}$;

10: $pre[\text{ }]\leftarrow cur[\text{ }]$, $\mathcal{F}$.add($\langle t$,
$map\rangle$);

11: return $\mathcal{F}$;

Algorithm 2 outlines BottomUp. We first initialize an empty forest
$\mathcal{F}$, two arrays $pre[\text{ }]$, $cur[\text{ }]$, where $pre[v]$ and
$cur[v]$ are supposed to keep the maximum value of $l$ such that there is a
($k$, $l$)-core containing $v$. We also initialize the CUF data structure
$\Psi$ which will be introduced later (line 2). Then, we enumerate $k$ from
$k_{\max}$ to 0 and for each $k$, we compute all the ($k$, $l$)-cores (lines
3-5), by using the algorithm in Fang et al., 2019b . We initialize the vertex-
node map $map$, and a set $\mathcal{P}$ for keeping the generated nodes for
each level of $k$-tree (line 4). After that, we group vertices into a list of
sets, such that $V_{l}$ contains vertices which are in the ($k$, $l$)-core but
not in the ($k$, $l$–1)-core (line 6). Next, we build the $k$-tree by invoking
BuildALevel to create nodes in the $l$-th level of $k$-tree where $l$ ranges
from $l_{\max}$ to $0$ (lines 7-8). Finally, we create the root node with
$\mathcal{P}$, and update $pre[\text{ }]$ and $\mathcal{F}$ (lines 9-10).

$\bullet$ Overview of function BuildALevel. Given nodes in the ($l$+1)-th
level of $k$-tree, the function BuildALevel creates nodes in the $l$-th level
and links them to the nodes in the ($l$+1)-th level. Since each node
corresponds to a ($k$, $l$)-$\widehat{core}$, a naive method to check the
connectivity and create the node will take $O(m)$ time to re-explore the
graph, i.e., executing steps 2 and 3 of TopDown. Consequently, using this
naive method totally takes $O(l_{\max}\cdot m)$ to build the $k$-tree, which
is the same as that of TopDown.

To improve the efficiency, we propose a novel data structure, called Core-
based Union-Find (or CUF), which allows the three key steps of BuildALevel to
be done efficiently: (1) verifying the connectivity, (2) memorizing the
connectivity, and (3) linking nodes. In the following sections, we first
introduce the CUF data structure, and then present our CUF-based BuildALevel,
which allows the $k$-tree to be built in $O(\alpha(n)\cdot m)$ time, where
$\alpha(n)$ is the inverse Ackermann function and $\alpha(n)<5$ for any
practical value of $n$.

$\bullet$ CUF data structure. CUF is extended from classic Union-Find (UF)
Forest333https://en.wikipedia.org/wiki/Disjoint-set_data_structure, which can
efficiently verify the graph connectivity and partition vertices into
different connected components. In the classic UF, each vertex has 2 elements,
i.e., $rank$ and $parent$, and the UF has 3 functions, i.e., makeSet, find and
union, where makeSet makes preparation for each vertex, find returns the
representative member of the component to which the vertex belongs, and union
merges two disjoint components as one. By using the classic UF, given a ($k$,
$0$)-core, we can verify the connectivity and sequentially find all ($k$,
$l$)-$\widehat{core}$’s by varying $l$ from $l_{\max}$ to $0$, and then build
all the levels of the $k$-tree accordingly. However, classic UF may have two
main limitations.

Algorithm 3 Functions of the CUF data structure.

1:function makeSet($v$)

2: $v.rank\leftarrow 0$, $v.parent\leftarrow v$;

3: $v.hook\leftarrow v$, $v.group\leftarrow v$;

4:function find($v$)

5: if $v.parent$ = $v$ then

6: $v.parent\leftarrow$ find($v.parent$);

7: return $v.parent$;

8:function union($u$, $v$, $cur[\text{ }]$)

9: $r_{u}\leftarrow$ find($u$), $r_{v}\leftarrow$ find($v$);

10: if $r_{u}\neq r_{v}$ then

11: if $r_{u}.rank<r_{v}.rank$ then swap($r_{u}$, $r_{v}$);

12: $r_{v}.parent\leftarrow r_{u}$;

13: if $r_{u}.rank=r_{v}.rank$ then

14: $r_{u}.rank\leftarrow r_{u}.rank+1$;

15: if $cur[r_{u}.group]<cur[r_{v}.group]$ then

16: $r_{u}.group\leftarrow r_{v}.group$;

17:function updateCuf($V$, $cur[\text{ }]$)

18: for $u\in V$ do

19: $r\leftarrow$ find($v$);

20: $v.group\leftarrow r.group$;

21: if $cur[r.hook]>cur[v]$ then $r.hook\leftarrow v$;

One limitation is that for a new node $p$ in the $l$-th level, classic UF can
not efficiently find $p$’s all child nodes and link them up. As observed in
Section 4.1, each subtree below the $l$-th level corresponds to a particular
($k$, $l^{\prime}$)-$\widehat{core}$ where $l^{\prime}\textgreater l$. This
means that to find $p$’s child nodes, we can first find all ($k$,
$l^{\prime}$)-$\widehat{core}$’s that are connected by vertices in $p.vSet$
and then link the root nodes of corresponding subtrees to $p$. To efficiently
locate these subtrees, we assign another element $hook$ to directly indicate
these root nodes. For example, for a vertex $v$ in $p.vSet$, if $v$’s
neighbour $u$ is contained in a ($k$, $l^{\prime}$)-$\widehat{core}$, we can
locate the root node of the corresponding subtree by referring $hook$ and then
link it to $p$.

The other limitation is that once the $l$-th level of the ($k$+$1$)-tree is
constructed, the connectivity of the corresponding ($k$+$1$, $l$)-core is
verified. When building the $l$-th level of the $k$-tree, we have to traverse
the corresponding ($k$, $l$)-core and verify its connectivity from scratch.
However, from Lemma 1, ($k$+$1$, $l$)-core is a subgraph of ($k$, $l$)-core,
which implies that the connectivity of this ($k$+$1$, $l$)-core will be
verified again. To cut off this redundant computation, we assign an additional
element $group$ in CUF structure to “memorize” the particular ($k$,
$l$)-$\widehat{core}$ to which each vertex used to belong. For instance, if
vertex $v$ is included in a certain ($k$+$1$, $l$)-$\widehat{core}$, $v.group$
will be marked; and when processing the ($k$, $l$)-core, by checking
$v.group$, we would quickly know that $v$ should be gathered together with
others who share the same value.

Algorithm 3 summarizes all CUF functions and underlines our contribution. To
maintain the two additional elements, we propose a new function updateCuf. As
shown in Algorithm 3, for each vertex $v$, we find the representative member
$r$ of the particular ($k$, $l$)-$\widehat{core}$ including $v$, i.e.,
find($v$) (lines 18-19). Then we update $v.group$ as $r.group$ and set
$r.hook$ as $v$ if $v$ has smaller value in $cur[\text{ }]$ (lines 20-21).

######  Lemma 5 (Space cost).

Given a directed graph $G$, the CUF data structure of all vertices costs
$O(n)$ space.

######  Lemma 6 (Time cost of CUF functions).

makeSet takes $O(1)$ time; for union and find, the amortized time per
operation is $O(\alpha(n))$; updateCuf takes $O(\alpha(n)\cdot|V|)$ time.

$\bullet$ Details of function BuildALevel. Algorithm 4 shows the details.
Firstly, we find root nodes of subtrees to be linked to new nodes in this
level. For each vertex $v$, we initialize a set $S_{v}$; we visit $v$’s
neighbour $u$ to find the root $p^{\prime}$ of the subtree including $u$ and
collect it in $S_{v}$ (lines 2-8). Then we use CUF to verify the subgraph
connectivity for this level. We initialize a set $V^{\prime}$ to collect
vertices if they has been previously processed in the $l$-th level of the
($k$+$1$)-tree (lines 9-13). For vertices in $V^{\prime}$, we directly use
their $group$ to achieve a quick union; for others, we visit their neighbours
to check the connectivity by invoking batchUnion (lines 15-16, 24-28). After
that, for each vertex set $C_{i}$ sharing the same CUF root, we create the
node $p$ and update $\mathcal{P}$ (lines 17-19). For each vertex $v$ in
$C_{i}$, we update the vertex-node map $map$ and link child nodes in $S_{v}$
to $p$ (lines 20-22). Finally, we update CUF for the constrcution of next
level (line 23).

Algorithm 4 Process vertices to create tree nodes.

1:function BuildALevel($k$, $l$, $V_{l}$, $pre[\text{ }]$, $cur[\text{ }]$,
$map$, $\mathcal{P}$, $\Psi$)

2: initialize $S_{v_{1}}$, $\cdots$, $S_{v_{i}}$, $\cdots$ for vertices
$v_{1}$, $\cdots$, $v_{i}$, $\cdots\in V_{l}$;

3: for $v\in V_{l}$ do

4: for $u\in N(v)$ do

5: if $cur[u]>cur[v]$ then

6: $r_{u}\leftarrow$ $\Psi$.find($u$);

7: $p^{\prime}\leftarrow map.$get($r_{u}.hook$);

8: $S_{v}$.add($p^{\prime}$), $\mathcal{P}$.delete($p^{\prime}$);

9: $V^{\prime}\leftarrow\emptyset$;

10: for $v\in V_{l}$ do

11: if $k\neq k_{\max}$ and $pre[v]=l$ then

12: $v.parent\leftarrow v$, $v.hook\leftarrow v$;

13: $v.rank\leftarrow 0$, $V^{\prime}.$add($v$);

14: else $\Psi$.makeSet($v$);

15: batchUnion($V_{l}\backslash V^{\prime}$, $cur[\text{ }]$, $\Psi$);

16: for $v\in V^{\prime}$ do $\Psi$.union($v$, $v.group$, $cur[\text{ }]$);

17: for each set $C_{i}\subseteq V_{l}$ with the same CUF root do

18: $p\leftarrow$ create tree node by using $l$ and $C_{i}$;

19: $\mathcal{P}$.add($p$);

20: for each $v\in C_{i}$ do

21: $map$.put($v$, $p$);

22: link nodes in $S_{v}$ with $p$;

23: $\Psi$.updateCuf($C_{i}$, $cur[\text{ }]$);

24:function batchUnion($V$, $cur[\text{ }]$, $\Psi$)

25: for $v\in V$ do

26: for $u\in N(v)$ do

27: if $cur[u]\geq cur[v]$ then

28: $\Psi$.union($u$, $v$, $cur[\text{ }]$);

######  Lemma 7.

Given a directed graph $G$, the time cost of building D-Forest using BottomUp
is $O(\alpha(n)\cdot m\cdot\sqrt{m})$.

##  5 Discussions

In this section, we discuss how to solve a variant of the CSD problem using
D-Forest. We also discuss index maintenance techniques.

###  5.1 SCSD Problem

The community returned by a CSD query may not be a strongly connected
component (SCC), i.e., each pair of vertices in are mutually reachable. To
search the SCC-based communities, Fang et al. introduced the SCSD problem:

######  Problem 2 (SCSD problem Fang et al., 2019b ).

Given a directed graph $G(V,E)$, a query vertex $q$, and two positive integers
$k$ and $l$, return a subgraph $G^{\prime}$ such that $G^{\prime}$ is an SCC
containing $q$ and $\forall v\in G^{\prime}$, $deg^{in}_{G^{\prime}}(v)\geq k$
and $deg^{out}_{G^{\prime}}(v)\geq l$.

The SCSD problem can be readily solved by using D-Forest. Specifically, we
first retrieve the ($k$, $l$)-$\widehat{core}$ $G^{\prime}$ containing $q$
from the D-Forest index. Then, we compute the SCC $C_{q}$ containing $q$ from
$G^{\prime}$. After that, if $C_{q}$ does not satisfy the minimum degree
constraints, we compute a ($k$, $l$)-$\widehat{core}$ containing $q$ from
$C_{q}$ and then repeat the above steps to find the answer. Note that to
compute SCCs of a graph, we can use Kosaraju’s algorithm Hopcroft and Ullman,
(1983), which only takes linear time. We denote this algorithm by IDX-SQ, and
omit its pseudocodes for lack of space.

###  5.2 Index Maintenance

In practice, graphs are often dynamically updated, so it is necessary to
update D-Forest accordingly. A simple method is to rebuild D-Forest from
scratch when the graph updates. This, however, is very costly, and thus it is
desirable to develop efficient index maintenance techniques. As shown in Li et
al., (2013); Fang et al., 2017a , when an edge is inserted or deleted, only a
few ($k$, $l$)-cores change while others remain unchanged, so it is possible
to update D-Forest efficiently. Specifically, when a new edge ($u$, $v$) is
added in the ($k$, $l$)-core, $u$’s out-degree and $v$’s in-degree will
increase by 1. To update D-Forest, we execute three steps: (1) for the vertex
$u$, if the increase of $u$’s out-degree enables $u$ to be included in the
($k$, $l$+1)-core, we locate the node containing $u$ in the $k$-tree and then
move $u$ down to the node corresponding to this ($k$, $l$+1)-core; (2) for the
vertex $v$, similarly, if the increase of $v$’s in-degree enables $v$ to be
grouped into the ($k$+1, $l$)-core, then we add $v$ to the node corresponding
to this ($k$+1, $l$)-core; (3) after including a vertex into another core, the
connectivity of some connected components of the cores may change, so we need
to merge the subtrees corresponding to the newly updated subgraph. For the
case of edge deletion, we can update the index by taking the inverse process
of above steps. Note that the case of vertex update can be regarded as
sequentially inserting or deleting a list of edges.

##  6 Experiments

###  6.1 Setup

We use six real large directed graphs and summarize their statistics in Table
1, where $d$ is the average degree of vertices. The Twitter dataset
444https://www.isi.edu/lerman/downloads/twitter/twitter2010.html is collected
by Kristina Lerman. The eu-2015, arabic, it-2004, sk-2005 and uk-2007 datasets
Boldi et al., (2014); Boldi and Vigna, (2004); Chen et al., (2021) are
available in the website555http://law.di.unimi.it/datasets.php. We implement
all the algorithms in Java, and run the experiments on a Linux machine with
Ten-core Intel E7-4820 V3<EMAIL_ADDRESS>and 300GB memory.

Table 1: Datasets in our experiments. Graph | $n$ | $m$ | $d$ | $k_{\max}$ | $l_{\max}$
---|---|---|---|---|---
Twitter | 699,986 | 36,743,091 | 52.49 | 443 | 448
eu-2015 | 6,650,532 | 165,693,531 | 24.91 | 9,568 | 9,569
arabic | 22,744,080 | 639,999,458 | 28.14 | 3,126 | 3,126
it-2004 | 41,291,594 | 1,150,725,436 | 27.86 | 3,198 | 3,197
sk-2005 | 50,636,154 | 1,949,412,601 | 38.50 | 4,502 | 4,502
uk-2007 | 110,123,614 | 3,944,932,566 | 35.82 | 10,027 | 10,027
|  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
Figure 3: The space cost of D-Forest and the time cost of index construction. |  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
Figure 4: The efficiency of answering CSD queries.

###  6.2 Experimental Results

We compare our approach with the state-of-the-art solutions Fang et al., 2019b
which propose three indices, i.e., NestIDX, PathIDX and UnionIDX, and three
corresponding query algorithms, i.e., Nest-Q, Path-Q and Union-Q. Using the
same evaluation strategy in Fang et al., 2019b , we respectively report the
efficiency results of index construction and queries in Figures 3 and 4. To
evaluate the efficiency of index construction, for each dataset, we randomly
select 20%, 40%, 60% and 80% of its vertices and obtain the four subgraphs
induced by these vertices.

1\. Space cost of D-Forest. To measure the space cost of an index, we store
all the index elements, which can be used to recover the index, into the disk.
As shown in Figure 3 (a)-(f), with the sizes of sub-datasets growing, the
space cost of D-Forest and others increase steadily. Besides, D-Forest uses
comparable space cost as other indexes, meaning that D-Forest is as space-
efficient as the state-of-the-art solutions.

2\. Time cost of index construction. From Figure 3(g)-(l), we can observe that
BottomUp takes similar time cost with state-of-the-art solutions . For
instance, on the largest dataset uk-2007 (35.4GB in disk), BottomUp takes only
8.12 hours to build D-Forest. And BottomUp always runs at least 10 times
faster than TopDown. We remark that to save the computational resources, for
each test, we terminate TopDown if it runs 10 times longer than BottomUp.

3\. Scalability evaluation of CSD queries. In Figure 4(a)-(f), we evaluate the
scalability of CSD query algorithms over different sizes of datasets. As
suggested in Fang et al., 2019b , for each sub-dataset, we randomly select 200
vertices which are in the (8,8)-cores as the query vertices and set
$k$=$l$=$8$. Generally, the running time of all algorithms increases as the
size of sub-datasets grows. Besides, our query algorithm IDX-Q achieves the
best performance on all the datasets. For example, on uk-2007 dataset with
around 4 billion edges, IDX-Q takes 72ms on average to answer a query and runs
about 100 times faster than the existing solutions.

4\. Effect of $k$ and $l$ in CSD queries. We depict the effect of $k$ and $l$
on the efficiency of CSD queries in Figure 4(g)-(r). For each dataset, we
randomly select 200 vertices within the (8,8)-cores to query. We see that as
the value of $k$ and $l$ increases, the returned communities become smaller,
so the time cost of all query algorithms decreases. Again, IDX-Q is up to two
orders of magnitude faster than the three existing algorithms which generally
achieve similar performance.

5\. Efficiency of SCSD queries. Generally, SCSD queries are slower than CSD
queries, since they have to spend extra time cost to compute SCC’s. We have
compared IDX-SQ with Nest-SQ, Path-SQ and Union-SQ proposed in Fang et al.,
2019b , and the results show that IDX-SQ can run about 4 times faster than
these three algorithms. For example, on uk-2007, IDX-SQ takes 1.85s on average
to find an SCC-based (8, 32)-core, while others take 3.21s, 2.38s and 6.88s.
For lack of space, we omit the detailed results here.

##  7 Conclusion

In this paper, we examine the CSD problem and design a novel index D-Forest,
based on which a CSD query can be completed in the optimal time cost. To build
the index, we propose a basic algorithm TopDown, and an advanced algorithm
BottomUp by introducing the CUF data structure. We also discuss the index
maintenance for dynamic graphs and how to answer the SCSD query using
D-Forest. The experimental results on six real large graphs demonstrate the
efficiency of our solutions.

In the future, we will investigate how to extend other cohesiveness metrics,
such as $k$-truss and $k$-clique, to search communities in large directed
graphs. We will also study how to find meaningful communities from directed
graphs with attributes, e.g., keywords and locations.

## Acknowledgments

##  Appendix A Proofs of Lemmas

######  Lemma 2 (Space cost).

Given a directed graph $G$, its D-Forest takes $O(m)$ space.

###### Proof.

For each vertex $v$, if its in-degree is $k$, then it appears in at most $k$
trees, and in each tree, it appears only twice (one in the tree and one in the
auxiliary map). Thus, the space cost of $v$ is bounded by
$O(deg_{G}^{in}(v))$. Hence, Lemma 2 holds. ∎

######  Lemma 3 (Query cost).

Given a D-Forest, IDX-Q completes in the optimal time and space cost, i.e.,
$O(|C|)$.

###### Proof.

The lemma directly follows the observation. ∎

######  Lemma 4.

Given a directed graph $G$, the time cost of building D-Forest using TopDown
is $O(m^{2})$.

###### Proof.

Given a specific $k$, computing all the ($k$, $l$)-cores from the ($k$,
$0$)-core takes $O(m)$ time; besides, searching all the ($k$,
$l$)-$\widehat{core}$s from the ($k$, $l$$-$$1$)-$\widehat{core}$s takes
$O(m)$ Fang et al., 2019b . Thus, it takes $O(l_{\max}\cdot m)$ time to build
the $k$-tree. Since there are ($k_{\max}$$+$$1$) trees, the total cost is
$O(k_{\max}\cdot l_{\max}\cdot m)$. Meanwhile, $k_{\max}$ and $l_{\max}$ are
at most $(\sqrt{4m+1}-1)/2$ Fang et al., 2019b , so Lemma 4 holds. ∎

######  Lemma 5 (Space cost).

Given a directed graph $G$, the CUF data structure of all vertices costs
$O(n)$ space.

###### Proof.

The lemma directly follows the observation. ∎

######  Lemma 6 (Time cost of CUF functions).

makeSet takes $O(1)$ time; for union and find, the amortized time per
operation is $O(\alpha(n))$; updateCuf takes $O(\alpha(n)\cdot|V|)$ time.

###### Proof.

Obviously, makeSet for each vertex takes $O(1)$. As for union and find, since
they use _union by rank_ and _path compression_ optimization, the amortized
time per operation is $O(\alpha(n))$ Tarjan, (1979). Thus, updateCuf totally
takes $O(\alpha(n)\cdot|V|)$ for all vertices in $V$. ∎

######  Lemma 7.

Given a directed graph $G$, the time cost of building D-Forest using BottomUp
is $O(\alpha(n)\cdot m\cdot\sqrt{m})$.

###### Proof.

Decomposing the ($k$, $0$)-core for a specific $k$ takes $O(m)$ time Fang et
al., 2019b . Then buildALevel takes $O(\alpha(n)\cdot m_{l})$, where $m_{l}$
is the edges visited in the $l$-th level. This implies that building $k$-tree
takes $O(\alpha(n)\cdot m)$ in total. Thus BottomUp takes
$O(k_{\max}\cdot\alpha(n)\cdot m)$, which is upper bounded by
$O(\alpha(n)\cdot m\cdot\sqrt{m})$. Lemma 7 holds. ∎

## References

  * Akbas and Zhao, (2017) Akbas, E. and Zhao, P. (2017).  Truss-based community search: a truss-equivalence based indexing approach.  PVLDB, 10(11):1298–1309.
  * Andersen and Lang, (2006) Andersen, R. and Lang, K. (2006).  Communities from seed sets.  In WWW, pages 223–232.
  * Barbieri et al., (2015) Barbieri, N., Bonchi, F., Galimberti, E., and Gullo, F. (2015).  Efficient and effective community search.  DMKD, 29(5):1406–1433.
  * Batagelj and Zaversnik, (2003) Batagelj, V. and Zaversnik, M. (2003).  An o (m) algorithm for cores decomposition of networks.  CoRR.
  * Boldi et al., (2014) Boldi, P., Marino, A., Santini, M., and Vigna, S. (2014).  Bubing: massive crawling for the masses.  In WWW, pages 227–228.
  * Boldi and Vigna, (2004) Boldi, P. and Vigna, S. (2004).  The WebGraph framework I: Compression techniques.  In WWW, pages 595–601, Manhattan, USA.
  * Chen et al., (2019) Chen, Y., Fang, Y., Cheng, R., Li, Y., Chen, X., and Zhang, J. (2019).  Exploring communities in large profiled graphs.  TKDE, 31(8):1624–1629.
  * Chen et al., (2021) Chen, Y., Zhang, J., Fang, Y., Cao, X., and King, I. (2021).  Efficient community search over large directed graphs: An augmented index-based approach.  In Proceedings of the Twenty-Ninth IJCAI, pages 3544–3550.
  * Cui et al., (2013) Cui, W., Xiao, Y., Wang, H., Lu, Y., and Wang, W. (2013).  Online search of overlapping communities.  In SIGMOD, pages 277–288.
  * Cui et al., (2014) Cui, W., Xiao, Y., Wang, H., and Wang, W. (2014).  Local search of communities in large graphs.  In SIGMOD, pages 991–1002.
  * Dorogovtsev et al., (2006) Dorogovtsev, S. N., Goltsev, A. V., and Mendes, J. F. F. (2006).  K-core organization of complex networks.  Phys. Rev. letters, 96(4):040601.
  * Ebadian and Huang, (2019) Ebadian, S. and Huang, X. (2019).  Fast algorithm for k-truss discovery on public-private graphs.  In IJCAI, pages 2258–2264.
  * (13) Fang, Y., Cheng, R., Chen, Y., Luo, S., and Hu, J. (2017a).  Effective and efficient attributed community search.  VLDB Journal, 26(6):803–828.
  * (14) Fang, Y., Cheng, R., Li, X., Luo, S., and Hu, J. (2017b).  Effective community search over large spatial graphs.  PVLDB, 10(6):709–720.
  * (15) Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., and Lin, X. (2019a).  A survey of community search over big graphs.  VLDB Journal.
  * (16) Fang, Y., Wang, Z., Cheng, R., Wang, H., and Hu, J. (2019b).  Effective and efficient community search over large directed graphs.  TKDE, 31(11):2093–2107.
  * Flake et al., (2000) Flake, G. W., Lawrence, S., and Giles, C. L. (2000).  Efficient identification of web communities.  In SIGKDD, volume 2000, pages 150–160.
  * Fortunato, (2010) Fortunato, S. (2010).  Community detection in graphs.  Physics reports, 486(3-5):75–174.
  * Fortunato and Hric, (2016) Fortunato, S. and Hric, D. (2016).  Community detection in networks: A user guide.  Physics reports, 659:1–44.
  * Giatsidis et al., (2011) Giatsidis, C., Thilikos, D. M., and Vazirgiannis, M. (2011).  D-cores: Measuring collaboration of directed graphs based on degeneracy.  In ICDM, pages 201–210.
  * Hopcroft and Ullman, (1983) Hopcroft, J. E. and Ullman, J. D. (1983).  Data structures and algorithms.
  * Hu et al., (2017) Hu, J., Wu, X., Cheng, R., Luo, S., and Fang, Y. (2017).  On minimal steiner maximum-connected subgraph queries.  TKDE, 29(11):2455–2469.
  * Huang et al., (2014) Huang, X., Cheng, H., Qin, L., Tian, W., and Yu, J. (2014).  Querying k-truss community in large and dynamic graphs.  In SIGMOD, pages 1311–1322.
  * Huang and Lakshmanan, (2017) Huang, X. and Lakshmanan, L. (2017).  Attribute driven community search.  PVLDB, 10(9):949–960.
  * Huang et al., (2015) Huang, X., Lakshmanan, L., Yu, J. X., and Cheng, H. (2015).  Approximate closest community search in networks.  PVLDB, 9(4):276–287.
  * Huang et al., (2016) Huang, X., Lu, W., and Lakshmanan, L. (2016).  Truss decomposition of probabilistic graphs: Semantics and algorithms.  In SIGMOD, pages 77–90.
  * Kim et al., (2010) Kim, Y., Son, S., and Jeong, H. (2010).  Finding communities in directed networks.  Phys. Rev. E, 81(1):016103.
  * Kloumann and Kleinberg, (2014) Kloumann, I. M. and Kleinberg, J. M. (2014).  Community membership identification from small seed sets.  In SIGKDD, pages 1366–1375.
  * Lancichinetti and Fortunato, (2009) Lancichinetti, A. and Fortunato, S. (2009).  Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities.  Phys. Rev. E, 80(1):016118.
  * Leicht and Newman, (2008) Leicht, E. A. and Newman, M. E. (2008).  Community structure in directed networks.  Phys. Rev. letters, 100(11):118703.
  * Li et al., (2015) Li, R., Qin, L., Yu, J., and Mao, R. (2015).  Influential community search in large networks.  PVLDB, 8(5):509–520.
  * Li et al., (2013) Li, R., Yu, J., and Mao, R. (2013).  Efficient core maintenance in large dynamic graphs.  TKDE, 26(10):2453–2465.
  * Malliaros and Vazirgiannis, (2013) Malliaros, F. and Vazirgiannis, M. (2013).  Clustering and community detection in directed networks: A survey.  Physics Reports, 533(4):95–142.
  * Newman and Girvan, (2004) Newman, M. and Girvan, M. (2004).  Finding and evaluating community structure in networks.  Phys. Rev. E, 69(2):026113.
  * Newman, (2004) Newman, M. E. (2004).  Fast algorithm for detecting community structure in networks.  Phys. Rev. E, 69(6):066133.
  * Ning et al., (2016) Ning, X., Liu, Z., and Zhang, S. (2016).  Local community extraction in directed networks.  Phys. A: Statist. Mech. Appl., 452:258–265.
  * Sozio and Gionis, (2010) Sozio, M. and Gionis, A. (2010).  The community-search problem and how to plan a successful cocktail party.  In SIGKDD, pages 939–948.
  * Tarjan, (1979) Tarjan, R. E. (1979).  A class of algorithms which require nonlinear time to maintain disjoint sets.  Journal of computer and system sciences, 18(2):110–127.
  * Yang et al., (2011) Yang, D., Chen, Y., Lee, W., and Chen, M. (2011).  On social-temporal group query with acquaintance constraint.  PVLDB, 4(6):397–408.
  * Yang et al., (2014) Yang, J., McAuley, J., and Leskovec, J. (2014).  Detecting cohesive and 2-mode communities indirected and undirected networks.  In WSDM, pages 323–332.
  * Yang et al., (2010) Yang, T., Chi, Y., Zhu, S., Gong, Y., and Jin, R. (2010).  Directed network community detection: A popularity and productivity link model.  In SIAM, pages 742–753.
  * Ying et al., (2018) Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., and Leskovec, J. (2018).  Graph convolutional neural networks for web-scale recommender systems.  In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974–983.
  * Zhang et al., (2014) Zhang, J., Wang, C., and Wang, J. (2014).  Who proposed the relationship?: recovering the hidden directions of undirected social networks.  In WWW, pages 807–818.