# Efficiently Answering Quality Constrained Shortest Distance Queries in Large
Graphs
††thanks: Xuemin Lin is the corresponding author.

You Peng†, Zhuo Ma†, Wenjie Zhang†, Xuemin Lin‡, Ying Zhang§, Xiaoshuang
Chen††
†The University Of New South Wales,
‡Antai College of Economics & Management, Shanghai Jiao Tong University,
Shanghai, China,
§QCIS, University of Technology, Sydney
††Data Principles (Beijing) Technology Co., Ltd.
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

The shortest-path distance is a fundamental concept in graph analytics and has
been extensively studied in the literature. In many real-world applications,
quality constraints are naturally associated with edges in the graphs and
finding the shortest distance between two vertices $s$ and $t$ along only
valid edges (i.e., edges that satisfy a given quality constraint) is also
critical. In this paper, we investigate this novel and important problem of
quality constraint shortest distance queries. We propose an efficient index
structure based on 2-hop labeling approaches. Supported by a path dominance
relationship incorporating both quality and length information, we demonstrate
the minimal property of the new index. An efficient query processing algorithm
is also developed. Extensive experimental studies over real-life datasets
demonstrates efficiency and effectiveness of our techniques.

###### Index Terms:

Constrained Shortest Distance, Path Queries, Graph Data Management

##  I Introduction

Shortest-path distance is a critical concept in graph analytics [1, 2, 3, 4,
5]. Specially, a path between two vertices $s$ and $t$ is a shortest path if
its length is the shortest among all paths between $s$ and $t$. The distance
of the shortest path is called the shortest-path distance, or shortest
distance for short. Due to its optimality, the notion of the shortest distance
has been exploited to tackle a broad range of problems, including keyword
search [6, 7, 8], betweenness centrality [9, 10] and route planning [11, 12,
13, 14, 15, 16, 17]. The shortest distance between two vertices $s$ and $t$
can reflect the vertices’ significance. For instance, i) in the nearest
keyword search, the vertices closest to the query source are favoured [7]; and
ii) in social networks, distances are employed in the search ranking to aid
users in identifying the most relevant results [18].

Many real-world networks [19, 20] naturally impose a quality constraint over
edges. For instance, in a road network, road segments may specify the weight
limits permitted for auto-trucks. In this scenario, the weight limit is the
quality of edges on road networks, and it is demanded to compute the shortest
path by which an auto-truck can pass. Namely, compute the shortest path and
the distance along which the auto-truck satisfies the quality constraint of
each edge. This motivates us to formulate the quality constraint shortest
distance problem: given query vertices $s$ and $t$ in a graph $G$ and a
quality constraint $w$, the quality constraint shortest distance problem finds
the shortest-path distance where the quality of each edge along the path is at
least $w$. Note that while we present the techniques focusing on the shortest
distance computation, we will show in Section V that our method can also
easily support quality constraint shortest path queries.

Figure 1: A Communication Network. $R_{i}$ indicates the $i^{th}$ router, and
$S_{i}$ indicates the $i^{th}$ switch.

Applications. Below we introduce some motivating applications.

(1) Communication Networks [21]. To achieve end-to-end Quality-of-Service
(QoS) guarantees [22], the transmission of multimedia streams imposes a
minimum-bandwidth requirement on all the links of a path. A quality
constrained shortest distance query can determine the distance (for the
consideration of minimum cost or delay) between two nodes in a network, where
each edge/link has a minimum bandwidth demand of $w$. The resultant path can
handle $w$ bits per second for the transmission of a stream, such as audio or
video, with guaranteed bandwidth. Figure 1 illustrates a motivating example.
Given a minimum speed guarantee such as $3$ Mbps, a query asks for the
distance from $R_{3}$ to $R_{2}$ with such a speed guarantee. In this case,
the resultant distance is $4$ since $R_{3}\rightarrow S_{1}\rightarrow
R_{4}\rightarrow S_{2}\rightarrow R_{2}$ fulfills all the criteria, while
$R_{3}\rightarrow S_{1}\rightarrow R_{2}$ does not owing to the speed of
$S_{1}\rightarrow R_{2}=2$Mbps $<$ $3$Mbps.

(2) Social Networks [18, 23, 24, 25, 26]. In social networks, determining the
closeness of two individuals is a critical issue. A popular metric is the
distance between them in the social networks, e.g., a 2-hop friendship
connection is stronger than a 3-hop one. The strength of connections between
users is indicated based on profile similarity and interaction activity [27,
28] and the distance between users needs to incorporate such strength
information. To support this, a distance query with the quality constraint
identifies the distance with only strong connections.

(3) Biology Networks [29]. Pathway queries are vital in the analysis of
biological networks, where vertices represent the entities, e.g., enzymes and
genes, while edges reflect interactions or relations [29]. As shown in [29],
one of the four important pathway queries in biological networks is to
identify a shortest path between two substances subject to certain
constraints. The quality can derive from the activity of kinase [30, 31]. A
frequently issued query in these biology networks is to determine the shortest
pathway from substance $u$ to transfer to substance $v$, where all the
activities of kinase on this pathway is as least $w$.

Challenges. In real applications, the quality constraint shortest distance
queries can be issued frequently over large-scale graphs. It requires both
real-time response time and scalability. An online BFS-based search needs to
traverse the graph for given query vertices $s$ and $t$, making it impractical
for real scenarios where real-time responses are demanded. 2-hop labelling
approaches are shown to be efficient to support distance queries.
Nevertheless, to deal with the constraints on edge qualities, a naïve adaption
of 2-hop labelling solution involves constructing an index for every possible
quality value $w$ among all edges of the graph. Such a solution is infeasible
since the number of distinct $w$ values can be large. To overcome these
challenges, a modified 2-hop labeling index is designed for the quality
constrained distance problem to fill this research gap. To further accelerate
index construction and query processing, and to reduce index size, this paper
investigates various pruning methods, proposes a query-efficient approach, and
develops efficient vertex ordering strategies. Since these applications
deserve both real-time response time (the online method could not satisfy) and
scalability (the existing index-based method could not satisfy), our proposed
method could cope with all these two challenges.

Novelty. Our approach incorporates an extension to the 2-hop index that takes
advantage of the ordering of weights and distance, and significantly prunes
vertices that would have been processed in a classical 2-hop index while
maintaining index minimality. We also investigated the ordering of BFS
searches and discovered that using vertex degree or tree decomposition can
have different effects on different kinds of networks.

Our Approach. To efficiently answer the quality constrained shortest distance
problem, this work develops a modified 2-hop labeling based index which
possesses soundness, completeness, and minimal properties. We investigate the
BFS search orders in building the index, and propose a quality- and distance-
priority constrained BFS to naturally meet the three properties without
incurring additional costs. The query operation over the index is used not
only in answering the quality constraint distance queries but also in the
index construction phase. We carefully design the query function and achieve
linear time complexity by utilizing a nice dominance property of the problem.
Last, a hybrid vertex ordering is proposed to tackle both graphs with small
and non-small treewidth.

Contributions. Our principal contributions are as follows:

  * •

Theoretical Analysis. First, the quality constrained distance problem is
defined, which has a variety of applications in road networks, social
networks, and biological networks. This paper theoretically analyzes the time
and space complexity of this problem. In addition, it investigates the
soundness, completeness, and minimal properties, and proposes a sophisticated
index capable of naturally preserving these three desirable features.

  * •

Efficient Index. We propose a $2$-hop labeling based index method. Both query-
efficient method and distance-prioritized traversal strategy are presented to
expedite index construction. With a nice property of this problem, the query
function could be implemented in linear time, which could accelerate both
query time and indexing time. Additionally, a hybrid vertex ordering is
investigated. In addition, we investigate how to simply modify our index to
support the quality constraint shortest path problem.

  * •

Comprehensive Experiments. Compared to the baselines, our comprehensive
experiments demonstrate the efficiency and effectiveness of our proposed
method.

Roadmap. The rest of the paper is organized as follows. Section II introduces
some preliminaries and Section III introduces baseline solutions. Our 2-hop
labeling based method is proposed in Section IV. Section V investigates some
extension cases, followed by empirical studies in Section VI. Section VII
surveys important related work. Section VIII concludes the paper.

##  II Preliminaries

###  II-A Problem Definition

Quality ($w$) Constrained Shortest Distance (WCSD) is defined over an
undirected unweighted graph $G(V,E,\Delta,\delta)$, where $V(G)$ denotes the
set of vertices, $E(G)$ denotes the set of edges, $\Delta\subset\mathbb{R}$ is
a set of real-valued qualities, and $\delta:E(G)\rightarrow\Delta$ is a
function that assigns each edge $e\in E(G)$ to a real-valued quality
$w\in\Delta$. For each vertex $u\in V(G)$, $N_{G}(u)=\\{v|(u,v)\in E(G)\\}$
denotes the set of neighbors of $u$, and $deg_{G}(u)$ denotes the degree of
$u$, i.e., $deg_{G}(u)=|N_{G}(u)|$. A path $p$ from the vertex $s\in V(G)$ to
the vertex $t\in V(G)$ is a sequence of vertices $\langle v_{0}\rightarrow
v_{1}\rightarrow\cdots\rightarrow v_{k}\rangle$ such that $s=v_{0}$, $t=v_{k}$
and $(v_{i-1},v_{i})$ is an edge that belongs to $E(G)$ for $\forall i\in[k]$.
The length of $p$, denoted by $len(p)$, is the number of edges included in the
path $p$, i.e., $len(p)=k$. A path between $s$ and $t$ is the shortest if its
length is no larger than any other path between $s$ and $t$, and the distance
between $s$ and $t$ in $G$, denoted by $dist_{G}(s,t)$, is defined as the
length of the shortest path between $s$ and $t$. Table I provides a summary of
the notations used in this paper.

###### Definition 1

($w$-Path) Given a graph $G$ and a threshold $w$, a $w$-path, denoted by
$p_{w}$, is a path in $G$ such that each of its edge has a quality not smaller
than $w$, i.e., $\forall e\in p_{w}$, $\delta(e)\geq w$.

###### Definition 2

($w$-Constrained Distance) Given two vertices $s$ and $t$ in a graph $G$, and
a threshold $w$, the $w$-constrained distance between $s$ and $t$, denoted by
$dist^{w}_{G}(s,t)$, is the minimum length among all the $w$-paths between $s$
and $t$.

For simplify, this paper focuses on the distance first. Once the distance is
found, the quality constrained shortest path can be easily located, and this
extension will be discussed in Section V.

######  Definition 3 (WCSD)

Given two vertices $s$ and $t$ in a graph $G$, and a real-valued threshold
$w$, the WCSD problem is to answer the $w$-constrained distance query, i.e.,
computing the $w$-constrained distance between $s$ and $t$.

Figure 2: An example graph. The values besides edges are their qualities.

###### Example 1

Figure 2 depicts a weighted undirected graph, with the quality of each edge
denoted by the number adjacent to it. In this example, a 1-constrained path
between $v_{0}$ and $v_{8}$ is $\\{v_{0}\rightarrow v_{2}\rightarrow v_{8}\\}$
since each edge on the path has a quality no less than $1$. It is also the
shortest 1-constrained path between $v_{0}$ and $v_{8}$, therefore
$dist_{1}(v_{0},v_{8})=2$. However, $\\{v_{0}\rightarrow v_{2}\rightarrow
v_{8}\\}$ is not a 2-constrained path, since the edge $(v_{0},v_{2})$ has a
quality less than 2. Alternatively, $\\{v_{0}\rightarrow v_{1}\rightarrow
v_{2}\rightarrow v_{8}\\}$ is the shortest 2-constrained path between $v_{0}$
and $v_{8}$, therefore $dist_{2}(v_{0},v_{8})=3$. For vertices $v_{1}$ and
$v_{4}$, the path $\\{v_{1}\rightarrow v_{2}\rightarrow v_{9}\rightarrow
v_{8}\rightarrow v_{5}\rightarrow v_{4}\\}$ is both a 2-constrained path and a
3-constrained path. However, it is not the shortest 2-constrained path as
$\\{v_{1}\rightarrow v_{2}\rightarrow v_{8}\rightarrow v_{5}\rightarrow
v_{4}\\}$ also meets the constraint and has a shorter length.

###  II-B 2-Hop Labeling Framework

Hub Labeling for Distance Queries. Hub labeling [32] is a vital category of
algorithms for distance evaluation. In this class, a label $L(v)$ is computed
for each vertex $v$ s.t. the distance between two vertices $s$ and $t$ can be
obtained by inspecting $L(s)$ and $L(t)$ only, without traversing the graph.
It is NP-hard to generate a labeling with the minimum size [32]. Efficient hub
labeling for road networks is explored in [11, 12]. [33] presents a labeling
scheme that instead employs paths as hubs. Under the assumption of small
treewidth and bounded tree height, [34] proposed a scheme combining both hub
labeling and hierarchy for road networks. Pruned landmark labeling (PLL) [35]
is the state-of-the-art for real graphs, and its various extensions have been
devised. For instance, [36] proposed an external algorithm that generates the
same set of labels; [37] devised a parallel algorithm; and [38] describes an
algorithm that updates the labels as new edges are inserted into the graph.
[39] conducted an experimental study on hub labeling for distance queries.

TABLE I: Summary of Notations
---
Notation | Definition
$G$ | a weighted unordered graph
$V(G)$ | a set of vertices
$E(G)$ | a set of edges
$\Delta$ | a set of real-valued qualities
$\delta$ | a function that assigns edges to a quality
$d$ | a distance value
$w$ | a quality value
$|w|$ | number of distinct values of edge qualities
$N_{G}(u)$ | neighbour set of $u$
$p$ | a path
$p_{w}$ | a $w$ path
$len(p)$ | number of edges included in path $p$
$dist_{G}(s,t)$ | distance between $s$ and $t$ in $G$
$dist^{w}_{G}(s,t)$ |  $w$-distance between $s$ and $t$ in $G$
$\mathcal{L}$ | WC-INDEX of $G$
$\mathcal{L}(u)$ | label set of $u$ in $\mathcal{L}$
$I$ | an index entry in the form of $(v,d,w)$
$R(u)$ | vector that records the current largest $w$
| of all paths from $v$ to all other vertices

##  III Baseline Solutions

###  III-A Basic Online and Indexing Approaches

BFS-based Online Approaches. A naïve online approach is to conduct a
constrained breadth first search, which filters out-edges with quality values
lower than the constraint $w$. The time and space complexity is both
$O(|V|+|E|)$. Alternative algorithms such as Dijktra can also be performed.
Another solution is to partition the original graph according to the values of
quality, then it can perform constrained BFS on the corresponding partition.
On large graphs, none of these online approaches is efficient in terms of
query time. These algorithms are evaluated as baselines in the experiments.

Details. Algorithm 1 depicts the BFS-based online computation. Line 1
initializes the arrays $dis$ and $visited$. Line 1 initializes the search
queue with the vertex $s$, and set $visited[s]=true$. Lines 1 to 1 constitute
the search procedure. In each iteration, $size$ is set as the current size of
$P$ and $dis=dis+1$ in Line 1. Then, all the vertices are traversed in Line 1
according the to vertex order. For vertex $u$ in $P$, each vertex $v$ in its
neighbors is explored, and it will be pruned in Line 1 if $e(u,v)<w$ or
$visited[v]$. Line 1 returns the $dis$ if explores $t$. Otherwise, $w$ is
added into the $P$ and set $visited[v]=true$ to prevent duplication of
candidates. $INF$ is returned in Line 1 if not reach $t$.

Input : any two vertices $s,t\in V$, and constraint $w$;

Output : $dist^{w}$ between $s$ and $t$

1 $dis=0$, $\forall v\in V,visited[v]=false$ $P.push((s))$, $visited[s]=true$;

2 while $P\neq\emptyset$ do

3 $size\leftarrow P.size()$, $dis=dis+1$;

4 for $\forall i\in\\{1,..,size\\}$ do

5 $(u)\leftarrow P.pop()$;

6 for $\forall v\in adj[u]$ do

7 if $e(u,v)<w$ or $visited[v]$ then

8 Continue;

9

10 if $v==t$ then

11 Return $dis$;

12

13 $P.push(v)$, $visited[v]=true$;

14

15

16

17 return $INF$;

Algorithm 1 WC-BFS

2-hop Labeling Approach. 2 hop-labeling approaches have been proven to be
effective for addressing shortest path problems [34, 35]. 2-hop indexes store
the distance between vertices that has been precomputed. Each vertex $u\in V$
has its own label consisting of the form $(v,d)$, where $v$ is another vertex
in the graph and $d$ is the distance from $u$ to $v$. To obtain the distance
from vertex $s$ to vertex $t$, common vertices are identified in the labels of
both $s$ and $t$, calculate the distance as the sum of their respective
distance to $w$, and return the minimum sum of distances.

Naïve 2-hop labeling method for WCSD. A naïve 2-hop labeling solution involves
filtering the graph based on edge qualities and constructing a classical 2-hop
labeling index for each filtered graph. $|w|$ is used to denote the number of
distinct values of edge qualities. Thus, $|w|$ 2-hop indices will be
constructed, each containing only edges satisfying $\forall e\in
E,\delta(e)\geq w$. Given a query $(s,t,w_{0})$, it can be answered by using
the classical 2-hop labeling method by a simple set intersection operation for
the corresponding index with $w_{0}$. This approach becomes infeasible since
the space required to store all of the indices grows as the graph sizes and
$|w|$ increase. Moreover, in some instances, e.g., communication networks, the
edge qualities are not integers. In such a scenario, it is impossible to
create the naïve 2-hop labeling for every possible value of $w$. The time
complexity of the naïve method is $O(|V|\cdot(|V|+|E|)\cdot|w|)$. The space
complexity is $O(|V|\cdot|V|\cdot|w|)$ since the number of induced graphs is
$|w|$, and in each of them, every vertex could store $|V|$ label entries in
the worst case.

##  IV Index Construction

###  IV-A Our proposed 2-hop Labeling Index-based Approach

The naïve approach can answer queries efficiently. Nevertheless, it needs to
construct $|w|$ distinct 2-hop indices, which is inefficient and space-
consuming. It becomes prohibitive to construct and maintain such a vast number
of indices when $|w|$ is large.

###### Observation 1

By building $|w|$ 2-hop labeling indexes, one may notice that numerous entries
in the separate indices are redundant and elimination of those redundant
entries does not impair the correctness of the queries. In this section, a
modified 2-hop indexing approach is proposed which seeks to build only one
index while efficiently supporting quality constrained shortest distance
queries.

Before providing this approach, the concept of path dominance is firstly
described.

###### Definition 4

(Path Dominance) Given two vertices $s$ and $t$ in a graph $G$, as well as two
$w$-paths from $s$ to $t$, i.e., $p_{w_{1}}$ and $p_{w_{2}}$, $p_{w_{1}}$
dominates $p_{w_{2}}$ if $len(p_{w_{1}})\leq len(p_{w_{2}})$ and $w_{1}\geq
w_{2}$.

###### Definition 5

(Minimal Path) A $w$-path $p_{w}$ is a minimal path if it cannot be dominated
by any other $w$-path.

###### Example 2

An example is illustrated in Figure 3. For paths between vertices $v_{0}$ and
$v_{4}$, path $\\{v_{0}\rightarrow v_{3}\rightarrow v_{4}\\}$ with length $2$
dominates path $\\{v_{0}\rightarrow v_{3}\rightarrow v_{5}\rightarrow
v_{4}\\}$ with length $3$, since the two paths have the same minimum edge
quality of $1$ and the length of $\\{v_{0}\rightarrow v_{3}\rightarrow
v_{4}\\}$ is smaller. For paths between vertices $v_{1}$ and $v_{3}$,
$\\{v_{1}\rightarrow v_{2}\rightarrow v_{3}\\}$ with a minimum edge quality of
$4$ dominates $\\{v_{1}\rightarrow v_{0}\rightarrow v_{3}\\}$ with a minimum
edge quality of $1$, while both have the same length of $2$. Likewise,
$\\{v_{1}\rightarrow v_{3}\\}$ dominates $\\{v_{1}\rightarrow v_{0}\rightarrow
v_{3}\\}$ due to both length and minimum edge quality. Path
$\\{v_{0}\rightarrow v_{3}\rightarrow v_{4}\\}$ is the minimal $1$-path
between $v_{0}$ and $v_{4}$, because it cannot be dominated by any other
paths. Also, $\\{v_{1}\rightarrow v_{2}\rightarrow v_{3}\\}$ is both the
minimal $3$-path and minimal $4$-path between $v_{1}$ and $v_{3}$.

In this paper, the dominance relationship between paths is leveraged and a
single compact 2-hop index is generated, which is capable of answering queries
regarding arbitrary quality constraint $w$. The WC-INDEX index is defined as
follows:

###### Definition 6

(WC-INDEX) Given an undirected weighted graph $G$, a WC-INDEX $\mathcal{L}$ of
$G$ assigns a label set $\mathcal{L}(u)$ to each vertex $u\in V(G)$. An index
entry $(v,dist^{\bar{w}}_{G}(u,v),\bar{w})\in\mathcal{L}(u)$ indicates that
there exists a minimal $\bar{w}$-path between $u$ and $v$, and it also records
the corresponding $\bar{w}$-constrained distance $dist^{\bar{w}}_{G}(u,v)$
between them.

TABLE II: WC-INDEX of Figure 3

Vertex | $L(\cdot)$
---|---
$v_{0}$ | $(v_{0},0,\infty)$
$v_{1}$ | $(v_{0},1,3),(v_{1},0,\infty)$
$v_{2}$ | $(v_{0},2,3),(v_{1},1,5),(v_{2},0,\infty)$
$v_{3}$ |  $(v_{0},1,1),(v_{0},2,2),(v_{0},3,3),(v_{1},1,2),(v_{1},2,4),(v_{2},1,4),$ $(v_{3},0,\infty)$
$v_{4}$ |  $(v_{0},2,1),(v_{0},3,2),(v_{0},4,3),(v_{1},2,2),(v_{1},3,4),(v_{2},2,4),$ $(v_{3},1,4),(v_{4},0,\infty)$
$v_{5}$ |  $(v_{0},2,1),(v_{0},3,2),(v_{0},5,3),(v_{1},2,2),(v_{1},4,3),(v_{2},2,2),$ $(v_{2},3,3),(v_{3},1,2),(v_{3},2,3),(v_{4},1,3),(v_{5},0,\infty)$

Query processing with WC-INDEX. Given a complete WC-INDEX $\mathcal{L}$ of
$G$, for any two vertices $s,t\in V(G)$ and an arbitrary real-value
$w\in\mathbb{R}$, query $Q(s,t,w)$ computes the $w$-constrained distance
between $s$ and $t$ as:

$dist^{w}_{G}(s,t)=\min_{\begin{subarray}{c}u\in\mathcal{L}(s)\cap\mathcal{L}(t)\\\
w_{1},w_{2}\geq w\end{subarray}}dist^{w_{1}}_{G}(s,u)+dist^{w_{2}}_{G}(u,t)$
(1)

Input : any two vertices $s,t\in V$, and constraint $w$;

Output : $dist^{w}$ between $s$ and $t$

1 $dist^{w}\leftarrow\infty$;

2 for every index entry $I_{i}$ in $L(s)$ do

3 if $I_{i}.quality\geq w$ then

4 for every index entry $I_{j}$ in $L(t)$ such that
$I_{j}.vertex=I_{i}.vertex$ do

5 if $I_{j}.quality\geq w$ then

6 if $I_{i}.dist+I_{j}.dist<dist^{w}$ then

7 $dist^{w}\leftarrow I_{i}.dist+I_{j}.dist$

8

9

10

11

12return $dist^{w}$;

Algorithm 2 Query Algorithm Figure 3: A running example.

###### Example 3

Figure 3 illustrates how these 2-hop labeling index works. Given a query
$Q(v_{2},v_{5},2)$, $L(v_{2})$ and $L(v_{5})$ are explored. This example
starts with the first entry of $L(v_{2})$, $(v_{0},2,3)$, and discover that it
satisfies the quality constraint of $2$. In the following, entries in
$L(v_{5})$ are explored that share the same vertex $v_{0}$ and also satisfy
the quality constraint. $(v_{0},3,2)$ is the first constraint-satisfying entry
in $L(v_{5})$. Therefore, $dist^{2}=2+3=5$ is obtained. The next entry
$(v_{0},4,3)$ also satisfies the constraint. Nevertheless, since the resultant
distance $dist^{2}=2+4=6$ is larger than the previous distance obtained, no
update is performed and $dist^{2}$ remains as $5$. It then moves on to the
second entry of $L(v_{2})$ which satisfies the constraint: $(v_{1},1,5)$. In
$L(v_{5})$, label entries $(v_{1},2,2)$ and $(v_{1},4,3)$ are found
satisfactory and subsequently update the distance as $dist^{3}=1+2=3$. Lastly,
it visits $(v_{2},0,\infty)$ in $L(v_{2})$ and finds $(v_{2},2,2)$ in
$L(v_{5})$, resulting in $dist^{2}=0+2=2$.

(a) The $1^{st}$ iteration.

(b) The $2^{nd}$ iteration.

(c) The $3^{rd}$ iteration.

(d) The $4^{th}$ iteration.

(e) The $5^{th}$ iteration.

(f) The $6^{th}$ iteration.

Figure 4: The constrained BFS process for $v_{0}$.

###  IV-B Distance-Prioritized Search Order

The whole index construction process consists of $|V|$ iterations’ constrained
BFS starting from different vertices. In each constrained BFS, it will explore
at most $|V|$ vertices, but each vertex will be touched at most once. The
order of these $|V|$ iterations’ starting vertex is named Vertex Order, while
in $i$-th constrained BFS starting from vertex $v_{i}$, the order to explore
remaining vertices is called the search Order of $v_{i}$. These two types of
orders are crucial for indexing time, indexing size, and query time in the
2-hop based index.

Below we introduce three properties that we aim to preserve for WC-INDEX.
Then, a smart search order is proposed to guarantee these three properties at
no additional cost, particularly the minimal property.

  * •

Soundness. If there are two index entries $(v,d_{1},w_{1})\in L(s)$ and
$(v,d_{2},w_{2})\in L(t)$ with $w_{1}\leq w_{2}$ ($w_{2}\leq w_{1}$), then
there exists a quality constrained path from $s$ to $t$ with distance
$d_{1}+d_{2}$ that satisfies quality constraint $w\leq w_{1}$ ($w_{2}$).

  * •

Completeness. If there is a quality constrained shortest path $P_{0}$ from $s$
to $t$ with distance $d$, and satisfying quality constraint $w$
($w=min(w(e)|e\in P_{0})$), then there exist either two label entries
$(v,d_{1},w_{1})\in L(s)$ and $(v,d_{2},w_{2})\in L(t)$. If
$w=min(w_{1},w_{2})$, then $d_{1}+d_{2}=d$ and $w=w$, or single label entry
such as $(s,d,w)$ $\in L(t)$ or $(t,d,w)$ $\in L(s)$.

  * •

Minimal. Intuitively, the minimal property indicates that any deletion of the
existing label entries will cause incorrect results for some queries. This
property is formulated as follows: For a vertex $u$, an entry
$I=(v,d_{1},w_{1})$ is minimal if $I$ is not dominated by any other entries in
$L(u)$; that is, there is no entry $I^{\prime}=(v,d_{2},w_{2})\in L(v)$ s.t.
$d_{2}\leq d_{1}$, and $w_{2}\geq w_{1}$. An index entry $I=(v,d_{1},w_{1})$
is necessary if there does not exist a vertex $u_{0}$ s.t.
$(u_{0},d_{0},w_{0})\in$ $L(s)$ and $(u_{0},d_{0}^{\prime},w_{0}^{\prime})\in$
$L(t)$ where $d_{0}+d_{0}^{\prime}\leq d_{1}$ and
$min(w_{0},w_{0}^{\prime})\geq w_{0}$. Then, a WC-INDEX is minimal if every
index entry in it is both minimal and necessary.

To efficiently construct the WC-INDEX, the dominance relationships between
edge qualities are exploited. Utilizing path domination, pruning is performed
by traversing vertices in a certain order. To optimize the number of path
traversals that are pruned throughout the index construction process, the
following priority-based search orders are strictly adhered:

  1. 1.

Distance order. Computing the index entries with smaller distance $d$ first;

  2. 2.

Quality order. When tackling one specific $d$ value, explore the entries with
the largest quality value $w$ first.

Based on the above processing order, the WC-INDEX is constructed using BFS
traversals from each vertex. Consider the BFS process from vertex $v\in V$.
The maximum $w$ value of paths from $v$ to all other vertices are recorded.
During each iteration of BFS expansion, it will be determined whether the
visited vertices, say $u$, can be reached from $v$ by an existing path that
dominates the current path, where an existing path is a path indicated by the
current index entries. If the current path from $v$ to $u$ is dominated by an
existing path, $u$ is pruned from the BFS process. Otherwise, the
corresponding index entries are added into the WC-INDEX. Before moving onto
the next iteration, all paths are processed from this iteration of expansion.
Therefore, it is guaranteed that the index entries added in this iteration
will not be dominated by any other entries.

Input : a graph $G$, and a vertex order $\mathcal{O}$;

Output : the constructed 2-hop index $\mathcal{L}$

1 $\mathcal{L}(v)\leftarrow\\{(v,0,\infty)\\}$ for all $v\in V(G)$;

2 for $k=1,2,\cdots,n$ do

3 $v_{k}\leftarrow$ the $k$-th vertex in $\mathcal{O}$;

4 $R(v)\leftarrow 0$ for all $v\in V(G)$;

5 $P\leftarrow$ an empty queues;

6 $P.push((v_{k},0,\infty))$;

7 while $P\neq\emptyset$ do

8 $vec\leftarrow\emptyset$;

9 while $P\neq\emptyset$ do

10 $(u,d,w)\leftarrow P.pop()$;

11 if Query$(v_{k},u,w,\mathcal{L})\leq d$ then continue;

12 else $\mathcal{L}_{k}(u)\leftarrow\mathcal{L}_{k}(u)\bigcup(v_{k},d,w)$;

13 foreach $v_{i}\in N_{G}(u){:O(v_{i})>O(v_{k})}$ do

14 $w^{\prime}\leftarrow\min(\delta(e=(u,v_{i})),w)$;

15 if $w^{\prime}\leq R(v_{i})$ then continue;

16 $vec\leftarrow vec\bigcup\\{v_{i}\\}$; $R(v_{i})\leftarrow w^{\prime}$;

17

18

19 foreach $w\in vec$ do $P.push(v_{i},d+1,R(v_{i}))$;

20

21

22return $\mathcal{L}$;

Algorithm 3 WC-Index Construction

Details. The algorithm for constructing WC-INDEX is shown in Algorithm 3.
Given graph $G$ and a vertex order $O$, this algorithm constructs the WC-INDEX
$L$, which consists of entry sets $L(v)$ for every $v\in V$. Each entry set
$L(v)$ is initialized as a set that contains only one entry, which corresponds
to $v$ itself (Line 3). Then, BFS is executed for all $v_{k}\in V$ following
the specified order. A vector $R(v)$ of size $|V|$ is used to record the
current largest $w$ value of all paths from $v$ to all other vertices in the
graph, with values set to 0 (Line 3). The maximum $w$ value from $v_{k}$ to
$u$ is denoted as $w_{max}^{u}$. A queue $P$ is used to store tuples in the
form of $(u,d,w)$, where $u$ is a vertex visited in the previous round of BFS,
$d$ is the associated BFS path length, and $w$ is the minimum edge quality of
that path. $P$ is initialized to contain a single element of
$(v_{k},0,\infty)$ (Line 3). The BFS process from $v_{k}$ is described in Line
3-3 of Algorithm 3.

During each iteration of BFS expansion, for each entry in queue $P$, a query
is performed on the $w$-constrained path from $v_{k}$ to $u$ using the current
index constructed so far (Line 3). This entry will be pruned if the result
$w$-constrained distance from the query is smaller than the current BFS
distance $d$. If not, the entry is appended to the index (Line 3). Then, for
each $v_{i}\in N(u)$, it will determine whether $v_{i}$ can be reached from
$v$ by an alternative path with a greater $w$ value (Line 3-3). This is
determined by comparing the current $w$ to $w_{max}^{v_{i}}$. If
$w<w_{max}^{v_{i}}$, then $w$ is pruned from the BFS process. Otherwise,
$v_{i}$ is added to a temporary set, and update $w_{max}^{v_{i}}$ with the
value $w$. After all neighbors of $u$ have been processed, all temporary queue
entries are pushed into $P$ to be processed in the next expansion iteration,
with a distance of one step further from $v_{k}$ (Line 3). Thus, the algorithm
ensures that for each $v_{i}$ only one path with the greatest $w$ will be
considered in the next iteration. After all potential entries are popped from
$P$, the process is repeated on this queue for the following round of BFS. The
entire BFS from $v_{k}$ ends when $P$ is empty. The construction of WC-INDEX
index finishes, after performing BFS for all $v\in V$.

###### Example 4

Figure 4 illustrates how the Algorithm 3 operates for the vertex $v_{0}$ in
Figure 3. $R(v)\leftarrow 0$ for every $v\in V(G)$ and $R(v_{0})=\infty$.
Figure 4a investigates the neighbors of $v_{0}$, i.e., $v_{1}$ and $v_{3}$.
Then, $R(v_{1})=3$ and $R(v_{3})=1$. In addition, $P$ is updated to include
the newly added vertices $v_{1}$ and $v_{3}$. Figure 4b indicates that
$v_{2},v_{3},v_{4}$, and $v_{5}$ will be explored. It is noted that $v_{3}$ is
updated into $P$ again since in the round, $R(v_{3})$ is updated with a larger
value, i.e., $2$. Likewise, in Figure 4c, $v_{3},v_{4}$ and $v_{5}$ are
inserted into $P$ due to their updated $R$ values. In Figure 4d, only $v_{4}$
is inserted into $P$ and $R(v_{4})$ is updated with $3$ since a path
$v_{0}\rightarrow v_{1}\rightarrow v_{2}\rightarrow v_{3}\rightarrow v_{4}$ is
found. In this path, the minimal quality is $e(v_{0},v_{1})=3$. Figure 4e
depicts the updates for $v_{5}$ with only $v_{5}$ being inserted into $P$ and
$R(v_{5})$ being updated with value $3$. This is the result of the newly found
path $v_{0}\rightarrow v_{1}\rightarrow v_{2}\rightarrow v_{3}\rightarrow
v_{4}\rightarrow v_{5}$. Figure 4f illustrates the last iteration. The
constrained BFS for $v_{0}$ terminates at this iteration since there is no
update for any vertex. For every triple inserted into $P$, the corresponding
label entry is inserted into $L(v_{0})$.

###### Lemma 1

In Algorithm 3, for each candidate index entry popped by the queue (Line 3),
it cannot be dominated by all the candidate index entries popped by the queues
afterwards.

###### Proof 1

Since for each iteration of BFS expansion, all entries in queue $P$ are
popped, and then new entries are added back to this queue $P$. Then, this
queue can only contain entries with the same $d$ at a given moment. For vertex
$u$ in a certain BFS iteration, if $u$ already exists in the temporary set,
which indicates there is an existing path from $v_{k}$ to $u$ with
$w_{max}^{u}$. If the current path induces an entry with $w>w_{max}^{u}$,
$w_{max}^{u}$ is updated to be $w$. Otherwise, nothing happens. Consequently,
$w$ will only exist once in the temporary set, and will only be pushed into
queue $P$ once, with $w=w_{max}^{u}$, which is the maximum $w$ value at
distance $d$. Any future entries in $P$ regarding $u$ will include a larger
$d$. Therefore, popped entries will never be dominated by future entries in
the queues.

Correctness of Algorithm. Then, the correctness of the algorithm is proved by
its Soundness and Completeness. Additionally, the Minimal properties is
proved.

###### Theorem 1

Algorithm 3 can construct a Sound, Complete, and Minimal index for WCSD
problem.

###### Proof 2

First, the Soundness and Completeness are demonstrated. These two
characteristics are equivalent to the correctness of Algorithm 3.

Soundness. It is proved by contradiction. Assume there are two index entries
$(v,d_{1},w_{1})\in L(s)$ and $(v,d_{2},w_{2})\in L(t)$ with $w_{1}\leq w_{2}$
($w_{2}\leq w_{1}$), and there does not exist a quality constrained path from
$s$ to $t$ with distance $d_{1}+d_{2}$ and satisfy quality constraint $w\leq
w_{1}$ ($w_{2}$). According to the index construction process, there are two
quality constrained shortest paths. The first is $s\rightsquigarrow v$ with
distance $d_{1}$ and quality constraint $w_{1}$, whereas the second is
$v\rightsquigarrow t$ with distance $d_{2}$ and quality constraint $w_{1}$.
Therefore, it can be combined to produce a new path $P_{new}$. Note that
soundness simply requires a quality constraint path; it does not have to be
shortest.

Completeness. Similarly, the Completeness is demonstrated by contraction.
Assume that there is a quality constrained shortest path from $s$ to $t$ with
distance $d$, satisfying quality constraint $w$, then there does not exist
either two label entries $(v,d_{1},w_{1})\in L(s)$ or $(v,d_{2},w_{2})\in
L(t)$. If $w=min(w_{1},w_{2})$, then $d_{1}+d_{2}=d$, nor one label entry like
$(s,d,w)$ $\in L(t)$ or $(t,d,w)$ $\in L(s)$. Assume $s$ is explored before
$t$111The proof process is similar if $t$ is the earlier one. and $s$ is the
first vertex that leads to such incorrectness, and $s,t$ is the first vertex
pair to lead the incorrectness. This indicates that the Completeness of all
the previously explored vertices is maintained. Consequently, according to
Algorithm 3 Line 3, if the $Query(s,t,w)$ is pruned, then it indicates that
there exist two label entries $(v,d_{1},w_{1})\in L(s)$ and
$(v,d_{2},w_{2})\in L(t)$. If $w=min(w_{1},w_{2})$, then $d_{1}+d_{2}=d$.
Otherwise, the label entry $(s,d,w)$ is inserted into $L(t)$ in accordance
with Algorithm 3 Line 3.

Minimal. According to Algorithm 3 Line 3, a newly added label entry is Minimal
when it is inserted into the index. Therefore, it is only necessary to prove
it will not be dominated in the label entries that are inserted after it. Due
to the distance order, quality order, and Definition 4, this property is
automatically maintained.

###### Theorem 2

The index constructed by Algorithm 3 is capable of producing correct results.

###### Proof 3

Theorem 1 proves the Soundness and Completeness of constructed index. Thus,
its correctness is immediately proved.

Complexity Analysis. The while loop dominates the time complexity of indexing
from the vertex $v_{k}$. Let $I(v)$ denote all the index entries associated
with $v$ and let $\zeta=\max\limits_{v\in V(G)}|I(v)|$. Let $d_{max}$ denote
the maximum vertex degree in the graph. Observe that in Algorithm 3, Lines 3-3
are executed at most $\zeta$ times, hence the size of the priority queue
cannot exceed $\zeta d_{max}$. For each index entry in the queue, a query
operation is performed to determine whether it can be covered by the existing
index entries, and the query time is bounded by $O(\zeta)$. As a result, the
time complexity of Algorithm 3 is $O(n\cdot\zeta\cdot d_{max}(\log\zeta\cdot
d_{max}+\zeta))$.

The size of the index is bounded by $O(\sum_{u\in V(G)}\sum_{v\in V(G)_{\leq
u}}min(D,|w|)).$

###  IV-C Query-Efficient Implementation

Since the $Query$ function is commonly utilized during the index construction
and query stages, it is a vital component that influences three aspects of the
index: indexing time, index size, and query time. This subsection investigates
how to efficiently implement the $Query$ function by utilizing the problem’s
property.

Given a query$(s,t,d,w)$, a basic operation is to determine whether there are
two label entries $(u_{1},d_{1},w_{1})$ and $(u_{2},d_{2},w_{2})$ with
$u=u_{1}=u_{2}$, $d_{1}+d_{2}\leq d$, $w_{1}\geq w$, and $w_{2}\geq w$.

Input : any two vertices $s,t\in V$, constraint $w$, and current distance $d$;

Output : a boolean value indicating if a path is found

1 for $\forall I_{j}$ $\in$ $L[t]$ do

2 if $I_{j}.vertex>s$ or $I_{j}.quality<w$ then

3 continue;

4 $v=I_{j}.vertex$;

5 if $L[s][v]=\emptyset$ then

6 continue;

7 for $\forall I_{i}$ $\in$ $L[s][v]$ do

8 if $I_{i}.quality\geq w$ then

9 if $I_{i}.dist+I_{j}.dist<=d$ then

10 return $True$;

11

12

13

14

15return $False$;

Algorithm 4 $Query$

Naïve Implementation. For simplicity, $L[u]$ denotes all the label entries of
vertex $u$, and $L[u][v]$ denotes all the label entries as $(v,d_{v},w_{v})$
in $L[u]$. The naïve query function is represented by Algorithm 4. Line 4
traverses every label entry in the $L[t]$. Assume a label entry is $I_{j}$,
Line 4 prunes it if its vertex order is larger than $s$ or $quality$ is less
than the quality constraint. Otherwise, entries of $L[s][v]$ are explored,
where $v$ is the vertex of $I_{j}$, and validate whether there are two valid
label entries $I_{j}$ and $I_{i}$ to return a $true$ result. The time
complexity of this implementation is $O(|L(s)|+|L(t)|+\sum_{v\in
L[t].vertex}{|L[t][v]|\times|L[s][v]|})$.

The following theorem helps speed up this procedure.

###### Theorem 3

For two label entries $(u_{0},d_{0},w_{0})$ and $(u_{0},d_{1},w_{1})$ in
$L(v)$, if $d_{0}>d_{1}$, then $w_{0}>w_{1}$, and vice versa.

###### Proof 4

This theorem is proved by contradiction. Assume that there are two label
entries $(u_{0},d_{0},w_{0})$, and $(u_{1},d_{1},w_{1})$, s.t. $d_{0}>d_{1}$
and $w_{0}\leq w_{1}$. According to Lemma 1, $(u_{0},d_{0},w_{0})$ will be
eliminated since it is dominated by $(u_{1},d_{1},w_{1})$, which results in a
contradiction. Likewise, a similar contradiction exists when $w_{0}>w_{1}$
with $d_{0}\leq d_{1}$.

Querying. During the BFS process for one vertex $v_{k}$, it is noted that all
queries are issued with one end-point as $v_{k}$. Therefore, an array $T$ of
size $|V|$ is initialized with the existing index entry of that $v_{k}$ before
the BFS begins. To evaluate $QUERY(u,v_{k})$, the new querying algorithm needs
$O(|L(u)|)$ time rather than $O(|L(u)|)+O(|L(v_{k})|)$ for looping through two
entry lists.

Based on Theorem 3, the index entries $(d_{i},w_{i}),i=1,2,...,|L(v)|$ for
vertex $v\in V$ must be in increasing order in terms of $d$ and $w$. If $j>i$,
then both $d_{j}>d_{i}$ and $w_{j}>w_{i}$. Instead of iterating through $T$,
binary search could be utilized to locate elements. Then, in such an
implication, the time complexity is $O(|L(s)|+|L(t)|+\sum_{v\in
L[t].vertex}{|L[t][v]|\times log|L[s][v]|})$.

Query-Efficient Implementation. Based on Theorem 3, the time complexity can be
further reduced to $O(|L(s)|+|L(t)|)$. The idea is explained as follows: Since
the index entries $(d_{i},w_{i}),i=1,2,...,|L(v)|$ for vertex $v\in V$ must be
in ascending order in terms of $d$ and $w$, if finding the first index entry
$(u_{i},w_{i},d_{i})$ whose $w_{i}\geq w$, $d_{i}$ is minimal for
$(u_{i},\cdot,\cdot)$. Thus, for every $v\in L(s)$ or $L(t)$, only one label
entry is required. Then, a naïve scanning could be conducted to answer the
queries. The time complexity is $O(|L(s)|+|L(t)|+\sum_{v\in
L[t].vertex}{(log|L[t][v]|+log|L[s][v]|)})$. Since $\sum_{v\in
L[t].vertex}{(log|L[t][v]|+log|L[s][v]|)}$ $\leq$ $|L(s)|+|L(t)|$, the final
time complexity is $O(|L(s)|+|L(t)|)$.

Details. The details of the Query-Efficient Implementation is illustrated in
Algorithm 5. Line 5 traverses every vertex $v\in L(t)$. Line 5 prunes if
$L[s][v]=\emptyset$. If not empty, a modified binary search is utilized to
locate the first label entry with $w_{i}\geq w$ in $L[t][v]$ and $w_{j}\geq w$
in $L[s][v]$, respectively. $true$ is immediately returned if $d_{1}+d_{2}\leq
d$ in Line 5. Otherwise, the query answer is $false$ in Line 5;

Input : any two vertices $s,t\in V$, constraint $w$, and current distance $d$;

Output : a boolean value indicating if a path is found

1 for $\forall$ vertex $v$ $\in$ $L[t]$ do

2 if $L[s][v]=\emptyset$ then

3 continue;

4 Find $I_{i}\in L[t][v]$ which is the first label entry with $w_{i}\geq w$;

5 Find $I_{j}\in L[s][v]$ which is the first label entry with $w_{j}\geq w$;

6 if $d_{i}+d_{j}\leq d$ then

7 return $True$;

8

9return $False$;

Algorithm 5 $Query^{+}$

Efficient Initialization. An important aspect is to avoid $O(n)$ time
initialization for data structures during each round of BFS. This may develop
into a bottleneck. A solution is to set updated values in the array, without
recreating the whole array. This can be accomplished by recording which
vertices have been processed during the process, and only update them.

Further Pruning. Whenever a path is found during the query process of index
construction, the algorithm records the result for the current quality of that
vertex pair. If a potential query in the same BFS round has the same vertex
pair and a quality not greater than the recorded quality, the query process
can be skipped since its result is recorded.

###  IV-D Vertex Ordering Strategies

Vertex ordering is one of the vital orders that significantly affect indexing
time, index size, and querying time. This subsection investigates a hybrid
vertex ordering based on some observations.

###### Observation 2

The degree ordering is shown to have better performance than other orderings
[35] for the shortest path distance problem in the scale-free network, e.g.,
social networks. Notwithstanding, for the road network
“Indochina”222http://law.di.unimi.it, the tree decomposition based ordering
has much better performance.

###### Observation 3

It is shown in [34] that Vertex Hierarchy via Tree Decomposition technique is
appropriate for the road network for distance query.

To use the Observation 3, it first introduces the degree-based ordering as
well as the Vertex Hierarchy through Tree Decomposition.

Degree-Based Scheme. A vertex with a higher degree is likely to cover more
shortest paths. In summary, in degree-based ordering, vertices are sorted in
non-ascending order of degree. This scheme leads to the state-of-the-art
canonical hub labeling for shortest distance queries.

Tree Decomposition Ordering. Tree decomposition is a technique for mapping a
graph to a tree in order to accelerate the resolution of certain computational
problems in graphs [40, 41]. Numerous algorithmic problems, such as maximum
independent set and Hamiltonian circuits that are NP-complete for arbitrary
graphs, can be solved efficiently by dynamic programming for graphs of finite
treewidth, employing the tree-decompositions of these graphs. A summary of
Bodlaender’s introduction can be found in [42]. The tree decomposition
provides a natural hierarchy to vertices. In this paper, tree decomposition is
utilized to establish the vertex hierarchy, and demonstrate that the hierarchy
is effective in resolving quality constrained distance queries in networks. A
tree decomposition of a graph $G(V,E)$ is defined as follows [42]:

######  Definition 7 (Tree Decomposition)

A tree decomposition of a graph $G(V,E)$, denoted by $T_{G}$, is a rooted tree
in which each node $X\in V(T_{G})$ is a subset of $V(G)$ (i.e., $X\subset
V(G)$) with the following three conditions:

  * •

$\bigcup_{X\in V(T_{G})}X=V$;

  * •

For every $(u,v)\in E(G)$, there exists $X\in V(T_{G})$ s.t. $u\in X$ and
$v\in X$.

  * •

For every $v\in V(G)$ the set $\\{X|v\in X\\}$ forms a connected subtree of
$T_{G}$.

Based on Observations 2 and 3, it simply employed vertex ordering of the
Vertex Hierarchy via Tree Decomposition in [34] and developed a fast approach
to obtain this ordering as opposed to constructing their whole index for the
WCSD problem.

The computation of the treewidth of a graph has been shown to be NP-Complete
[43]. One of the most effective heuristics Tree decomposition is based on
minimum degree elimination.

Minimum Degree Elimination (MDE)-based Tree Decomposition. Minimum Degree
Elimination [44] based tree decomposition removes recursively the vertex $v$
in $G$ with the minimum degree and then adds $v$’s neighbors’ clique back to
$G$. A bag of the tree decomposition is comprised of each node $v$ and its
neighbors on the transient graph right before the deletion of $v$.

######  Definition 8 (Minimum Degree Elimination)

Generate $n$ bags of nodes $\\{B_{1},B_{2},...,B_{n}\\}$ and a sequence of
nodes $\\{v_{1},v_{2},...,v_{n}\\}$ in $n$ rounds with the starting graph
$G_{0}=G$. In the $i-th$ round, $i$ takes value from $1$ to $n$:

  * •

$v_{i}$ : the node with the lowest degree (or any one of these nodes if there
is a tie situation) in $G_{i-1}$.

  * •

$N_{i}$ : the neighbor set of $v_{i}$ in $G_{i-1}$.

  * •

$B_{i}$ : $\\{v_{i}\\}\cup N_{i}$.

  * •

$G_{i}$ : a graph that eliminates $v_{i}$ from $G_{i-1}$ and then adds
clique($N_{i}$), that is $V(G_{i})$ $=V(G_{i-1}\backslash\\{v_{i}\\}$, and
$E(G_{i})=E(G_{i-1})$ $\cup$ $E[clique(N_{i})]$ $\backslash\\{N_{i}\\}\times
N_{i}$.

Hybrid Vertex Ordering. Therefore, this paper proposes a hybrid vertex
ordering that compromises between the computational efficiency of degree
vertex order and the index size effectiveness of the tree decomposition order
as follows:

  * •

Classification. All vertices are classified into two categories: core part and
periphery. To achieve this, a degree threshold $\delta$ is specified. If a
vertex $v$’s degree is above this threshold, it is classified into the core-
part. Otherwise, it is classified into the periphery.

  * •

Core-Part. Regarding the core-part vertices, it is observed that the
computation cost can be quite high if the tree decomposition method is used.
Therefore, all these vertices are ordered according to their degree.

  * •

Periphery. The vertices in periphery are ranked according to tree
decomposition order.

  * •

Combinations. Then, these two types of vertices are combined to produce a
hybrid vertex order.

##  V Variants and extensions

Quality Constrained Shortest Path. Similar to [35], to locate the exact
shortest path rather than the distance, the modified algorithm records sets of
quads instead of triples of labels. Let $L(v)$ be a set of quads of
$(u,d_{u},w_{u},p_{uv})$, where $p_{uv}\in V$ is the last edge visited before
inserting this label entry in the index construction search process of
Algorithm 3 starting from $u$. It can restore the shortest path between $v$
and $u$ by ascending the last edge from $v$ to the parents.

Directed and Weighted Graphs. To modify WC-INDEX to a directed graph, the only
modification required is to conduct a constrained constrained BFS from two
directions for each vertex. In addition, $L_{in}$ and $L_{out}$ are required
to hold the index data for in-coming edges and out-coming edges, respectively.
It is necessary to traverse all the index entries in $L_{out}(s)$ and
$L_{in}(t)$ for a $query(s,t,w)$. In cases where the length of an edge is not
$1$ (e.g., weighted graph), we can convert the constrained BFS to a
constrained Dijkstra.

##  VI Experimental Evaluations

Datasets. Tables III and IV provide the statistics of real graphs used in the
experiments. 14 publicly available datasets are used. These datasets can be
downloaded from either KONECT[45]333http://konect.uni-koblenz.de or SNAP
[46]444https://snap.stanford.edu. Directed graphs were converted to undirected
ones in our testings. For labeled graphs such as Movielens, $|w|$ is directly
taken from the original data-set. For other non-labeled graphs, we randomly
generate those weights. For query performance evaluation, 10,000 random
queries were employed and the average time is reported.

Settings. In experiments, all programs were implemented in standard c++11 and
compiled with g++4.8.5.
All experiments were performed on a machine with 20X Intel Xeon 2.3GHz and
385GB main memory running Linux(Red Hat Linux 7.3 64 bit).

TABLE III: Summary of Road Networks

Name | Dataset | $|V(G)|$ | $|E(G)|$
---|---|---|---
NY | New York City | 264,346 | 733,846
FLA | Florida | 1,070,376 | 2,712,798
CAL | California and Nevada | 1,890,815 | 4,657,742
E | Eastern USA | 3,598,623 | 8,778,114
W | Western USA | 6,262,104 | 15,248,146
CTR | Central USA | 14,081,816 | 34,292,496
USA | Full USA | 23,947,347 | 58,333,344

TABLE IV: Summary of Social Networks

Name | Dataset | $|V(G)|$ | $|E(G)|$ | $|w|$
---|---|---|---|---
MV-10 | Movielens-10m | 80,555 | 10,000,054 | 5
EU | eu-2005 | 862,664 | 16,138,468 | 3
ES | eswiki-2013 | 970,331 | 21,184,931 | 3
MV-25 | Movielens-25m | 221,588 | 25,000,095 | 5
FR | frwiki | 1,350,986 | 31,037,302 | 3
UK | uk-2007 | 1,000,000 | 37,061,970 | 3
SO-Y | Stackoverflow (year) | 2,601,977 | 28,183,518 | 9

Figure 5: Indexing Time (s) for baseline, WC-INDEX, and WC-INDEX+. Figure 6:
Indexing Size (GB) for baseline, WC-INDEX, and WC-INDEX+. Figure 7: Querying
time (ms) for baselines, WC-INDEX, and WC-INDEX+.

Algorithms We compare our techniques with the following baseline solutions.

  * •

W-BFS. The original graph is partitioned into $|w|$ parts, and then conduct
BFS.

  * •

Dijkstra. After the partitioning of the original graph into $|w|$ parts,
Dijkstra is conducted.

  * •

C-BFS. It conducts Constrained BFS on the original graph, with the valid edges
explored.

  * •

Naïve. The naïve 2-hop labeling method introduced in Section III.

  * •

LCR-adapt. We modify the state-of-the art Label Constrained Reachability
algorithm to our problem.

  * •

WC-INDEX. The basic algorithm for the quality-constrained shortest path
problem. e

  * •

WC-INDEX+. The advanced algorithm with the query-efficient and hybrid order
techniques.

Exp 1: Indexing Time for Road Networks. Figure 5 illustrates the indexing time
for Naïve 2-hop labeling index, WC-INDEX, and WC-INDEX+. What stands out in
these figures is that WC-INDEX+ is the fastest method to construct the index
among these three algorithms. For instance, for CTR, only WC-INDEX+ can
construct the 2-hop index. As for Naïve and WC-INDEX, WC-INDEX is slower than
Naïve in small datasets, e.g., NY, BAY, COL, EST. Notwithstanding, WC-INDEX is
much faster than Naïve for large datasets, e.g., WST and CTR. We observed that
for smaller graphs, the construction overhead of WC-INDEX dominates the index
construction time. As a result, WC-INDEX builds up slower than the baseline
index. On the other hand, naïve index simply filter the graph based on every
possible weight and construct simple 2-hop indexes for each filter graph. When
the graphs are small, this can be done relatively quickly compared to WC-
INDEX. However, as the size of the graphs gets large, building indexes for
every separate filtered sub-graph is costing much more time, and is eventually
outperformed by WC-INDEX, which only constructs one index.

Exp 2: Indexing size for Road Networks. Figure 6 depicts the index size for
Naïve 2-hop labeling index, WC-INDEX, and WC-INDEX+. What is striking in this
figure is that WC-INDEX and WC-INDEX+ could achieve the same index size. The
reason is that they use the same vertex ordering, and the Query-Efficient
technique can only speed up the construction process, but does not have any
impact on the index size. As for Naïve, its index size is the largest among
these three in all datasets. Table V summarizes the memory usage of storing
the road networks.

TABLE V: Size of Road Networks

Name | Dataset | Size (GB)
---|---|---
NY | New York City | 0.006
FLA | Florida | 0.025
CAL | California and Nevada | 0.043
E | Eastern USA | 0.082
W | Western USA | 0.142
CTR | Central USA | 0.319
USA | Full USA | 0.54

Exp 3: Query Time for Road Networks. Figure 7 demonstrates the query time for
W-BFS, Dijkstra, C-BFS, Naïve, WC-INDEX, and WC-INDEX+. An interesting
obervation is that Dijkstra is the slowest among all the algorithms. It is
evident from Figure 7 that W-BFS and C-BFS have comparable query efficiency.
C-BFS is more efficient than W-BFS in terms of query time. These two BFS-based
online algorithms can commit on all the datasets. The reason that Dijsktra is
slower than BFS is that it reserved the distance priority queue and a distance
vector $D[v]$ to store all the distance information to the start vertex $s$.
Additional, once a new distance from $s$ to $v$ is found, it would be compared
with $d[v]$. $d[v]$ would be updated if a shorter one is found. With these
additional operations, the W-BFS would run faster than Dijskstra, but Dijsktra
could directly cope with the case where edge distance is not $1$.
Nevertheless, W-BFS could not directly address such a case. The query time for
the index-based technique is substantially smaller than the online search
based method. On average, 4-5 orders of magnitudes speedup can be achieved.
Nevertheless, the Naïve 2-hop labeling index can not be constructed for CTR
and WST, hence the query time for these two datasets is set as $INF$. As with
WC-INDEX and WC-INDEX+, they can be constructed in all datasets with a
feasible index size, indexing time, and query time in microseconds. For very
large road networks such as WST and CTR, the naïve indexing cannot constructed
due to memory constraint, since the method builds separate indices for each
$w$. As a result, the query time cannot be tested and thus listed as infinity.

Figure 8: Indexing time (s) for baseline, WC-INDEX, and WC-INDEX+, when
$|W|=20$. Figure 9: Indexing size (GB) for baseline, WC-INDEX, and WC-INDEX+,
when $|W|=20$.

Exp 4: Large $|w|$. Exp 4 investigates the indexing time and indexing size for
the number of different constraint values $|w|=20$. Figures 8 and 9 reports
the findings. The results are similar to that in Exp 1 and 2. Regarding
indexing time, Figure 8 reveals that WC-INDEX+ is the fastest method among
these three to construct the index. Regarding Naïve and WC-INDEX, WC-INDEX is
slower than Naïve across all datasets evaluated, i.e., NY, BAY, COL, EST. As
for indexing size, what is striking in Figure 9 is that WC-INDEX and WC-INDEX+
can achieve the same index size. The reason for this is because they both
employ the same vertex ordering, and the Query-Efficient technique can only
speed up the construction process, without affecting on the index size. As for
Naïve, its index size is the largest among these three in all datasets.

Figure 10: Indexing Time (s) for baseline, WC-INDEX, and WC-INDEX+. Figure 11:
Indexing Size (GB) for baseline, WC-INDEX, and WC-INDEX+. Figure 12: Querying
time (ms) for baselines, WC-INDEX, and WC-INDEX+.

Exp 5: Indexing Time, Size, and Query Time for Social Networks. Exp 5
evaluates the indexing time, size and query time for social networks. As shown
in Figures 10, 11, and 12, the patterns resemble those of road networks. It is
interesting to notice that the indexing time and size over social networks are
larger than that of road networks since social networks have a higher average
degree. For the query time, this experiment does not consider the Dijkstra
since the edge is unweighted and thus it is the same as W-BFS in the social
networks. The query times of WC-INDEX, and WC-INDEX+ are much faster than that
of Naïve method. Table VI summarizes the memory usage of storing the social
networks.

TABLE VI: Size of Social Networks

Name | Dataset | $|E(G)|$
---|---|---
MV-10 | Movielens-10m | 0.093
EU | eu-2005 | 0.15
ES | eswiki-2013 | 0.21
MV-25 | Movielens-25m | 0.23
FR | frwiki | 0.29
UK | uk-2007 | 0.34
SO-Y | Stackoverflow (year) | 0.26

##  VII Related Work

Weight Constrained Shortest Path. Given a directed graph $G$, and two vertices
$s,t\in V(G)$, the WCSP aims to find a path $p$ between $s$ and $t$ such that
the cost of $p$ (i.e., $c(p)=\sum_{e\in p}c(e)$) is minimized and the quality
of $p$ (i.e., $w(p)=\sum_{e\in p}w(e)$) is less than a given threshold $W$.
This problem is proved to be NP-hard [47, 48, 49]. Our quality constraint
shortest distance problem is inherently different as the constraint is imposed
over each individual edge.

Label Constraint Shortest Path. Label-constraint shortest path [50] returns
the length of a shortest path over all paths that satisfy the predefined label
sets (e.g., all labels of the edges in the path belong to the predefined label
set). Likewise, there are some variants of this problem, e.g., Language
constrained shortest path [51], regular language constrained shortest path
[51], and some others in [52, 53]. Nevertheless, they are different from our
quality constraints. Thus, both weight and label constrained shortest path
algorithms are not considered in this paper.

Graph Search for Distance Queries. Both breadth-first search and Dijkstra’s
algorithm are classic algorithms for shortest path problems. Instead of
Dijkstra’s algorithm, the ALT algorithm [54] employs A* search with a
landmark-based heuristic to speed up query processing. The notion of vertex
reach is proposed to reduce the search space for Dijkstra’s algorithm in [55].
In the approaches that are based on arc-flag [56], a graph is partitioned into
$k$ regions and each arc $(u,v)$ is associated with a $k$-bit flag of which
the i-th bit indicates if there is a shortest path from $u$ to the $i$-th
region via $(u,v)$. Based on the arc-flags, the search space of Dijkstra’s
algorithm can also be greatly reduced. The notation of highway hierarchy (HH)
[57] is designed to capture the natural hierarchy of road networks so that
queries can be answered by searching the sparse high levels of HH, reducing
the search space. [58] introduced contraction hierarchy (CH), in which,
different from HH, each level consists of only one vertex. Its efficiency
relies heavily on the noiton of shortcut, which is to presere the distance
between vertices after less important vertices are removed.

Hub Labeling for Distance Queries. Another important class of algorithms for
distance evaluation is hub labeling [32]. In this class, a label $L(v)$ is
computed for each vertex $v$ such that the distance between two vertices $s$
and $t$ can be obtained by inspecting $L(s)$ and $L(t)$ only, without
searching the graph. In general, it is NP-hard to construct a labeling with
the minimum size [32]. In [11, 12], efficient hub labelings for road networks
are discussed. A labeling scheme that instead uses paths as hubs is presented
in [33].

In [34], under the assumption of small treewidth and bounded tree height, a
scheme combining both hub labeling and hierarchy is proposed for road
networks. For real graphs that are scale-free, pruned landmark labeling (PLL)
[35] is the state-of-the-art and many extensions have been devised. For
example, an external algorithm generating the same set of labels is proposed
in [36]; a parallel algorithm is devised in [37]; and [38] shows an algorithm
to update the labels when new edges are inserted into the graph.

##  VIII Conclusion and Future Works

The shortest path is a fundamental concept in graph analytics. Existing works
mainly focus on the distance computer of shortest paths. Nevertheless, finding
a shortest path between $s$ and $t$ with a quality constraint along each edge
is an important problem in many applications. To bridge this research gap,
this paper presents a 2-hop labeling based solution to answer quality
constrained shortest distance queries. Our techniques support query processing
over large-scale graphs in real-time.

Future Works. re-indexing/dynamic index. Effectively managing the index on
dynamic graphs can be a future research direction. Here, we point out a
plausible direction for extending our index to a dynamic scene. To handle edge
insertion and deletion, a set of affected vertices can be computed and updates
in the index can be performed only on affected entries cause by the edge
insertion/deletion. How to effectively compute affected vertices will be the
focus of future research. Potential solutions are to utilize existing index
entries instead of conducting constrained BFS for the edge inserted/deleted.

## References

  * [1] Z. Yang, L. Lai, X. Lin, K. Hao, and W. Zhang, “Huge: An efficient and scalable subgraph enumeration system,” in Proceedings of the 2021 International Conference on Management of Data, SIGMOD ’21, (New York, NY, USA), p. 2049–2062, Association for Computing Machinery, 2021.
  * [2] X. Jin, Z. Yang, X. Lin, S. Yang, L. Qin, and Y. Peng, “Fast: Fpga-based subgraph matching on massive graphs,” arXiv preprint arXiv:2102.10768, 2021\.
  * [3] Y. Peng, X. Lin, Y. Zhang, W. Zhang, L. Qin, and J. Zhou, “Efficient hop-constrained s-t simple path enumeration,” The VLDB Journal, pp. 1–24, 2021.
  * [4] Y. Peng, W. Zhao, W. Zhang, X. Lin, and Y. Zhang, “Dlq: A system for label-constrained reachability queries on dynamic graphs,” in Proceedings of the 230th ACM International Conference on Information & Knowledge Management, 2021.
  * [5] Y. Peng, X. Lin, Y. Zhang, W. Zhang, and L. Qin, “Answering reachability and k-reach queries on large graphs with label-constraints,” The VLDB Journal, pp. 1–25, 2021.
  * [6] H. He, H. Wang, J. Yang, and P. S. Yu, “Blinks: ranked keyword searches on graphs,” in Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pp. 305–316, 2007.
  * [7] M. Jiang, A. W.-C. Fu, and R. C.-W. Wong, “Exact top-k nearest keyword search in large networks,” in Proceedings of the 2015 ACM SIGMOD international conference on management of data, pp. 393–404, 2015.
  * [8] Y. Tao, S. Papadopoulos, C. Sheng, and K. Stefanidis, “Nearest keyword search in xml documents,” in Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pp. 589–600, 2011.
  * [9] U. Brandes, “A faster algorithm for betweenness centrality,” Journal of mathematical sociology, vol. 25, no. 2, pp. 163–177, 2001.
  * [10] R. Puzis, Y. Elovici, and S. Dolev, “Fast algorithm for successive computation of group betweenness centrality,” Physical Review E, vol. 76, no. 5, p. 056709, 2007.
  * [11] I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck, “A hub-based labeling algorithm for shortest paths in road networks,” in International Symposium on Experimental Algorithms, pp. 230–241, Springer, 2011\.
  * [12] I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck, “Hierarchical hub labelings for shortest paths,” in European Symposium on Algorithms, pp. 24–35, Springer, 2012.
  * [13] Y. Peng, Y. Zhang, X. Lin, L. Qin, and W. Zhang, “Answering billion-scale label-constrained reachability queries within microsecond,” Proceedings of the VLDB Endowment, vol. 13, no. 6, pp. 812–825, 2020.
  * [14] X. Qiu, W. Cen, Z. Qian, Y. Peng, Y. Zhang, X. Lin, and J. Zhou, “Real-time constrained cycle detection in large dynamic graphs,” Proceedings of the VLDB Endowment, vol. 11, no. 12, pp. 1876–1888, 2018.
  * [15] Y. Peng, Y. Zhang, W. Zhang, X. Lin, and L. Qin, “Efficient probabilistic k-core computation on uncertain graphs,” in 2018 IEEE 34th International Conference on Data Engineering (ICDE), pp. 1192–1203, IEEE, 2018\.
  * [16] Y. Peng, Y. Zhang, X. Lin, W. Zhang, L. Qin, and J. Zhou, “Towards bridging theory and practice: hop-constrained st simple path enumeration,” Proceedings of the VLDB Endowment, vol. 13, no. 4, pp. 463–476, 2019.
  * [17] Z. Lai, Y. Peng, S. Yang, X. Lin, and W. Zhang, “Pefp: Efficient k-hop constrained s-t simple path enumeration on fpga,” in ICDE, IEEE, 2021\.
  * [18] M. V. Vieira, B. M. Fonseca, R. Damazio, P. B. Golgher, D. d. C. Reis, and B. Ribeiro-Neto, “Efficient search ranking in social networks,” in Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, pp. 563–572, 2007.
  * [19] K. Hao, L. Yuan, and W. Zhang, “Distributed hop-constrained s-t simple path enumeration at billion scale,” Proc. VLDB Endow., vol. 15, no. 2, pp. 169–182, 2021.
  * [20] X. Li, K. Hao, Z. Yang, X. Cao, and W. Zhang, “Hop-constrained s-t simple path enumeration in large uncertain graphs,” in Databases Theory and Applications - 33rd Australasian Database Conference, ADC 2022, Sydney, NSW, Australia, September 2-4, 2022, Proceedings (W. Hua, H. Wang, and L. Li, eds.), vol. 13459 of Lecture Notes in Computer Science, pp. 115–127, Springer, 2022.
  * [21] M. Qiao, H. Cheng, L. Qin, J. X. Yu, S. Y. Philip, and L. Chang, “Computing weight constraint reachability in large networks,” The VLDB journal, vol. 22, no. 3, pp. 275–294, 2013.
  * [22] Q. Ma and P. Steenkiste, “On path selection for traffic with bandwidth guarantees,” in Proceedings 1997 International Conference on Network Protocols, pp. 191–202, IEEE, 1997.
  * [23] Q. Feng, Y. Peng, W. Zhang, Y. Zhang, and X. Lin, “Towards real-time counting shortest cycles on dynamic graphs: A hub labeling approach,” in ICDE, IEEE, 2022.
  * [24] Z. Yuan, Y. Peng, P. Cheng, L. Han, X. Lin, L. Chen, and W. Zhang, “Efficient k-clique listing with set intersection speedup,” in ICDE, IEEE, 2022\.
  * [25] Y. Peng, S. Bian, R. Li, S. Wang, and J. X. Yu, “Finding top-r influential communities under aggregation function,” in ICDE, IEEE, 2022.
  * [26] X. Chen, Y. Peng, S. Wang, and J. X. Yu, “Dlcr : Efficient indexing for label-constrained reachability queries on large dynamic graphs,” Proceedings of the VLDB Endowment, 2022.
  * [27] R. Xiang, J. Neville, and M. Rogati, “Modeling relationship strength in online social networks,” in Proceedings of the 19th international conference on World wide web, pp. 981–990, 2010.
  * [28] X. Zhao, J. Yuan, G. Li, X. Chen, and Z. Li, “Relationship strength estimation for online social networks with the study on facebook,” Neurocomputing, vol. 95, pp. 89–97, 2012.
  * [29] U. Leser, “A query language for biological networks,” Bioinformatics, vol. 21, no. suppl_2, pp. ii33–ii39, 2005.
  * [30] D. Kitagawa, K. Yokota, M. Gouda, Y. Narumi, H. Ohmoto, E. Nishiwaki, K. Akita, and Y. Kirii, “Activity-based kinase profiling of approved tyrosine kinase inhibitors,” Genes to cells, vol. 18, no. 2, pp. 110–122, 2013.
  * [31] A. Biosa, A. Trancikova, L. Civiero, L. Glauser, L. Bubacco, E. Greggio, and D. J. Moore, “Gtpase activity regulates kinase activity and cellular phenotypes of parkinson’s disease-associated lrrk2,” Human molecular genetics, vol. 22, no. 6, pp. 1140–1156, 2013.
  * [32] E. Cohen, E. Halperin, H. Kaplan, and U. Zwick, “Reachability and distance queries via 2-hop labels,” SIAM Journal on Computing, vol. 32, no. 5, pp. 1338–1355, 2003.
  * [33] T. Akiba, Y. Iwata, K.-i. Kawarabayashi, and Y. Kawata, “Fast shortest-path distance queries on road networks by pruned highway labeling,” in 2014 Proceedings of the sixteenth workshop on algorithm engineering and experiments (ALENEX), pp. 147–154, SIAM, 2014.
  * [34] D. Ouyang, L. Qin, L. Chang, X. Lin, Y. Zhang, and Q. Zhu, “When hierarchy meets 2-hop-labeling: Efficient shortest distance queries on road networks,” in Proceedings of the 2018 International Conference on Management of Data, pp. 709–724, 2018.
  * [35] T. Akiba, Y. Iwata, and Y. Yoshida, “Fast exact shortest-path distance queries on large networks by pruned landmark labeling,” in Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 349–360, 2013.
  * [36] M. Jiang, A. W.-C. Fu, R. C.-W. Wong, and Y. Xu, “Hop doubling label indexing for point-to-point distance querying on scale-free networks,” arXiv preprint arXiv:1403.0779, 2014.
  * [37] W. Li, M. Qiao, L. Qin, Y. Zhang, L. Chang, and X. Lin, “Scaling distance labeling on small-world networks,” in Proceedings of the 2019 International Conference on Management of Data, pp. 1060–1077, 2019.
  * [38] T. Akiba, Y. Iwata, and Y. Yoshida, “Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling,” in Proceedings of the 23rd international conference on World wide web, pp. 237–248, 2014.
  * [39] Y. Li, L. H. U, M. L. Yiu, and N. M. Kou, “An experimental study on hub labeling based shortest path algorithms,” Proceedings of the VLDB Endowment, vol. 11, no. 4, pp. 445–457, 2017.
  * [40] R. Halin, “S-functions for graphs,” Journal of geometry, vol. 8, no. 1, pp. 171–186, 1976.
  * [41] N. Robertson and P. D. Seymour, “Graph minors. iii. planar tree-width,” Journal of Combinatorial Theory, Series B, vol. 36, no. 1, pp. 49–64, 1984.
  * [42] H. L. Bodlaender, “A tourist guide through treewidth,” Acta cybernetica, vol. 11, no. 1-2, p. 1, 1994.
  * [43] S. Arnborg, D. G. Corneil, and A. Proskurowski, “Complexity of finding embeddings in ak-tree,” SIAM Journal on Algebraic Discrete Methods, vol. 8, no. 2, pp. 277–284, 1987.
  * [44] A. Berry, P. Heggernes, and G. Simonet, “The minimum degree heuristic and the minimal triangulation process,” in International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 58–70, Springer, 2003.
  * [45] J. Kunegis, “Konect: the koblenz network collection,” in Proceedings of the 22nd international conference on World Wide Web, pp. 1343–1350, 2013.
  * [46] J. Leskovec, A. Krevl, and S. Datasets, “Stanford large network dataset collection,” 2011.
  * [47] O. J. Smith, N. Boland, and H. Waterer, “Solving shortest path problems with a weight constraint and replenishment arcs,” Computers & Operations Research, vol. 39, no. 5, pp. 964–984, 2012.
  * [48] I. Dumitrescu and N. Boland, “Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem,” Networks: An International Journal, vol. 42, no. 3, pp. 135–153, 2003.
  * [49] L. Qin, W. Zhang, Y. Zhang, Y. Peng, H. Kato, W. Wang, and C. Xiao, Software Foundations for Data Interoperability and Large Scale Graph Data Analytics: 4th International Workshop, SFDI 2020, and 2nd International Workshop, LSGDA 2020, Held in Conjunction with VLDB 2020, Tokyo, Japan, September 4, 2020, Proceedings, vol. 1281.  Springer Nature, 2020.
  * [50] F. Bonchi, A. Gionis, F. Gullo, and A. Ukkonen, “Distance oracles in edge-labeled graphs.,” in EDBT, pp. 547–558, 2014.
  * [51] M. Rice and V. J. Tsotras, “Graph indexing of road networks for shortest path queries with label restrictions,” Proceedings of the VLDB Endowment, vol. 4, no. 2, pp. 69–80, 2010.
  * [52] X. Zhang and M. T. Özsu, “Correlation constraint shortest path over large multi-relation graphs,” Proceedings of the VLDB Endowment, vol. 12, no. 5, pp. 488–501, 2019.
  * [53] Q. Shi, Y. Wang, P. Yao, and C. Zhang, “Indexing the extended dyck-cfl reachability for context-sensitive program analysis,” Proceedings of the ACM on Programming Languages, vol. 6, no. OOPSLA2, pp. 1438–1468, 2022.
  * [54] A. V. Goldberg and C. Harrelson, “Computing the shortest path: A search meets graph theory.,” in SODA, vol. 5, pp. 156–165, Citeseer, 2005.
  * [55] R. J. Gutman, “Reach-based routing: A new approach to shortest path algorithms optimized for road networks.,” ALENEX/ANALC, vol. 4, pp. 100–111, 2004\.
  * [56] M. Hilger, E. Köhler, R. H. Möhring, and H. Schilling, “Fast point-to-point shortest path computations with arc-flags,” The Shortest Path Problem: Ninth DIMACS Implementation Challenge, vol. 74, pp. 41–72, 2009\.
  * [57] P. Sanders and D. Schultes, “Highway hierarchies hasten exact shortest path queries,” in European Symposium on Algorithms, pp. 568–579, Springer, 2005\.
  * [58] R. Geisberger, P. Sanders, D. Schultes, and D. Delling, “Contraction hierarchies: Faster and simpler hierarchical routing in road networks,” in International Workshop on Experimental and Efficient Algorithms, pp. 319–333, Springer, 2008.


# Band strutures of hybrid graphene quantum dots with magnetic flux

Bouchaib Lemaalem Laboratory of Theoretical Physics
Faculty of Sciences
Chouaïb Doukkali University
El Jadida, Morocco
<EMAIL_ADDRESS>Youness Zahidi EMAFI
Polydisciplinary Faculty
Sultan Moulay Selimane University
Khouribga, Morocco
<EMAIL_ADDRESS>Ahmed Jellal Laboratory of Theoretical Physics
Faculty of Sciences
Chouaïb Doukkali University
El Jadida, Morocco
<EMAIL_ADDRESS>
###### Abstract

We study the band structures of hybrid graphene quantum dots subject to a
magnetic flux and electrostatic potential. The system is consisting of a
circular single layer graphene surrounded by an infinite bilayer graphene. By
solving the Dirac equation we obtain the solution of the energy spectrum in
two regions. For the valley $K$, it is found that the magnetic flux strongly
acts by decreasing the gap and shifting energy levels away from zero radius
with some oscillations, which are note observed for null flux case. As for the
valley $K^{\prime}$, the energy levels rapidly increase when the radius
increases. A number of oscillations appeared that is strongly dependent on the
values taken by the magnetic flux.

Hybrid graphene, quantum dots, magnetic flux, electrostatic potential.

##  1 Introduction

Quantum dots (QDs) in graphene are very small particles with unique electronic
and optical properties [1, 2, 3, 4, 5, 6]. Since they are highly tunable, then
they can serve as interesting building blocks for materials that might be used
to advance a wide range of applications such as solar cells, medical imaging
and quantum computing. Because of the Klein tunneling effect and the absence
of the gap in the energy spectrum, Dirac fermions cannot be confined by
electrostatic potentials [7]. One solution to overcome such situation is to
realize QDs for instance using thin single-layer graphene (SLG) strips [8, 9]
or nonuniform magnetic fields [10]. Generally, the electronic and optical
properties of fermions in graphene depend on shapes and edges of QDS [11].

On the other hand, A-B bilayer graphene (BLG) consists of two SLG sheets where
the A and B atoms in different layers are on top of each other [12], called
also Bernal stacking. The most important interaction between the two layers is
represented by a direct overlap integral between A and B atoms on top of each
other. BLG presents some particularities for instance an external electric
field, realized by external gate potentials, can induce a tunable band gap in
its energy spectrum contrary to SLG.

Very recently a new generation of circular graphene QDs has been proposed
based on a hybrid system [13]. Indeed, it was demonstrated that charge
carriers can be confined in SLG and BLG islands in a hybrid QD-like structure
made of SLG-BLG junctions. As a result, it is found that the energy levels
exhibit characteristics of interface states in addition to the emergence of
anti-crossings and closing of the band gap in the presence of a bias
potential.

Motivated by the results reported in [13], we consider a geometry made of a
circular SLG QD subjected to a magnetic flux and surrounded by an infinite BLG
sheet as depicted in Fig. 1. We solve Dirac equation in both regions and
determine in the first stage the eigenspinors. To derive equations governing
the energy levels, we use the zigzag boundary conditions at interface. We
numerically analyze our results and show that the magnetic flux differently
acts on the energy levels for both valleys $K$ and $K^{\prime}$.

##  2  SLG quantum dots–BLG infinite

We consider a geometry made of a circular SLG QD of radius $r_{0}$ in the
presence of a magnetic flux $\phi$ embedded in infinite BLG containing
$A_{1}$, $B_{1}$ in first layer and $A_{2}$, $B_{2}$ in second one (Fig. 1).

Figure 1: (color online) Circular SLG quantum dot in the presence of the
magnetic flux $\Phi$ surrounded by an infinite BLGS.

The hybrid system can be described by the following Hamiltonian

$H=v_{F}\ \vec{\sigma}\cdot(\vec{p}+e\vec{A})+U_{1}\mathbb{I}$ (1)

where the vector potential associated to the magnetic flux $\Phi$ is given by

$A(r)=\frac{h}{e}\frac{\Phi}{2\pi r}\hat{e_{\theta}}$ (2)

and $\hat{e_{\theta}}$ is the unit vector for the azimuthal, $U_{1}$ is the
potential applied to SLG, $\sigma_{i}$ are Pauli matrices. To do not couple
the two valleys $K$ and $K^{\prime}$, we assume that the spatial extension of
the flux line is large in comparison to the lattice constant.

###  2.1 Eigenspinors for the two valleys

To determine the eigenspinors of fermions in monolayer graphene subjected to
magnetic flux, we consider the basis
$\Psi^{\tau}(r,\theta)=(\Psi^{\tau}_{A},\Psi^{\tau}_{B})^{T}$ in polar
coordinates $(r,\theta)$ because of the system symmetry. The valley index
$\tau=+1$ refers to $K$ and $\tau=-1$ to $K^{{}^{\prime}}$. By showing that
$[H,J_{z}]=0$, then the separability imposes such as

$\Psi^{\tau}(r,\theta)=e^{im\theta}\begin{pmatrix}\chi^{\tau}_{A}(r)\\\
ie^{-i\tau\theta}\chi^{\tau}_{B}(r)\end{pmatrix}$ (3)

where $m=0,\pm 1,\pm 2,\cdots$ are eigenvalues of $L_{z}$ associated to the
total angular momentum $J_{z}=L_{z}+\frac{\hbar}{2}\sigma_{z}$. To proceed
further, let us write the Hamiltonian (1)

$H=v_{F}\hbar\begin{pmatrix}u_{1}&\pi_{+}\\\ \pi_{-}&u_{1}\end{pmatrix}$ (4)

in terms of the operators

$\displaystyle\pi_{\pm}=e^{\pm
i\varphi}\left(-i\frac{\partial}{\partial\xi}\pm\frac{\tau}{\xi}\frac{\partial}{\partial\theta}\pm
i\frac{\Phi}{\xi}\right)$ (5)

such that the change of variable $\xi=\frac{r}{r_{0}}$ and the dimensionless
quantities $\varepsilon=\frac{Er_{0}}{\hbar v_{F}}$,
$u_{1}=\frac{U_{1}r_{0}}{\hbar v_{F}}$ are used.

The eigenvalue equation $H\Psi(\xi,\theta)=\varepsilon\Psi(\xi,\theta)$ allows
to find two coupled equations

$\displaystyle\left(\frac{\partial}{\partial\xi}-\frac{\tau
m-1+\Phi}{\xi}\right)\chi^{\tau}_{B}=\left(\varepsilon-
u_{1}\right)\chi^{\tau}_{A}$ (6)
$\displaystyle\left(\frac{\partial}{\partial\xi}+\frac{\tau
m+\Phi}{\xi}\right)\chi^{\tau}_{A}=-\left(\varepsilon-
u_{1}\right)\chi^{\tau}_{B}$ (7)

By injecting (7) into (6) we obtain a second order differential equation for
$\chi_{A}^{\tau}$

$\displaystyle\left[\frac{\partial^{2}}{\partial\xi^{2}}+\frac{1}{\xi}\frac{\partial}{\partial\xi}-\frac{1}{\xi^{2}}\left(\tau
m+\Phi\right)^{2}+\left(\varepsilon-u_{1}\right)^{2}\right]\chi^{\tau}_{A}=0$
(8)

having the Bessel function as solution

$\displaystyle\chi^{\tau}_{A}(\xi)=N^{\tau}J_{\nu}(\lambda\xi)$ (9)

where we have set $\lambda=\varepsilon-u_{1}$ and a new quantum number
$\nu=\tau m+\Phi$ depending on the valley index $\tau$ and flux $\Phi$,
$N^{\tau}$ is a constant of normalization. Now replacing (9) in (7), we end up
with the second component

$\displaystyle\chi^{\tau}_{B}(\xi)=-\tau N^{\tau}J_{\nu-\tau}(\lambda\xi)$
(10)

With the help of some relations between Bessel functions, we finally obtain
the eigenspinors in monolayer graphene, which are

$\Psi^{\tau}(\xi,\theta)=e^{im\theta}\begin{pmatrix}N^{\tau}J_{\nu}(\lambda\xi)\\\
ie^{i\tau\theta}\tau N^{\tau}J_{\nu+\tau}(\lambda\xi)\end{pmatrix}$ (11)

To achieve our task we consider the BLG region described by Hamiltonian for
the valley $K$ $(\tau=+1)$

$H^{+}=\begin{pmatrix}u_{+}+u_{-}&p_{+}&t^{{}^{\prime}}&0\\\
p_{-}&u_{0}+\delta&0&0\\\ t^{{}^{\prime}}&0&u_{0}-\delta&p_{-}\\\
0&0&p_{+}&u_{0}-\delta\end{pmatrix}$ (12)

in the basis
$(\Phi_{A_{1}}^{+},\Phi_{B_{1}}^{+},\Phi_{A_{2}}^{+},\Phi_{B_{2}}^{+})$ and we
have set $p_{\pm}=p_{x}\pm ip_{y}$, $t^{{}^{\prime}}=\frac{tr_{0}}{\hbar
v_{F}}$, $u_{+}=\frac{u_{1}+u_{2}}{2}$, $u_{-}=\frac{u_{1}-u_{2}}{2}$, and
$u_{1,2}=\frac{U_{1,2}r_{0}}{\hbar v_{F}}$, with $U_{1,2}$ are the potentials
at the two layers. In this region, the eigenspinors can be decoupled as

$\Phi^{+}(\xi,\theta)=e^{im\theta}\begin{pmatrix}\chi^{+}_{A_{1}}(\xi)\\\
ie^{-i\theta}\chi^{+}_{B_{1}}(\xi)\\\ \chi^{+}_{B_{2}}(\xi)\\\
ie^{i\theta}\chi^{+}_{A_{1}}(\xi)\end{pmatrix}$ (13)

and then the eigenvalue equation gives rise to the set

$\displaystyle\left(\frac{d}{d\xi}-\frac{m-1}{\xi}\right)\chi^{+}_{B_{1}}=\left(\varrho-
u_{-}\right)\chi^{+}_{A_{1}}-t{{}^{\prime}}\chi^{+}_{B_{2}}$ (14)
$\displaystyle\left(\frac{d}{d\xi}+\frac{m}{\xi}\right)\chi^{+}_{A_{1}}=-\left(\varrho-
u_{-}\right)\chi^{+}_{B_{1}}$ (15)
$\displaystyle\left(\frac{d}{d\xi}+\frac{m+1}{\xi}\right)\chi^{+}_{A_{2}}=\left(\varrho+u_{-}\right)\chi^{+}_{B_{2}}(\rho)-t{{}^{\prime}}\chi^{+}_{A_{1}}$
(16)
$\displaystyle\left(\frac{d}{d\xi}-\frac{m}{\xi}\right)\chi^{+}_{B_{2}}=-\left(\varrho+u_{-}\right)\chi^{+}_{A_{2}}$
(17)

with $\varrho=\epsilon-u_{+}$. These equations can be decoupled to obtain for
instance the following one for $\chi^{k}_{A_{1}}$

$\left(\frac{d^{2}}{d\xi^{2}}+\frac{1}{\xi}\frac{d}{d\xi}-\frac{m^{2}}{\xi^{2}}-\mu^{2}_{\pm}\right)\chi^{+}_{A_{1}}=0$
(18)

showing the eigenvalues

$\mu_{\pm}=\left[-\left(\varrho^{2}+u_{-}^{2}\right)\pm\left[\left(\varrho^{2}-u_{-}^{2}\right)t^{{}^{\prime}2}+4\varrho^{2}u_{-}^{2}\right]^{\frac{1}{2}}\right]^{\frac{1}{2}}$
(19)

and the appropriate solutions vanishing at $r\longrightarrow\infty$ is the
modified Bessel function of the second kind $K_{m}^{\pm}=K_{m}(\mu_{\pm}\xi)$,
then we have

$\chi^{+}_{A_{1}}(\xi)=N^{+}_{1}K_{m}^{+}+N^{+}_{2}K_{m}^{-}$ (20)

This can be used to derive the remaining components of the eigenspinors as
follows

$\displaystyle\chi^{+}_{B_{1}}=\frac{1}{\varrho-
u_{-}}\left[N_{1}^{+}\mu_{+}K_{m-1}^{+}+N_{2}^{+}\mu_{-}K_{m-1}^{-}\right]$
(21) $\displaystyle\chi^{+}_{B_{2}}=\frac{1}{(\varrho-
u_{-})t^{{}^{\prime}}}\left[N_{1}^{+}\eta_{+}K_{m}^{+}+N_{2}^{+}\eta_{-}K_{m}^{-}\right]$
(22)
$\displaystyle\chi^{+}_{A_{2}}=\frac{1}{(\varrho^{2}-u_{-}^{2})t^{{}^{\prime}}}\left[N_{1}^{+}\mu_{+}\eta_{+}K_{m+1}^{+}+N_{2}^{+}\mu_{-}\eta_{-}K_{m+1}^{-}\right]$
(23)

where we have defined

$\eta_{\pm}=(\varrho-u_{-})^{2}+\mu_{\pm}^{2}$ (24)

$N^{+}_{1}$ and $N^{+}_{2}$ are two constants of normalization. It is showed
that (19) possess a gap in the energy spectrum [14]

$\Delta=\frac{\Delta U}{\sqrt{1+\frac{\Delta U^{2}}{t^{2}}}}$ (25)

resulted from the Mexican-hat shaped low-energy dispersion in pristine BLG. In
the limit $\Delta U\ll t$ it behaves as potential scale, i.e.
$\Delta\approx{\Delta U}$.

As concerning the valley $K^{\prime}$, one can easy show that the radial parts
of the corresponding eigenspinors can be linked to those for the valley $K$.
Indeed, solving the eigenvalue equation with the basis

$\Phi^{-}(\xi,\theta)=e^{im\xi}\begin{pmatrix}\chi^{-}_{A_{1}}(\xi)\\\
ie^{i\theta}\chi^{-}_{B_{1}}(\xi)\\\ \chi^{K^{{}^{\prime}}}_{B_{2}}(\xi)\\\
ie^{-i\theta}\chi^{-}_{A_{2}}(\xi)\end{pmatrix}$ (26)

to end up with the relations

$\displaystyle\chi^{-}_{A_{1}}(\xi)=\chi^{+}_{B_{2}}(\xi)$ (27)
$\displaystyle\chi^{-}_{B_{1}}(\xi)=\chi^{+}_{A_{2}}(\xi)$ (28)
$\displaystyle\chi^{-}_{B_{2}}(\xi)=\chi^{+}_{A_{1}}(\xi)$ (29)
$\displaystyle\chi^{-}_{B_{1}}(\xi)=\chi^{+}_{B_{1}}(\xi)$ (30)

In the next we will see how the above results will be used to analyze the
influence of the applied magnetic flux on the energy levels.

###  2.2 Zigzag boundary conditions

To derive equations describing the energy levels for the two valleys, we use
the zigzag boundary conditions [15]. Then, at the interface $\xi=1$, namely
$r=r_{0}$, between SLG and BLG we have the continuities

$\displaystyle\Psi^{\tau}_{A}(1,\theta)=\Phi_{A_{1}}^{\tau}(1,\theta)$ (31)
$\displaystyle\Psi^{\tau}_{B}(1,\theta)=\Phi_{B_{1}}^{\tau}(1,\theta)$ (32)
$\displaystyle 0=\Phi_{A_{2}}^{\tau}(1,\theta)$ (33)

Consequently, (31-33) give

$\displaystyle M^{+}\begin{pmatrix}N^{+}\\\ N^{+}_{1}\\\
N^{+}_{2}\end{pmatrix}=0$ (34)

for the valley $K$ ($\tau=+1$) such that the matrix is

$M^{+}=\begin{pmatrix}-J_{\nu}(\lambda)&K_{m}^{+}&K_{m}^{-}\\\
J_{\nu-1}(\lambda)&a_{+}K_{m-1}^{+}&a_{-}K_{m-1}^{-}\\\
0&b_{+}K_{m}^{+}&b_{-}K_{m}^{-}\end{pmatrix}$ (35)

where we have set

$\displaystyle a_{\pm}=\frac{\mu_{\pm}}{\varrho-u_{-}},\qquad
b_{\pm}=\frac{\left(\varrho-u_{-}\right)^{2}+\mu_{\pm}^{2}}{\left(\varrho-
u_{-}\right)t{{}^{\prime}}}$ (36)

Regarding $K^{{}^{\prime}}$, we fix $\tau=-1$ and use the corresponding
eigenspinors to end up with

$\displaystyle M^{-}\begin{pmatrix}N^{-}\\\ N^{-}_{1}\\\
N^{-}_{2}\end{pmatrix}=0$ (37)

and the matrix reads as

$\displaystyle
M^{-}=\begin{pmatrix}-J_{\nu}(\lambda)&b_{+}K_{m}^{+}&b_{-}K_{m}^{-}\\\
-J_{\nu+1}(a)&c_{+}K_{m-1}^{+}&c_{-}K_{m-1}^{-}\\\
0&K_{m}^{+}&K_{m}^{-}\end{pmatrix}$ (38)

with the parameters

$c_{\pm}=\frac{b_{\pm}\mu_{\pm}}{\varrho+u_{-}}$ (39)

$N^{-}_{1}$ and $N^{-}_{2}$ are two constants of normalization. At this level
we point out that the energy levels for both valleys are solutions of the two
determinants

$\displaystyle\det M^{+}=0,\qquad\det M^{-}=0$ (40)

It is clear that form the complexity of the special functions involved in the
eigenspinors, it is not easy to analytically derive an explicit expression of
the energy levels. Then, to investigate the basic features of our hybrid
system we will proceed numerically.

##  3 Numerical Analysis

We plot the energy levels $E$(eV) versus the dot radius $r_{0}$(nm) for the
valleys $K$ and $K^{{}^{\prime}}$ under suitable conditions of the physical
parameters. It is convenient for our task to choose the angular momenta
$m=0,\pm 1,\pm 2,\pm 3$, magnetic flux
$\Phi=\pm\frac{1}{2},\pm\frac{3}{2},\pm\frac{5}{2}$ and the biased potential
$U_{1}=-U_{2}=0.1$ eV. We emphasis that the solid black horizontal lines in
all figures show the band gap.

###  3.1 Valley $K$

As a first result regarding the valley $K$, we observe that the symmetry
$E^{+}(m)=E^{+}(-m)$ is always preserved for all values taken by the magnetic
flux.

Figure 2: (color online) Energy levels of the valley $K$ as a function of the
dot radius $r_{0}$ for $m=0,\pm 1,\pm 2,\pm 3$ in the presence of the biased
potential $U_{1}=-U_{2}=0.1$ eV and the magnetic flux $\Phi$ (a):
$\frac{1}{2}$, (b): $-\frac{1}{2}$.

Fig. 2a presents the behavior of the energy levels $E$ for the value
$\Phi=\frac{1}{2}$. We notice that the energy levels are shifted and band gap
decreased compared to the non-flux case [13]. As long as the radius increases
we see that $E$ increase but gap continue decreasing. We observe another
behavior in Fig. 2b with $\Phi=-\frac{1}{2}$. Indeed, the energy levels show a
maximum corresponds to $m=0$ and $r_{0}=0$, after they oscillate to reach a
minimum at $r_{0}=4.8$ nm and then increase.

Figure 3: (color online) The same as in Fig. 2, but now with the magnetic flux
$\Phi$ (a): $\frac{3}{2}$, (b): $-\frac{3}{2}$.

Now we increase the magnetic flux and choose $\Phi=\frac{3}{2}$ as presented
in Fig. 3b. In the present case, the shift of the energy levels becomes clear
and the decrease in gap as well. Remarkably for the negative value
$\Phi=-\frac{3}{2}$ in Fig. 3b we notice that the values $m=\pm 1$ show a
similar behavior as in Fig. 2b for $m=0$ but with less oscillation. In
addition, we observe here that $m=0$ and $m=\pm 1$ correspond to the minima
$r_{0}=12.67$ nm and $r_{0}=10.11$ nm, respectively.

Figure 4: (color online) The same as in Fig. 2, but now the magnetic flux
$\Phi$ (a): $\frac{5}{2}$, (b): $-\frac{5}{2}$.

By increasing the magnetic flux to $\phi=\frac{5}{2}$ in Fig. 4a, we notice
that the shift and gap become more important. As for $\phi=-\frac{5}{2}$ in
Fig. 4b, we observe that the number of oscillations increases to three
corresponding to the quantum numbers $m=0$, $m=\pm 1$ and $m=\pm 2$ with the
minima $r_{0}=18.81$ nm, $r_{0}=15.69$ nm and $r_{0}=13.67$ nm, respectively.

###  3.2 Valley $K^{\prime}$

As for the valley $K^{\prime}$, the energy levels show different behavior
resulted form the choice of the magnetic flux compared to the valley $K$.
Indeed, the first difference that should be noticed we do not have the
symmetry $E^{-}(m)\neq E^{-}(-m)$ with $m=0,1,2,3$ correspond to solid lines
and the negative numbers to dashed lines in plots below. In addition, for
$\Phi=\frac{1}{2}$ in Fig. 5a, the energy levels rapidly increase and the
particularity is seen for $m=-1$ where the level overcomes that for $m=1$. The
situation is completely changed for $\Phi=-\frac{1}{2}$ in Fig. 5b because we
observe that the level $m=-1$ is under $m=1$.

Figure 5: (color online) Energy levels of the valley $K^{\prime}$ as a
function of the dot radius $r_{0}$ for $m=0,\pm 1,\pm 2,\pm 3$ in the presence
of the biased potential $U_{1}=-U_{2}=0.1$ eV and the magnetic flux $\Phi$
(a): $\frac{1}{2}$, (b): $-\frac{1}{2}$.

The behavior of the energy levels becomes more clear in Fig. 6a with
$\Phi=\frac{3}{2}$ compared to Fig. 5a. Now as concerning the negative value
$\Phi=-\frac{3}{2}$, Fig. 6b shows a mixing of the energy levels and we
observe that some oscillations with different amplitudes start to take place.
These are corresponding to the quantum numbers $m=0$ (black solid line),
$m=-1$ (blue dashed line), $m=-2$ (red dashed line), $m=-3$ (green dashed
line).

Figure 6: (color online) The same as in Fig. 5, but now with the magnetic flux
$\Phi$ (a): $\frac{3}{2}$, (b): $-\frac{3}{2}$.

We now consider $\Phi=\frac{5}{2}$ in Fig. 7a and observe an important change
in the energy levels such that shifts increase. In Fig. 7b with
$\Phi=-\frac{5}{2}$, we notice that the number of oscillations increase as
well. These results show the manifestation of the magnetic flux and its impact
on the energy levels.

Figure 7:  (color online) The same as in Fig. 5, but now with the magnetic
flux $\Phi$ (a): $\frac{5}{2}$, (b): $-\frac{5}{2}$.

##  4 Conclusion

We have studied the influence of a magnetic flux on the energy levels of a
hybrid graphene. More precisely, we have considered a graphene quantum dot
surrounded by a infinite bilayer graphene. Our result showed that the energy
levels can oscillate, increase and shift under appropriate choice of flux and
variation of the dot radius. We have found that the energy levels of the
valleys $K$ and $K^{\prime}$ present different behaviors.

## References

  * [1] A. V. Rozhkov, G. Giavaras, Y. P. Bliokh, V. Freilikher, and F. Nori, Phys. Rep. 503, 77 (2011).
  * [2] Z. Z. Zhang, K. Chang, and F. M. Peeters, Phys. Rev. B 77, 235411 (2008).
  * [3] D. Bischoff, A. Varlet, P. Simonet, M. Eich, H. C. Overweg, T. Ihn, and K. Ensslin, Appl. Phys. Rev. 2, 031301 (2015).
  * [4] B. Trauzettel, D. V. Bulaev, D. Loss, and G. Burkard, Nat. Phys. 3, 192 (2007).
  * [5] J. M. Pereira Jr, F. M. Peeters, P. Vasilopoulos, R. N. Costa Filho, and G. A. Farias, Phys. Rev. B 79, 195403 (2009).
  * [6] P. Recher and B. Trauzettel, Nanotechnol. 21, 302001 (2010).
  * [7] M. I. Katsnelson, K. S. Novoselov, and A. K. Geim, Nat. Phys. 2, 620 (2006).
  * [8] N. M. R. Peres, A. H. Castro Neto, and F. Guinea, Phys. Rev. B 73, 241403 (2006).
  * [9] P. G. Silvestrov and K. B. Efetov , Phys. Rev. Lett. 98, 016802 (2007).
  * [10] C. Berger et al., Science 312, 1191 (2006).
  * [11] Alev Devrim Güçlü, Pawel Potasz, Marek Korkusinski, and Pawel Hawrylak, Graphene Quantum Dots (Springer Berlin Heidelberg, 2014).
  * [12] E. McCann, D. S. L. Abergel, and V. I. Falko, Eur. Phys. J. Spec. Top. 148, 91 (2007).
  * [13] M. Mirzakhani, M. Zarenia, S. A. Ketabi, D. R. da Costa, and F. M. Peeters, Phys. Rev. B 93, 165410 (2016).
  * [14] E. McCann, D. S. L. Abergel, and V. I. Falko, Eur. Phys. J. Spec. Top. 148, 91 (2007).
  * [15] M. Koshino, T. Nakanishi, and T. Ando, Phys. Rev. B 82, 205436 (2010).