# Efficient Reachability Ratio Computation for 2-hop Labeling Scheme

Junfeng Zhou, Xian Tang, Ming Du Junfeng Zhou and Ming Du were with the School
of Computer Science and Technology, Donghua University, Shanghai, China
201620.
E-mail<EMAIL_ADDRESS>Tang was with Shanghai University of
Engineering Science, Shanghai, China 201620.
E-mail<EMAIL_ADDRESS>
###### Abstract

As one of the fundamental graph operations, reachability queries processing
has been extensively studied during the past decades. Many approaches followed
the line of designing 2-hop labels to make acceleration. Considering that the
index size cannot be bounded when using all nodes to construct 2-hop labels,
researchers proposed to use a part of important nodes to construct 2-hop
labels (partial 2-hop labels) to cover as much reachability information as
possible. Then, we may achieve better query performance with limited index
size and index construction time. However, partial 2-hop labels do not always
perform well on different graphs.

In this paper, we focus on the problem of how to efficiently compute
reachability ratio, such that to help users determine whether partial 2-hop
labels should be used to answer reachability queries for the given graph.
Intuitively, reachability ratio denotes the ratio of the number of reachable
queries that can be answered by partial 2-hop labels over the total number of
reachable queries involved in the given graph. We discuss the difficulties of
reachability ratio computation, and propose an incremental-partition algorithm
for reachability ratio computation. We show by rich experimental results that
our algorithm can efficiently get the result of reachability ratio, and show
how the overall query performance is affected by different partial 2-hop
labels. Based on the experimental results, we give out our findings on whether
partial 2-hop labels should be used to the given graph for reachability
queries processing.

###### Index Terms:

Reachability Queries Processing, 2-hop Labeling Scheme, Reachability Ratio

##  1 Introduction

Reachability queries processing is one of the fundamental graph operations and
has been extensively studied in the literature [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]. Given a
directed graph, a reachability query ${u}?\rightsquigarrow{v}$ asks whether
there exists a directed path from node $u$ to $v$. It can be used to Semantic
Web (RDF), online social networks, biological networks, ontology,
transportation networks, etc, to answer whether two nodes have a certain
connection. It can also be used as a building brick in structured queries
answering, such as XQuery111https://www.w3.org/TR/2017/REC-xquery-31-20170321
or SPARQL222https://www.w3.org/TR/rdf-sparql-query.

To answer a given reachability query, researchers have proposed many efficient
labeling schemes [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23, 24, 25, 26] to make acceleration, among which 2-hop
labeling scheme has been widely adopted and was shown to be better than others
in many cases [4, 7, 3, 20, 19, 9, 26]. Existing approaches that adopt 2-hop
labels can be classified into two categories. The first kind of approaches [4,
3, 7, 20, 19] generate 2-hop labels based on all nodes, i.e., the 2-hop labels
maintain the whole transitive closure (TC). For these approaches, a
reachability query ${u}?\rightsquigarrow{v}$ can be answered by comparing the
2-hop labels of $u$ and $v$ without graph traversal. However, the index size
cannot be bounded w.r.t. the size of the input graph, and minimizing the size
of 2-hop labels is NP-hard [4].

Different with [4, 3, 7, 20, 19], the second kind of approaches [9, 26] do not
generate 2-hop labels based on all nodes, but based on a few nodes with large
degree. We call these nodes as hop-nodes, and call 2-hop labels based on these
hop-nodes as partial 2-hop labels. Compared with the first kind of approaches,
the index size of partial 2-hop labels can be bounded, and is usually much
smaller than that of the first kind of approaches. Even though partial 2-hop
labels cannot answer all reachable queries in the whole TC, it was shown in
[9, 26] that partial 2-hop labels can help improve the query performance
significantly by answering most reachable queries for some graphs.

However, for some other graphs, the query performance may degenerate when
using partial 2-hop labels [9, 26]. The reason lies in that the reachability
ratio of partial 2-hop labels changes violently for different graphs. Here,
reachability ratio means the ratio of the number of reachable queries that can
be answered by partial 2-hop labels over the size of the TC. Figure 1 shows
the reachability ratio of partial 2-hop labels on three graphs, from which we
know that if we construct partial 2-hop labels using four hop-nodes with large
degree, then the reachability ratio is greater than 90% on human and web-uk,
meaning that the probability that a given reachable query $q$ can be answered
by partial 2-hop labels is greater than 90%, and is close to 0 on patent
meaning that the probability that $q$ can be answered by partial 2-hop labels
is close to 0. In this case, using partial 2-hop labels brings us nothing but
additional cost, which may degenerate the overall performance.

Figure 1: Reachability ratio of partial 2-hop labels based on $k$ nodes with
large degree.

Therefore, before using partial 2-hop labels, a key problem that needs to be
solved is: how to efficiently compute the reachability ratio of partial 2-hop
labels w.r.t. the given graph? Because only if we know the reachability ratio,
we can determine whether we should use it. For example, given the reachability
ratio shown in Figure 1, we may decide to use partial 2-hop labels on human
and web-uk, but not on patent, due to that using more hop-nodes on patent
cannot increase the reachability ratio significantly. Furthermore, we can
determine how many hop-nodes should be chosen to construct the partial 2-hop
labels, if we decide to use partial 2-hop labels to accelerate the query
performance. For example, according to the reachability ratio in Figure 1, we
may decide to use four hop-nodes to construct partial 2-hop labels on human,
but for web-uk, reachability ratio changes little with the increase of hop-
nodes and one hop-node is good enough, which means a larger reachability ratio
and smaller index size.

To the best of our knowledge, this is the first work that addresses the
problem of reachability ratio computation, which is not a trivial task and
involves two operations. One is computing the size of TC, the other is
computing the exact number of reachable queries that can be answered by the
partial 2-hop labels, which we call as the coverage size. Considering that TC
size computation can be efficiently solved by existing works [27], the
difficulty of reachability ratio computation lies in how to efficiently
compute the coverage size. The naive way is first generating partial 2-hop
labels based on $k$ selected hop-nodes, then getting the coverage size by
checking all node pairs using the partial 2-hop labels. In this way, the cost
of coverage size computation is $O(k|V|^{2})$ and cannot scale to large
graphs, where $V$ is the set of nodes in the input graph. Further, if the
reachability ratio is too small to meet the requirement, we may need to
increase $k$’s value and repeat the above operation, which makes reachability
ratio computation more difficult to be solved.

We propose to compute the coverage size incrementally, such that when the
value of $k$ changes, we can avoid the costly coverage size recomputation,
such that to support efficient reachability ratio computation. The basic idea
is, given the coverage size w.r.t. $k$ nodes, when we decide to compute the
coverage size w.r.t. $k+1$ hop-nodes, we do not compute the coverage size from
scratch, but only compute the increased coverage size. However, the increased
coverage size cannot be easily computed. To know the increased coverage size
w.r.t. the $(k+1)^{\text{th}}$ hop-node $u$, we need to firstly traverse from
$u$ to get a set of nodes $D_{u}$ that $u$ can reach, then traverse from $u$
backwardly to get the second set of nodes $A_{u}$ that can reach $u$. Given
$A_{u}$ and $D_{u}$, we need to check for each pair of nodes $(a,d)$, whether
$a$ can reach $d$ can be determined by the current partial 2-hop labels
without $u$, where $a\in A_{u},d\in D_{u}$. If the answer is YES, then we know
that $a$ can reach $d$ can be answered by the partial 2-hop labels without
$u$, and should not be considered when computing the increased coverage size
w.r.t. $u$. The cost of processing one hop-node $u$ is as high as
$O(k|A_{u}||D_{u}|)$. Obviously, with the increase of the number of hop-nodes
for partial 2-hop labels construction, the cost could be unaffordable. To this
problem, we propose to divide both $A_{u}$ and $D_{u}$ into a set of disjoint
subsets based on equivalence relationship (defined later), such that for each
pair of subsets $A_{1}\subseteq A_{u}$ and $D_{1}\subseteq D_{u}$, we only
need to test one reachability query, rather than $|A_{1}|\times|D_{1}|$
queries. The cost of reachability ratio computation is, therefore, reduced
significantly even when processing large graphs. We make the following
contributions.

  1. 1.

To the best of our knowledge, this is the first work to address the problem of
reachability ratio computation.

  2. 2.

We propose a set of algorithms for reachability ratio computation. We show
that according to the properties of 2-hop labels, the two sets of nodes that
can reach and be reached by a certain hop-node can be divided into a set of
disjoint subsets, such that the computation cost can be reduced significantly.
We prove the correctness and efficiency of our approach.

  3. 3.

We conduct rich experiments on real datasets. The experimental results show
that compared with the baseline approach, our algorithm works much more
efficiently on reachability ratio computation. We also show how the overall
query performance is affected by partial 2-hop labels with different number of
hop-nodes, based on which we give out our findings on whether partial 2-hop
labels should be used to the given graph for reachability queries processing.

The remainder of the paper is organized as follows. We discuss the
preliminaries and the related work in Section 2. In Section 3, we give out the
baseline algorithm for reachability ratio computation, and propose the first
incremental algorithm in Section 4. After that, we propose the optimized
incremental algorithm in Section 5. We report our experimental studies in
Section 6, and conclude our paper in Section 7.

##  2 Background and Related Work

###  2.1 Preliminaries

Given a directed graph $\mathcal{G}$, we can construct a directed acyclic
graph (DAG) $G$ from $\mathcal{G}$ in linear time [28] by coalescing each
strongly connected component (SCC) of $\mathcal{G}$ into a node in $G$. Then,
the reachability query on $\mathcal{G}$ can be answered equivalently on $G$.
We follow the tradition and assume that the input graph is a DAG.

Given a DAG $G=(V,E)$, where $V$ is the set of nodes and $E$ the set of edges.
We define $in({u})=\\{v|(v,u)\in E\\}$ as the set of in-neighbor nodes of $u$
in $G$, and $out({u})=\\{v|(u,v)\in E\\}$ the set of out-neighbor nodes of
$u$. Similarly, we use $in^{*}({u})$ to denote the set of nodes in $G$ that
can reach $u$, and $out^{*}({u})$ the set of nodes in $G$ that $u$ can reach.
We say $u$ can reach $v$ (${u}\rightsquigarrow{v}$), if $v\in out^{*}({u})$.

The transitive closure (TC) of $G$ is $G^{*}=(V,E^{*})$, where
$E^{*}=\\{(u,v)|u,v\in V,v\in out^{*}({u}),v\neq u\\}$. We define
$TC(u)=out^{*}({u})\setminus\\{u\\}$ as the transitive closure of $u$, and
define $TC^{-1}(u)=in^{*}({u})\setminus\\{u\\}$ as the reverse TC of $u$. The
TC size of $G$ is denoted as $TC(G)=\sum_{u\in V}|TC(u)|$. In [27], the
authors proposed an efficient algorithm for TC size computation with time
complexity $O(r|E|)$, where $r$ is the number of distinct paths decomposed
from the input graph. In this paper, we assume that the TC size is given in
advance, which can be got by executing the algorithm in [27] as an offline
activity. Note that TC size computation is different with TC computation. The
former computes $|TC(v)|$ for all nodes, while the latter computes $TC(v)$ for
all nodes with time complexity $O(|V|\times|E|)$.

Given a set of $k$ nodes $S_{k}\subseteq V$, we use $\mathcal{L}_{k}$ to
denote 2-hop labels constructed based on nodes of $S_{k}$, where each node in
$S_{k}$ is called a hop-node. If $v\in TC(u)$ and $\mathcal{L}_{k}$ can
correctly tell that ${u}\rightsquigarrow{v}$, we say $\mathcal{L}_{k}$ (or
$S_{k}$) can cover the reachable query ${u}\rightsquigarrow{v}$. Let $N_{k}$
be the number of distinct reachable queries that can be covered by
$\mathcal{L}_{k}$, the reachability ratio of $S_{k}$ is defined as Equation 1.

$\alpha=N_{k}/TC(G)$ (1)

Problem Statement: Given a DAG $G=(V,E)$, its TC size and a hop-node set
$S_{k}\subseteq V$, return the reachability ratio of $S_{k}$.

TABLE I: Notations Notation | Description
---|---
$G=(V,E)$ | a DAG with a node set $V$ and an edge set $E$
$in({v})(out({v}))$ | the set of in-neighbors (out-neighbors) of $v$
$in^{*}({v})(out^{*}({v}))$ | the set of nodes that can reach (be reached by) $v$
$TC(v)(TC^{-1}(v))$ | $out^{*}({v})\setminus\\{v\\}(in^{*}({v})\setminus\\{v\\})$
$TC(G)$ | the TC size of $G$
$S_{k}$ | a set of $k$ hop nodes
$L^{{k}}_{out}({v})(L^{{k}}_{in}({v}))$ | the 2-hop out (in) label of $v$ w.r.t. $S_{k}$
$\mathcal{L}_{k}$ | the partial 2-hop labels w.r.t. $S_{k}$
$N_{k}$ | the number of reachable queries covered by $\mathcal{L}_{{k}}$
$A_{k}$ | ancestor set containing nodes that can reach $v_{k}$
$D_{k}$ | descendant set containing nodes that $v_{k}$ can reach

###  2.2 Related Work

As no existing works has addressed reachability ratio computation, we only
discuss existing works on reachability queries processing. We discuss these
approaches according to whether they use 2-hop labels to answer reachability
queries.

2-hop based Approaches: Cohen et al. proposed to use 2-hop label [4] to answer
reachability queries, where each node $u$ is assigned two labels, one is in-
label $L_{in}({u})$, and the other is out-label $L_{out}({u})$.
$L_{in}({u})(L_{out}({u}))$ consists of a set of nodes $v$ that can reach (be
reached by) $u$. Given the 2-hop label, the answering of a reachability query
${u}?\rightsquigarrow{v}$ can be done by a set intersection operation on two
labels, as indicated by Formula 2.

${u}?\rightsquigarrow{v}=\left\\{\begin{array}[]{ll}\text{TRUE},&L_{out}({u})\bigcap
L_{in}({v})\neq\emptyset,\\\ \text{FALSE},&\text{otherwise}\\\
\end{array}\right.$ (2)

Existing works involving 2-hop labeling scheme can be classified into two
categories. The approaches in the first category construct 2-hop labels based
on all nodes [4, 3, 7, 20, 19]. Considering that minimizing 2-hop label size
is NP-hard [4], Cohen et al. proposed a $(\log|V|)$-approximate solution.
However, the index construction cost is $O(|V||E|\log(|V|^{2}/|E|))$, which
makes it difficult to scale to large graphs. Motivated by this, the following
works [3, 7, 20, 19] have to discard the approximation guarantee and focused
on finding better ordering strategy to rank nodes, such that to improve the
efficiency of 2-hop label construction. Even though, the index size still
cannot be bounded w.r.t. the size of the input graph.

Different with the above approaches, approaches in the second category [9, 26]
generate partial 2-hop labels based on a few hop-nodes to cover as more
reachability relationships as possible. It was shown in [9, 26] that partial
2-hop labels can work very efficiently in answering reachability queries for
some graphs, due to that the partial 2-hop labels can cover most reachability
relationships for these graphs. Moreover, the index size of partial 2-hop
labels can be bounded, and is usually much smaller than that of the first kind
of approaches in practice. However, for some other graphs, they cannot work
efficiently [9, 26]. The query performance may degenerate due to small
reachability ratio for these graphs, as shown by Fig. 1. Therefore when
considering partial 2-hop labels for reachability queries processing, its
necessary that we can quickly know what is the reachability ratio w.r.t. a set
of hop-nodes for the underlying graphs, such that we can correctly decide
whether we should use partial 2-hop labels, and further, we can decide how
many hop-nodes should be chosen to construct partial 2-hop labels.

Other Reachability Approaches: Besides approaches that use (partial) 2-hop
labels, researchers also proposed other approaches that do not involve 2-hop
labels, including [15, 16, 12, 9, 14, 18, 21]. These approaches assign each
node $u$ a label that maintains partial TC. For a given reachability query
${u}?\rightsquigarrow{v}$, we may need to conduct depth-first search (DFS) or
breadth-first search (BFS) from $u$ to check whether $u$ can reach $v$, if we
cannot get the result by comparing labels of $u$ and $v$.

##  3 The Baseline Algorithm

To get the reachability ratio of $S_{k}$, we need to solve two tasks. One is
constructing partial 2-hop labels, the other is computing the reachability
ratio. In this section, we first analyze the construction of 2-hop labels and
the computation of reachability ratio, then give out the baseline algorithm
for reachability ratio computation.

Step-1: 2-hop Labels Construction. To construct 2-hop labels, existing
approaches need to sort all nodes based on a certain rank value, such as
degree [7, 20] or closeness [29]. The result of the sorting operation is
$v_{1},v_{2},...,\cdots,v_{|V|}$, where the first (last) node has the largest
(smallest) rank value. Based on the sorting result, we select the first $k$
nodes as hop-nodes to get the hop-node set
$S_{k}=\\{v_{1},v_{2},...,v_{k}\\}$. We have the following result w.r.t. the
hop-node sets (Equations 3 and 4).

$\emptyset=S_{0}\subset S_{1}\subset S_{2}\subset\cdots\subset S_{|V|}=V$ (3)

$S_{i}\setminus S_{i-1}=\\{v_{i}\\}\text{, where}~{}0<i\leq|V|$ (4)

Given a set $S_{i}$ of $i$ hop-nodes, its 2-hop labels $\mathcal{L}_{i}$ can
be generated by processing $v_{i}$ based on $\mathcal{L}_{i-1}$ according to
Equations 3 and 4. Specifically, we first perform forward BFS from $v_{i}$ to
get a set $D_{i}$ of nodes that $v_{i}$ can reach. Second, we perform backward
BFS from $v_{i}$ to get a set $A_{i}$ of nodes that can reach $v_{i}$, as
denoted by Figure LABEL:graph:ourapproach-idea(a). We call $A_{i}$ the
ancestor set of $v_{i}$, and $D_{i}$ the descendant set of $v_{i}$. For each
node $a\in A_{i}$, we add $v_{i}$ to $a$’s out-label, i.e.,
$L^{{i}}_{out}({a})=L^{{i-1}}_{out}({a})\cup\\{v_{i}\\}$, denoting that $a$
can reach $v_{i}$. For each node $d\in D_{i}$, we add $v_{i}$ to $d$’s in-
label, i.e., $L^{{i}}_{in}({d})=L^{{i-1}}_{in}({d})\cup\\{v_{i}\\}$, denoting
that $v_{i}$ can reach $d$. After processing $v_{i}$, we get 2-hop labels
$\mathcal{L}_{i}$. The superscript $i$ in
$L^{{i}}_{out}({a})(L^{{i}}_{in}({a}))$ denotes that both 2-hop labels
$L^{{i}}_{out}({a})$ and $L^{{i}}_{in}({a})$ w.r.t. node $a$ are subsets of
$S_{i}$, i.e., they contain only nodes of $S_{i}$. When $i=|V|$, then
$S_{i}=V$, the 2-hop labels of $a$ are subsets of $V$. In this case, all nodes
are hop-nodes and we do not use superscript in 2-hop labels for simplicity,
i.e., $L^{{|V|}}_{out}({a})=L_{out}({a})$ and
$L^{{|V|}}_{in}({a})=L_{in}({a})$.

It is worth noting that we can use 2-hop labels $\mathcal{L}_{i-1}$ to reduce
the size of both $A_{i}$ and $D_{i}$ by checking whether we can terminate the
BFS traversal from $v_{i}$ in advance. For example, consider Figure
LABEL:graph:ourapproach-idea(c), where both $v_{i-1}$ and $v_{i}$ are hop-
nodes and $v_{i}$ is processed after $v_{i-1}$. After processing $v_{i-1}$, we
have $\mathcal{L}_{i-1}$. When processing $v_{i}$, the backward BFS traversal
from $v_{i}$ can be terminated at $v_{i-1}$, due to that $v_{i-1}$ can reach
$v_{i}$ can be answered by $\mathcal{L}_{i-1}$, and $\forall a\in
TC^{-1}(v_{i-1})$ that can reach $v_{i}$ through $v_{i-1}$ can also be
answered by $\mathcal{L}_{i-1}$. Therefore in practice, $A_{i}\subseteq
in^{*}({v_{i}})\wedge D_{i}\subseteq out^{*}({v_{i}})$.

Figure 3: A sample DAG $G$. TABLE II: The partial 2-hop labels $\mathcal{L}_{1},\mathcal{L}_{2},\mathcal{L}_{3}$ constructed based on $S_{1}=\\{v_{1}\\},S_{2}=\\{v_{1},v_{2}\\}$ and $S_{3}=\\{v_{1},v_{2},v_{3}\\}$, respectively. Node | $\mathcal{L}_{1}$ | $\mathcal{L}_{2}$ | $\mathcal{L}_{3}$
---|---|---|---
|  $L^{{1}}_{out}({v})$ |  $L^{{1}}_{in}({v})$ |  $L^{{2}}_{out}({v})$ |  $L^{{2}}_{in}({v})$ |  $L^{{3}}_{out}({v})$ |  $L^{{3}}_{in}({v})$
$v_{1}$ | 1 | 1 | 1 | 1 | 1 | 1
$v_{2}$ |  | 1 | 2 | 1,2 | 2 | 1,2
$v_{3}$ |  |  | 2 |  | 2,3 | 3
$v_{4}$ | 1 |  | 1 |  | 1,3 |
$v_{5}$ |  |  | 2 |  | 2,3 |
$v_{6}$ | 1 |  | 1 |  | 1,3 |
$v_{7}$ |  | 1 |  | 1 |  | 1,3
$v_{8}$ |  |  |  |  |  | 3
$v_{9}$ |  | 1 |  | 1 |  | 1,3
$v_{10}$ |  | 1 |  | 1,2 |  | 1,2
$v_{11}$ | 1 |  | 1 |  | 1,3 |
$v_{12}$ |  |  | 2 |  | 2 |
$v_{13}$ |  | 1 |  | 1,2 |  | 1,2
$v_{14}$ |  |  |  |  |  | 3
$v_{15}$ |  | 1 |  | 1,2 |  | 1,2

###### Example 1

Consider $G$ in Figure 3. Assume that we want to construct partial 2-hop
labels $\mathcal{L}_{2}$. The first thing we need to do is to sort all nodes
by a certain rank value. In this paper, we follow the tradition [20, 7] and
take $(|out({v})|+1)\times(|in({v})|+1)$ as $v$’s rank value for sorting. The
sorting result is $v_{1},v_{2},v_{3},...,v_{15}$. To get $\mathcal{L}_{2}$, we
first process $v_{1}$ by performing both forward and backward BFS from $v_{1}$
to get $A_{1}=\\{v_{1},v_{4},v_{6},v_{11}\\}$ and
$D_{1}=\\{v_{1},v_{2},v_{7},v_{9},v_{10},v_{13},v_{15}\\}$. After that, we add
1 to out label of nodes in $A_{1}$ and in label of nodes in $D_{1}$. Then, we
get $\mathcal{L}_{1}$. The next processed node is $v_{2}$. Similarly, we
perform forward and backward BFS from $v_{2}$ to get
$A_{2}=\\{v_{2},v_{3},v_{5},v_{12}\\}$ and
$D_{2}=\\{v_{2},v_{10},v_{13},v_{15}\\}$. Note that all nodes in $A_{1}$ can
reach $v_{2}$, but some of them are not included in $A_{2}$, due to that for
nodes that are in $A_{1}$ but not included in $A_{2}$, they can reach $v_{2}$
can be answered by $\mathcal{L}_{1}$. Then, we add 2 to out and in label of
nodes in $A_{2}$ and $D_{2}$, as shown by Table II. $\Box$

Step-2: Reachability Ratio Computation. Given 2-hop labels $\mathcal{L}_{k}$
w.r.t. $S_{k}$, the baseline approach computes the reachability ratio of
$S_{k}$ as follow. First, it computes the set of nodes that can reach either
one of the set of hop-nodes, as shown by Equation 5. Second, it computes the
set of nodes that can be reached by either one of the set of hop-nodes, as
shown by Equation 6. It computes the number of reachable queries that can be
answered by $\mathcal{L}_{k}$, as shown by Equation 7. At last, we return the
reachability ratio of 2-hop labels w.r.t. $S_{k}$ based on Equation 1.

$A=\bigcup_{i\in[1,k]}A_{i}$ (5)

$D=\bigcup_{i\in[1,k]}D_{i}$ (6)

$\begin{split}N_{k}=|\\{(a,d)|&a\in A,d\in D,a\neq d\,\\\
&L^{{k}}_{out}({a})\cap L^{{k}}_{in}({d})\neq\emptyset\\}|\end{split}$ (7)

###### Example 2

Continue Example 1. To compute the reachability ratio of
$S_{2}=\\{v_{1},v_{2}\\}$, we first compte $A=A_{1}\cup
A_{2}=\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{11},v_{12}\\}$, $D=D_{1}\cup
D_{2}=\\{v_{1},v_{2},v_{7},v_{9},v_{10},v_{13},v_{15}\\}$ according to
Equations 5 and 6, respectively. At last, we check for each pair of nodes
$a\in A$ and $d\in D(a\neq d)$ , whether $a$ can reach $d$ can be answered by
$\mathcal{L}_{2}$. And compute the number of answered reachable queries
according to Equation 7, which is 42 for $G$ in Figure 3 and $\mathcal{L}_{2}$
in Table II. Given $TC(G)=70$, we know that the reachability ratio of $S_{2}$
is $42/70=60\%$. $\Box$

The Algorithm: The baseline algorithm to compute reachability ratio is shown
in Algorithm 1, which works in two steps. Step-1 (lines 1-17) constructs 2-hop
labels $\mathcal{L}_{k}$ of $k$ hop-nodes and gets the two set of nodes $A$
and $D$. Specifically, it first sorts all nodes in certain order in line 2,
then selects $k$ hop-nodes in line 3. In lines 4-15, it performs forward and
backward BFS from each hop-node $v_{i}$ to construct 2-hop labels
$\mathcal{L}_{i}$. During the processing, only if the reachability
relationship between $v_{i}$ and the visited node $v$ cannot be answered by
2-hop labels $\mathcal{L}_{i-1}$, it adds $v_{i}$ to $v$’s in-label (line 8)
or out-label (line 13), and adds $v$ to $D_{i}$ (line 9) or $A_{i}$ (line 14);
otherwise, it terminates the processing due to that the reachability
relationship has already been covered by $\mathcal{L}_{i-1}$. In lines 16-17,
it gets the two sets $A$ and $D$ according to Equations 5 and 6. Step-2 (lines
18-20) computes the number of covered reachable queries by $\mathcal{L}_{k}$
according to Equation 7. Finally, it computes and returns the reachability
ratio in line 21.

1

2

3 1 $N_{k}\leftarrow
0,S_{k}\leftarrow\emptyset,A\leftarrow\emptyset,D\leftarrow\emptyset$

4 2 rank nodes in $G$ in a certain order

5 3 put the first $k$ nodes into $S_{k}$ as hop-nodes

6 4 foreach $(v_{i}\in S_{k})$ do

7 5 $A_{i}\leftarrow\emptyset$; $D_{i}\leftarrow\emptyset$

8 6 perform forward BFS from $v_{i}$, and for each visited $v$

9 7 if $(L^{{i-1}}_{out}({v_{i}})\bigcap L^{{i-1}}_{in}({v})=\emptyset)$ then
/*$\mathcal{L}_{i-1}$*/

10 8 $L^{{i}}_{in}({v})\leftarrow L^{{i-1}}_{in}({v})\bigcup\\{v_{i}\\}$
/*compute $\mathcal{L}_{i}$*/

11 9 $D_{i}\leftarrow D_{i}\cup\\{v\\}$

1210 else stop expansion from $v$

1311 perform backward BFS from $v_{i}$, and for each visited $v$

1412 if $(L^{{i-1}}_{out}({v})\bigcap L^{{i-1}}_{in}({v_{i}})=\emptyset)$ then
/*$\mathcal{L}_{i-1}$*/

1513 $L^{{i}}_{out}({v})\leftarrow L^{{i-1}}_{out}({v})\bigcup\\{v_{i}\\}$
/*compute $\mathcal{L}_{i}$*/

1614 $A_{i}\leftarrow A_{i}\cup\\{v\\}$

1715 else stop expansion from $v$

1816 $A=\bigcup_{i\in[1,k]}A_{i}$

1917 $D=\bigcup_{i\in[1,k]}D_{i}$

2018 foreach $(a\in A,d\in D,a\neq d)$ do

2119 if $(L^{{k}}_{out}({a})\bigcap L^{{k}}_{in}({d})\neq\emptyset)$ then
/*$\mathcal{L}_{k}$*/

2220 $N_{k}\leftarrow N_{k}+1$

2321 return $\alpha\leftarrow N_{k}/TC(G)$ as reachability ratio of $S_{k}$

Algorithm 1 blRR$(G=(V,E),k,TC(G))$

Analysis: For Step-1 (lines 1-17), the time cost of line 2 is $O(|V|)$ by
counting sort. The time cost of performing BFS from each hop-node $v_{i}$ is
$O(|V|+|E|)$ (lines 5-15). During the two BFS traversals, the time cost of
processing every visited node $v$ is $O(k)$ (lines 7 and 12). Thus the time
cost of 2-hop labels construction for each hop-node is $O(k(|V|+|E|))$, and
the time cost of processing $k$ hop-nodes, i.e., the time cost of Step-1 is
$O(k^{2}(|V|+|E|))$. For Step-2, the time cost is $O(k|A||D|)$. Therefore, the
time complexity of Algorithm 1 is $O(k^{2}(|V|+|E|)+k|A||D|)$.

During the processing, we do not need to actually maintain every $A_{i}$ and
$D_{i}$, instead, we only need to maintain $A$ and $D$. Further, we need to
maintain the 2-hop labels w.r.t. $k$ hop-nodes, the space cost is $O(k|V|)$.
As $S_{k},A$ and $D$ are bounded by $V$, the space complexity of Algorithm 1
is $O(k|V|)$.

In practice, if the reachability ratio is too small to meet the requirement,
we may need to use more hop-nodes, and therefore Algorithm 1 will be called
once more to compute the new reachability ratio, for which all reachability
relationships tested for $S_{k}$ will be tested again for the new hop-node
set.

###### Example 3

Continue Example 2. After getting $A=\\{v_{1},v_{2},v_{3},$
$v_{4},v_{5},v_{6},v_{11},v_{12}\\}$ and
$D=\\{v_{1},v_{2},v_{7},v_{9},v_{10},v_{13},v_{15}\\}$ during constructing
partial 2-hop labels, in lines 18-20, we need to test 56 reachability queries,
due to $|A|=8$ and $|D|=7$. By line 21, we know that the reachability ratio is
60%. If we set the threshold of the reachability ratio to be equal or greater
than 80%, then we need to enlarge the hop-node set and recompute the
reachability ratio from scratch. As a result, the 56 queries tested for
$S_{2}$ will be tested again for the new hop-node set. $\Box$

##  4 The Incremental Approach

Considering that when the hop-node set is enlarged, Algorithm 1 will be called
once more, and the set of reachability relationships tested for the first call
will be tested again for the second call, a natural question is: can we
compute the reachability ratio incrementally? That is, given the reachability
ratio w.r.t. $S_{i-1}$, when we decide to compute the reachability ratio
w.r.t. $i$ hop-nodes, i.e., $S_{i}=S_{i-1}\cup\\{v_{i}\\}$, we do not compute
the number of covered reachable queries from scratch, instead, we only compute
the number of increased reachable queries that cannot be covered by
$\mathcal{L}_{i-1}$, but can be covered by $\mathcal{L}_{i}$.

However, the increased reachability ratio cannot be easily computed. On one
hand, by constructing 2-hop labels using hop-node $v_{i}$, we capture three
kinds of reachability relationships: (1) $v_{i}$ can reach every node in
$D_{i}\setminus\\{v_{i}\\}$ can be determined by 2-hop labels w.r.t. $v_{i}$,
and the number of covered reachable queries is $|D_{i}|-1$; (2) every node in
$A_{i}\setminus\\{v_{i}\\}$ can reach $v_{i}$ can be determined by 2-hop
labels w.r.t. $v_{i}$, and the number of covered reachable queries is
$|A_{i}|-1$; and (3) each node in $A_{i}\setminus\\{v_{i}\\}$ can reach every
node in $D_{i}\setminus\\{v_{i}\\}$ can be determined by 2-hop labels w.r.t.
$v_{i}$, and the number of covered reachable queries is
$(|A_{i}|-1)\times(|D_{i}|-1)$. Thus the number of covered reachable queries
by 2-hop labels w.r.t. $v_{i}$ can be computed as
$(|A_{i}|-1)\times(|D_{i}|-1)+(|A_{i}|-1)+(|D_{i}|-1)=|A_{i}|\times|D_{i}|-1$.

On the other hand, 2-hop labels w.r.t. different hop-nodes may cover the same
reachable queries. For example, consider Figure LABEL:graph:ourapproach-
idea(b), where $v_{i-1}$ and $v_{i}$ are two hop-nodes, and $v_{i}$ is
processed after $v_{i-1}$. After processing $v_{i-1}$, every node $a_{1}\in
A_{i1}$ can reach every node $d_{1}\in D_{i1}$ can be covered by 2-hop labels
w.r.t. $v_{i-1}$, due to that $v_{i-1}\in L^{{i-1}}_{out}({a_{1}})\cap
L^{{i-1}}_{in}({d_{1}})$. After processing $v_{i}$, we also know that $a_{1}$
can reach $d_{1}$ can also be covered by 2-hop labels w.r.t. $v_{i}$, due to
that $v_{i}\in L^{{i}}_{out}({a_{1}})\cap L^{{i}}_{in}({d_{1}})$. Therefore,
the increased number of reachable queries w.r.t. $v_{i}$ can be computed as
Equations 8 and 9, and the total number of reachable queries $N_{k}$ covered
by $\mathcal{L}_{k}$ can be computed as Equation 10.

$n_{i}=|A_{i}|\times|D_{i}|-1-\lambda$ (8)

$\begin{split}\lambda=|\\{(a,d)|&a\in A_{i},d\in D_{i},a\neq d,\\\
&L^{{i-1}}_{out}({a})\cap L^{{i-1}}_{in}({d})\neq\emptyset\\}|\end{split}$ (9)

$N_{k}=\sum_{i\in[1,k]}n_{i}$ (10)

Therefore, to compute the number of reachable queries that cannot be covered
by $\mathcal{L}_{i-1}$ but can be covered by $\mathcal{L}_{i}$, the intuitive
way is firstly getting the two sets of nodes $A_{i}$ and $D_{i}$, then testing
for each pair of nodes $a\in A_{i}$ and $d\in D_{i}$, whether $a$ can reach
$d$ can be answered by $\mathcal{L}_{i-1}$. If $a$ can reach $d$ can be
answered by $\mathcal{L}_{i-1}$, it means that ${a}\rightsquigarrow{d}$ has
already been covered by $S_{i-1}$; otherwise, it is a new covered reachable
query and needs to be counted in, as shown by Algorithm 2.

1

2

3 1 $N_{0}\leftarrow 0$

4 2 rank nodes in $G$ in a certain order

5 3 put the first $k$ nodes into $S_{k}$ as hop-nodes

6 4 foreach $(v_{i}\in S_{k})$ do

7 5 $A_{i}\leftarrow\emptyset,D_{i}\leftarrow\emptyset$

8 6 perform forward BFS from $v_{i}$, and for each visited $v$

9 7 if $(L^{{i-1}}_{out}({v_{i}})\bigcap L^{{i-1}}_{in}({v})=\emptyset)$ then
/*$\mathcal{L}_{i-1}$*/

10 8 $D_{i}\leftarrow D_{i}\cup\\{v\\}$

11 9 else stop expansion from $v$

1210 perform backward BFS from $v_{i}$, and for each visited $v$

1311 if $(L^{{i-1}}_{out}({v})\bigcap L^{{i-1}}_{in}({v_{i}})=\emptyset)$ then
/*$\mathcal{L}_{i-1}$*/

1412 $A_{i}\leftarrow A_{i}\cup\\{v\\}$

1513 else stop expansion from $v$

1614 $\lambda\leftarrow 0$

1715 foreach $(a\in A_{i},d\in D_{i},a\neq d)$ do

1816 if $(L^{{i-1}}_{out}({a})\bigcap L^{{i-1}}_{in}({d})\neq\emptyset)$ then
/*$\mathcal{L}_{i-1}$*/

1917 $\lambda\leftarrow\lambda+1$

2018 $n_{i}\leftarrow|A_{i}|\times|D_{i}|-1-\lambda$

2119 $N_{i}\leftarrow N_{i-1}+n_{i}$

2220 $\alpha\leftarrow N_{i}/TC(G)$ /*reachability ratio of $S_{i}$*/

2321 foreach $(a\in A_{i})$ do /*compute $\mathcal{L}_{i}$*/

2422 $L^{{i}}_{out}({a})\leftarrow L^{{i-1}}_{out}({a})\bigcup\\{v_{i}\\}$

2523 foreach $(d\in D_{i})$ do /*compute $\mathcal{L}_{i}$*/

2624 $L^{{i}}_{in}({d})\leftarrow L^{{i-1}}_{in}({d})\bigcup\\{v_{i}\\}$

2725 return $\alpha$ as reachability ratio of $S_{k}$

Algorithm 2 incRR$(G=(V,E),k,TC(G))$

In Algorithm 2, we compute reachability ratio for each $S_{i}$ when
$v_{i}(i\in[1,k])$ is added into $S_{i-1}$. For each processed $v_{i}$ (lines
4-24), we first perform forward and backward BFS from $v_{i}$ to get the two
set of nodes $A_{i}$ and $D_{i}$ (lines 5-13). In lines 14-17, we compute the
number of reachable queries that can be covered by $\mathcal{L}_{i-1}$. After
that, we get the increased number of reachable queries that can be covered by
$\mathcal{L}_{i}$ but cannot be covered by $\mathcal{L}_{i-1}$ in line 18
according to Equation 8. In line 19, we get the total number of reachable
queries covered by $\mathcal{L}_{i}$, and get the reachability ratio of
$S_{i}$ in line 20. We compute $\mathcal{L}_{i}$ based on $\mathcal{L}_{i-1}$
in lines 21-24. At last, we return the reachability ratio of $S_{k}$ in line
25.

It is worth noting that for Algorithm 2, when processing the first hop-node
$v_{1}$, we do not need to actually execute lines 15-17, due to that for
$v_{1}$, $A_{1}=in^{*}({v_{1}})$ and $D_{1}=out^{*}({v_{1}})$, we can directly
get $n_{i}=|A_{i}|\times|D_{i}|-1$ and the corresponding reachability ratio.

Analysis: Different with Algorithm 1, Algorithm 2 performs Step-1 by first
computing the two sets $A_{i}$ and $D_{i}$ in lines 1-13, then computing
$\mathcal{L}_{i}$ in lines 21-24. The overall cost is same as that of
Algorithm 1, i.e., $O(k^{2}(|V|+|E|))$.

The difference between Algorithm 1 and Algorithm 2 lies in Step-2 (lines
14-20), i.e., how to compute the increased number of reachable queries that
cannot be covered by $\mathcal{L}_{i-1}$ but can be covered by
$\mathcal{L}_{i}$ based on Equation 8. The cost of Step-2 for each hop-node is
$O(i|A_{i}||D_{i}|)$. For $k$ hop-node, the cost is therefore
$O(\sum_{i\in[1,k]}i|A_{i}||D_{i}|)$.

Therefore, the time complexity of Algorithm 2 is
$O(k^{2}(|V|+|E|)+\sum_{i\in[1,k]}i|A_{i}||D_{i}|)$.

Similar to Algorithm 1, we need to maintain the 2-hop labels w.r.t. at most
$k$ hop-nodes during the processing. As $A_{i}$ and $D_{i}$ are bounded by
$V$, and $A_{i}(D_{i})$ can be used to store nodes of $A_{i+1}(D_{i+1})$, the
space complexity of Algorithm 2 is $O(k|V|)$.

###### Example 4

Consider $G$ in Figure 3. Assume that we want to construct partial 2-hop
labels $\mathcal{L}_{3}$.

The first node to be processed is $v_{1}$, and the partial 2-hop labels are
shown in Table II. As $A_{1}=\\{v_{1},v_{4},v_{6},v_{11}\\}$,
$D_{1}=\\{v_{1},v_{2},v_{7},v_{9},v_{10},v_{13},v_{15}\\}$, thus we know that
$N_{1}=n_{1}=|A_{1}|\times|D_{1}|-1=27$. The second processed node is $v_{2}$
and the partial 2-hop labels are shown in Table II. By lines 5-13, we have
that $A_{2}=\\{v_{2},v_{3},v_{5},v_{12}\\}$,
$D_{2}=\\{v_{2},v_{10},v_{13},v_{14}\\}$. Then, in lines 15-17, we need to
test $|A_{2}|\times|D_{2}|=16$ reachability queries. The result is
$\lambda=0$, thus $n_{2}=|A_{2}|\times|D_{2}|-1-0=15$, and
$N_{2}=n_{1}+n_{2}=27+15=42$. The third processed node is $v_{3}$. By lines
5-13, we have that $A_{3}=\\{v_{3},v_{4},v_{5},v_{6},v_{11}\\}$,
$D_{3}=\\{v_{3},v_{7},v_{8},v_{9},v_{14}\\}$. Then, in lines 15-17, we need to
test $|A_{3}|\times|D_{3}|=25$ reachability queries. The result is
$\lambda=6$, thus $n_{3}=|A_{3}|\times|D_{3}|-1-6=18$, and
$N_{3}=N_{2}+n_{3}=42+18=60$. After processing $v_{1},v_{2}$ and $v_{3}$, we
have $\mathcal{L}_{3}$ shown in Table II, and the reachability ratio is
$60/70=85.7$% by testing $16+25=41$ reachability queries for Algorithm 2.

As a comparison, when using Algorithm 1, $|A_{3}|=8$, $|D_{3}|=10$, and we
need to test 80 reachability queries to get the reachability ratio. $\Box$

Note that, since a reachable query ${a}\rightsquigarrow{d}$ may be covered by
2-hop labels w.r.t. different hop-nodes, compared with Algorithm 1, Algorithm
2 may test the reachability relationship between $a$ and $d$ in line 16 more
than once. However, it is still valuable due to that (1) only a part of
reachable queries, rather than all, need to be tested more than once, and (2)
we can terminate the computation whenever we find that reachability ratio of
$S_{i}$ is good enough in line 20. As a comparison, Algorithm 1 may be called
more than once before getting a reachability ratio meeting the requirement.
When it is called again due to the enlarged hop-node set, all previously
tested queries will be tested once more.

##  5 The Incremental-Partition Approach

###  5.1 The Equivalence Relationship

By comparing Algorithm 1 and Algorithm 2, we know that the key factor that
affects the overall performance is the total number of tested reachability
queries, which dominates the cost of Step-2, as indicated by their time
complexities. Even though Algorithm 2 does not need to compute reachability
ratio from scratch when the hop-node set becomes large by adding one more hop-
node $v_{i}$, it still needs to test $|A_{i}|\times|D_{i}|$ reachability
queries in line 16 with cost $O(i|A_{i}||D_{i}|)$. Given a large hop-node set,
the cost could be unaffordable.

###### Definition 1

[Equivalence Relationship] Given a hop-node $v_{i}$, its ancestor set $A_{i}$
and descendant set $D_{i}$. We say two nodes $a_{1},a_{2}(a_{1}\neq a_{2})$ of
$A_{i}$ are forward equivalent to each other, denoted as
$a_{1}\equiv_{F}a_{2}$, if they have the same out-label, i.e.,
$L^{{i}}_{out}({a_{1}})=L^{{i}}_{out}({a_{2}})$. Similarly, we say two nodes
$d_{1},d_{2}(d_{1}\neq d_{2})$ of $D_{i}$ are backward equivalent to each
other, denoted as $d_{1}\equiv_{B}d_{2}$, if they have the same in-label,
i.e., $L^{{i}}_{in}({d_{1}})=L^{{i}}_{in}({d_{2}})$.

By Definition 1, we can get, for $A_{i}$, a partition
$\mathcal{A}{(i)}=\\{A_{i1},A_{i2},...,A_{im}\\}$, which consists of a set of
$m$ disjoint subsets satisfying that (1) $\forall l,j\in[1,m],l\neq
j,A_{il}\cap A_{ij}=\emptyset$ and $\cup_{l\in[1,m]}A_{il}=A_{i}$; and (2)
$\forall a_{l},a_{j}$ belonging to the same subset, $a_{l}\equiv_{F}a_{j}$.

###### Theorem 1

Let $a_{1}$ and $a_{2}$ be two nodes satisfying that $a_{1}$ and $a_{2}$ are
forward equivalent to each other $(a_{1}\equiv_{F}a_{2})$. For $\forall d\in
V$, we have that $L^{{i}}_{out}({a_{1}})\cap
L^{{i}}_{in}({d})=L^{{i}}_{out}({a_{2}})\cap L^{{i}}_{in}({d})$.

###### Proof:

The correctness is obvious, due to that $a_{1}$ and $a_{2}$ are forward
equivalent to each other, which means that they have the same out-label.
$\Box$ ∎

Based on this result, for each subset $A_{ij}\in\mathcal{A}{(i)}$, to know the
reachability relationship from all nodes of $A_{ij}$ to $\forall d\in V$, we
do not need to test $|A_{ij}|$ reachability queries, instead, we only need to
test one reachability query, due to that all nodes of $A_{ij}$ are forward
equivalent to each other.

For $D_{i}$, we also have a partition
$\mathcal{D}{(i)}=\\{D_{i1},D_{i2},...,D_{in}\\}$ satisfying that (1) $\forall
l,j\in[1,n],l\neq j,D_{il}\cap D_{ij}=\emptyset$ and
$\cup_{j\in[1,n]}D_{ij}=D_{i}$; and (2) $\forall d_{l},d_{j}$ belonging to the
same subset, $d_{l}\equiv_{B}d_{j}$. And similarly, for each subset
$D_{ij}\in\mathcal{D}{(i)}$, to know the reachability relationship from any
node to all nodes of $D_{ij}$, we do not need to test $|D_{ij}|$ reachability
queries, instead, the number of tested reachability queries can be reduced to
one, due to that all nodes of $D_{ij}$ are backward equivalent to each other.

###### Theorem 2

Given a hop-node $v_{i}$, its ancestor set $A_{i}$ and descendant set $D_{i}$,
the number of tested reachability queries for reachability ratio computation
is $|\mathcal{A}{(i)}|\times|\mathcal{D}{(i)}|$, which is bounded by
$\min\\{|A_{i}|\times|D_{i}|,4^{i-1}\\}$.

###### Proof:

Let $\mathcal{A}{(i)}(\mathcal{D}{(i)})$ be the partition of $A_{i}(D_{i})$
based on the equivalence relationship,
$\mathcal{P}_{A}{(i)}(\mathcal{P}_{D}{(i)})$ the partition of $V$ w.r.t. hop-
node set $S_{i}$ and forward (backward) equivalence relationship, i.e., all
nodes in each subset have the same out-label (in-label), which is a subset of
$S_{i}$. Initially,
$\mathcal{A}{(1)}=\\{A_{1}\\}(\mathcal{D}{(1)}=\\{D_{1}\\})$,
$\mathcal{P}_{A}{(1)}=\\{A_{1},V\setminus
A_{1}\\}(\mathcal{P}_{D}{(1)}=\\{D_{1},V\setminus D_{1}\\})$.

On one hand, according to Theorem 1, for each subset
$A_{il}\in\mathcal{A}{(i)}$, the result of testing all the reachability
relationships from nodes of $A_{il}$ to any other node is same to each other,
thus we only need to randomly pick a node and take it as the representative
node of $A_{il}$ to perform the testing of reachability relationship.
Similarly, for each subset $D_{ij}\in\mathcal{D}{(i)}$ based on backward
equivalence relationship, we can also randomly pick a node and take it as the
representative node of $D_{ij}$ to test the reachability relationships from
any node to all nodes of $D_{ij}$. As a result, the number of tested
reachability queries from nodes of $A_{i}$ to nodes of $D_{i}$ is
$|\mathcal{A}{(i)}|\times|\mathcal{D}{(i)}|$. Since
$\mathcal{A}{(i)}(\mathcal{D}{(i)})$ is the partition of $A_{i}(D_{i})$, we
know that
$|\mathcal{A}{(i)}|\times|\mathcal{D}{(i)}|\leq|A_{i}|\times|D_{i}|$.

On the other hand, given the partition
$\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$ of $V$, the size of
$\mathcal{P}_{A}{(i)}(\mathcal{P}_{D}{(i)})$ is at most twice bigger than that
of $\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$. The reason lies in that
all nodes in each subset of $\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$
can be further divided into at most two disjoint subsets. One consists of
nodes that can reach (be reached by) $v_{i}$, and the other contains nodes
that cannot reach (be reached by) $v_{i}$. Then, the size of
$\mathcal{P}_{A}{(i)}(\mathcal{P}_{D}{(i)})$ is bounded by $2^{i}$, and the
size of $\mathcal{A}{(i)}(\mathcal{D}{(i)})$ is bounded by $2^{i-1}$, thus the
the number of tested reachability queries is bounded by $2^{i-1}\times
2^{i-1}=4^{i-1}$.

In summary, we know that the number of tested reachability queries for
reachability ratio computation w.r.t. hop-node $v_{i}$ is bounded by
$\min\\{|A_{i}|\times|D_{i}|,4^{i-1}\\}$. $\Box$

∎

According to Theorem 2, we can reduce the number of tested reachability
queries when processing hop-node $v_{i}$.

As shown by Equation 11, for each pair of subsets
$(A_{il}\in\mathcal{A}{(i)},D_{ij}\in\mathcal{D}{(i)})$, we only need to check
the reachability relationship between their representative nodes $a\in A_{il}$
and $d\in D_{ij}$. If $a$ can reach $d$ can be answered by
$\mathcal{L}_{i-1}$, it means that all the reachable relationships from each
node of $A_{il}$ to every node of $D_{ij}$ can be answered by
$\mathcal{L}_{i-1}$. To do that, the first thing we need to do is getting the
partitions of both $A_{i}$ and $D_{i}$ according to equivalence relationship.

$\lambda=\sum_{\begin{subarray}{c}a\in A_{il}\in\mathcal{A}{(i)}\\\ d\in
D_{ij}\in\mathcal{D}{(i)}\\\ L^{{i-1}}_{out}({a})\cap
L^{{i-1}}_{in}({d})\neq\emptyset\end{subarray}}|A_{il}|\times|D_{ij}|$ (11)

###  5.2 Partitions Computation

To get the partitions of both $A_{i}$ and $D_{i}$, we need to compare the
labels of nodes in $A_{i}$ and $D_{i}$, such that nodes with same labels can
be clustered together. The naive way to do this is based on pairwise comparing
node labels, which is expensive in practice. It is worth noting that the out-
label and in-label of a node are sorted in advance, this actually can be done
without additional cost, due to that these labels are used to check whether
their set-intersection is empty, which means that we can store the processing
order of hop-nodes, rather than their IDs, in these labels. In this way, the
integers in both out-label and in-label of any node are naturally sorted, as
shown by Table II. With this result, we can sort all nodes in $A_{i}(D_{i})$
by comparing their out-labels (in-labels) in lexicographic order. After the
sorting operation, all equivalent nodes are clustered together. As the size of
each label is bounded by $i$, the cost of computing the partition
$\mathcal{A}{(i)}(\mathcal{D}{(i)})$ of $A_{i}(D_{i})$ is
$O(i\times|A_{i}|\times\log|A_{i}|)(O(i\times|D_{i}|\times\log|D_{i}|))$.

Let $\mathcal{P}_{A}{(i)}$ be the partition of $V$ w.r.t. hop-node set $S_{i}$
and forward equivalence relationship, i.e., all nodes in each subset have the
same out-label, which is a subset of $S_{i}$, $\mathcal{P}_{D}{(i)}$ the
partition of $V$ w.r.t. $S_{i}$ and backward equivalence relationship, i.e.,
all nodes in each subset have the same in-label, which is also a subset of
$S_{i}$. We have the following result.

###### Theorem 3

Given the hop-node $v_{i}$ and its ancestor (descendant) set $A_{i}(D_{i})$,
for $\forall v_{1},v_{2}\in A_{i}(D_{i})$,
$v_{1}\equiv_{F}v_{2}(v_{1}\equiv_{B}v_{2})$, iff they belong to the same
subset of $\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$.

###### Proof:

We prove this result from two aspects. First, we prove the correctness when
both $v_{1}$ and $v_{2}$ belong to $A_{i}$ (Case-1), then we prove the
correctness when both $v_{1}$ and $v_{2}$ belong to $D_{i}$ (Case-2).

Case-1 where $v_{1},v_{2}\in A_{i}$ and $v_{i}\in L^{{i}}_{out}({v_{1}})\cap
L^{{i}}_{out}({v_{2}})$.

On one hand, if $v_{1}\equiv_{F}v_{2}$, it means that
$L^{{i}}_{out}({v_{1}})=L^{{i}}_{out}({v_{2}})$ according to Definition 1.
Hence,
$L^{{i}}_{out}({v_{1}})\setminus\\{v_{i}\\}=L^{{i}}_{out}({v_{2}})\setminus\\{v_{i}\\}$,
i.e., they belong to the same subset of $\mathcal{P}_{A}{(i-1)}$.

On the other hand, if both $v_{1}$ and $v_{2}$ belong to the same subset of
$\mathcal{P}_{A}{(i-1)}$, it means that before processing hop-node $v_{i}$,
$L^{{i-1}}_{out}({v_{1}})=L^{{i-1}}_{out}({v_{2}})$ according to the
definition of $\mathcal{P}_{A}{(i-1)}$. As $v_{1},v_{2}\in A_{i}$, we know
that after processing $v_{i}$, $v_{i}\in L^{{i}}_{out}({v_{1}})\cap
L^{{i}}_{out}({v_{2}})$ and $L^{{i}}_{out}({v_{1}})=L^{{i}}_{out}({v_{2}})$
still holds. According to Definition 1, $v_{1}\equiv_{F}v_{2}$.

Therefore we have that $v_{1}\equiv_{F}v_{2}$, iff they belong to the same
subset of $\mathcal{P}_{A}{(i-1)}$.

Case-2 where $v_{1},v_{2}\in D_{i}$ and $v_{i}\in L^{{i}}_{in}({v_{1}})\cap
L^{{i}}_{in}({v_{2}})$.

Similar to the proof of Case-1, we know that $v_{1}\equiv_{B}v_{2}$, iff they
belong to the same subset of $\mathcal{P}_{D}{(i-1)}$.

By considering both the two cases, we know that for $\forall v_{1},v_{2}\in
A_{i}(D_{i})$, $v_{1}\equiv_{F}v_{2}(v_{1}\equiv_{B}v_{2})$, iff they belong
to the same subset of $\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$. $\Box$
∎

According to Theorem 3, we assign each node $v$ two set IDs, denoted as
$id_{A}({v})$ and $id_{D}({v})$, which are used to check which subset it
belongs to in $\mathcal{P}_{A}{(i)}$ and $\mathcal{P}_{D}{(i)}$, respectively.
Then, given the ancestor (descendant) set $A_{i}(D_{i})$ of $v_{i}$, we only
need to scan all nodes of $A_{i}(D_{i})$ once, and know immediately that for
two nodes $v_{1}$ and $v_{2}$, if
$id_{A}({v_{1}})=id_{A}({v_{2}})(id_{D}({v_{1}})=id_{D}({v_{2}}))$ in
$\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$, then
$v_{1}\equiv_{F}v_{2}(v_{1}\equiv_{B}v_{2})$ and will definitely belong to the
same subset of $\mathcal{P}_{A}{(i)}(\mathcal{P}_{D}{(i)})$. Therefore,
$\mathcal{P}_{A}{(i)}(\mathcal{P}_{D}{(i)})$ is a refinement of
$\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$, i.e., each element of
$\mathcal{P}_{A}{(i)}(\mathcal{P}_{D}{(i)})$ is a subset of a unique element
of $\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$.

Recall that when processing the hop-node $v_{i}$, we first have its ancestor
(descendant) set $A_{i}(D_{i})$, then get the partition
$\mathcal{A}{(i)}(\mathcal{D}{(i)})$ of $A_{i}(D_{i})$ based on equivalence
relationship. Since $\mathcal{P}_{A}{(i)}(\mathcal{P}_{D}{(i)})$ is the
partition of $V$ w.r.t. equivalence relationship, we know that
$\mathcal{A}{(i)}\subset\mathcal{P}_{A}{(i)}(\mathcal{D}{(i)}\subset\mathcal{P}_{D}{(i)})$,
and the relationship between $\mathcal{P}_{A}{(i)}(\mathcal{P}_{D}{(i)})$,
$\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$ and
$\mathcal{A}{(i)}(\mathcal{D}{(i)})$ are shown as Equations 12-13.

$\mathcal{P}_{A}{(i)}=\\{P\setminus
A_{i}|P\in\mathcal{P}_{A}{(i-1)}\\}\cup\mathcal{A}{(i)}$ (12)

$\mathcal{P}_{D}{(i)}=\\{P\setminus
D_{i}|P\in\mathcal{P}_{D}{(i-1)}\\}\cup\mathcal{D}{(i)}$ (13)

When processing hop-node $v_{i}$, since we only need to check the reachability
relationships from nodes of $A_{i}$ to $D_{i}$, we choose to maintain the
information of both $\mathcal{P}_{A}{(i)}(\mathcal{P}_{D}{(i)})$ and
$\mathcal{A}{(i)}(\mathcal{D}{(i)})$ using the set ID of each node to
facilitate partitions computation. Specifically, we use a hash table
$H_{A}(H_{D})$ to help achieve linear-time complexity. Each element of
$H_{A}(H_{D})$ is a tuple $(id_{o},e_{n})$ denoting a subset $A_{il}(D_{il})$
of $\mathcal{A}{(i)}(\mathcal{D}{(i)})$, where $id_{o}$ is, for all nodes of
$A_{il}(D_{il})$, their old set ID in
$\mathcal{P}_{A}{(i-1)}(\mathcal{P}_{D}{(i-1)})$, $e_{n}=(id_{n},v_{1},s)$ is
a triple denoting the new set ID for all nodes of $A_{il}(D_{il})$, the
representative node of $A_{il}(D_{il})$, and the size of $A_{il}(D_{il})$,
respectively.

###### Example 5

Consider $G$ in Figure 3. Before processing $v_{1}$,
$\mathcal{P}_{A}{(0)}=\mathcal{P}_{D}{(0)}=\\{V\\}$,
$\mathcal{A}{(0)}=\mathcal{D}{(0)}=\emptyset$, and for all nodes $v$,
$id_{A}({v})=id_{D}({v})=0$.

For the first node $v_{1}$, $A_{1}=\\{v_{1},v_{4},v_{6},v_{11}\\}$,
$D_{1}=\\{v_{1},v_{2},v_{7},v_{9},v_{10},v_{13},v_{15}\\}$. Since all nodes in
$A_{1}(D_{1})$ have the same $id_{A}({v})(id_{D}({v}))$, we know that
$\mathcal{A}{(1)}=\\{A_{1}\\}$ and $\mathcal{D}{(1)}=\\{D_{1}\\}$.
$\mathcal{P}_{A}{(1)}=\\{A_{1},V\setminus A_{1}\\}$ and
$\mathcal{P}_{D}{(1)}=\\{D_{1},V\setminus D_{1}\\}$. In Table III, the two
columns under $v_{1}$ denote $\mathcal{P}_{A}{(1)}$ and
$\mathcal{P}_{D}{(1)}$, where each 1 in the second (third) column corresponds
a node in $A_{1}(D_{1})$. Figure LABEL:graph:hash(a) shows the two hash tables
denoting $\mathcal{A}{(1)}$ and $\mathcal{D}{(1)}$, respectively. For $H_{A}$,
there is one (key, value) pair, denoting that $\mathcal{A}{(1)}$ contains one
subset $A_{1}$, and for all nodes in $A_{1}$, their set ID is 0 in
$\mathcal{P}_{A}{(0)}$, thus they all belong to the same subset in
$\mathcal{A}{(1)}$, i.e., $\mathcal{A}{(1)}=\\{A_{1}\\}$. By $H_{A}$ in Figure
LABEL:graph:hash(a), we know that all nodes in $A_{1}$ now have the new set ID
1, the representative node of $A_{1}$ is $v_{4}$, and $|A_{1}|=4$.

For the second processed node $v_{2}$, $A_{2}=\\{v_{2},v_{3},v_{5},v_{12}\\}$,
$D_{2}=\\{v_{2},v_{10},v_{13},v_{14}\\}$. As all nodes in $A_{2}$ have the
same set ID 0 in $\mathcal{P}_{A}{(1)}$, $\mathcal{A}{(2)}$ contains a unique
subset $A_{2}$, i.e., $\mathcal{A}{(2)}=\\{A_{2}\\}$. As shown by Figure
LABEL:graph:hash(b), the key is 0, and the triple $(2,v_{3},4)$ denotes that
the new set ID for all nodes in $A_{2}$ is 2, the representative node of
$A_{2}$ is $v_{3}$, and $|A_{2}|=4$. Similarly, all nodes in $D_{2}$ have the
same set ID 1 in $\mathcal{P}_{D}{(1)}$, $\mathcal{D}{(2)}$ contains a unique
subset $D_{2}$, i.e., $\mathcal{D}{(2)}=\\{D_{2}\\}$, which is denoted as
$H_{D}$ in Figure LABEL:graph:hash(b).

For the third processed node $v_{3}$,
$A_{3}=\\{v_{3},v_{4},v_{5},v_{6},v_{11}\\}$,
$D_{3}=\\{v_{3},v_{7},v_{8},v_{9},v_{14}\\}$. For $A_{3}$, $v_{3}$ and $v_{5}$
have the same set ID 2 in $\mathcal{P}_{A}{(2)}$, thus they form the subset in
$\mathcal{A}{(3)}$. Further, $v_{4},v_{6},v_{11}$ have the same set ID 1 in
$\mathcal{P}_{A}{(2)}$, they form the second subset in $\mathcal{A}{(3)}$.
Therefore $\mathcal{A}{(3)}=\\{\\{v_{3},v_{5}\\},\\{v_{4},v_{6},v_{11}\\}\\}$.
Similarly, we know that
$\mathcal{D}{(3)}=\\{\\{v_{3},v_{8},v_{14}\\},\\{v_{7},v_{9}\\}\\}$. Both
$\mathcal{A}{(3)}$ and $\mathcal{D}{(3)}$ are denoted by $H_{A}$ and $H_{D}$
in Figure LABEL:graph:hash(c), respectively. $\Box$

TABLE III: The status of set IDs for all nodes. Node | $v_{1}$ | $v_{2}$ | $v_{3}$
---|---|---|---
|  $id_{A}({v})$ |  $id_{D}({v})$ |  $id_{A}({v})$ |  $id_{D}({v})$ |  $id_{A}({v})$ |  $id_{D}({v})$
$v_{1}$ | 1 | 1 | 1 | 1 | 1 | 1
$v_{2}$ |  | 1 | 2 | 2 | 2 | 2
$v_{3}$ |  |  | 2 |  | 3 | 3
$v_{4}$ | 1 |  | 1 |  | 4 |
$v_{5}$ |  |  | 2 |  | 3 |
$v_{6}$ | 1 |  | 1 |  | 4 |
$v_{7}$ |  | 1 |  | 1 |  | 4
$v_{8}$ |  |  |  |  |  | 3
$v_{9}$ |  | 1 |  | 1 |  | 4
$v_{10}$ |  | 1 |  | 2 |  | 2
$v_{11}$ | 1 |  | 1 |  | 4 |
$v_{12}$ |  |  | 2 |  | 2 |
$v_{13}$ |  | 1 |  | 2 |  | 2
$v_{14}$ |  |  |  |  |  | 3
$v_{15}$ |  | 1 |  | 2 |  | 2

The Algorithm: As shown by Algorithm 3, for each hop-node $v_{i}$, we first
perform forward and backward BFS to get $D_{i}$ (lines 6-15) and $A_{i}$
(lines 16-25). At the same time, we generate their partitions
$\mathcal{D}{(i)}$ and $\mathcal{A}{(i)}$, for which each subset is recorded
in $H_{D}$ and $H_{A}$, respectively. In lines 26-29, we compute $\lambda$
according to Equation 11, which is the number of reachable queries that are
covered by $\mathcal{L}_{i-1}$. In line 30, we get the number of reachable
queries that can be covered by $\mathcal{L}_{i}$ but cannot be covered by
$\mathcal{L}_{i-1}$. After that, we have the total number of covered reachable
queries in line 31, and the reachability ratio in line 32. At last, we
generate $\mathcal{L}_{i}$ in lines 33-36, and return the reachability ratio
of $S_{k}$ in line 37.

1

2

3 1 $N_{0}\leftarrow 0$; $n_{A}\leftarrow 0$; $n_{D}\leftarrow 0$;

4 2 rank nodes in $G$ in a certain order

5 3 put the first $k$ nodes into $S_{k}$ as hop-nodes

6 4 foreach $(v_{i}\in S_{k})$ do

7 5 $A_{i}\leftarrow\emptyset$; $D_{i}\leftarrow\emptyset$;
$H_{A}\leftarrow\emptyset$; $H_{D}\leftarrow\emptyset$

8 6 perform forward BFS from $v_{i}$, and for each visited $v$

9 7 if $(L^{{i-1}}_{out}({v_{i}})\bigcap L^{{i-1}}_{in}({v})=\emptyset)$ then
/*$\mathcal{L}_{i-1}$*/

10 8 if $(id_{A}({v})\not\in H_{D})$ then

11 9 $n_{A}\leftarrow n_{A}+1$

1210 $H_{D}[id_{A}({v})]\leftarrow(n_{A},v,1)$

1311 else

1412 $H_{D}[id_{A}({v})].s\leftarrow H_{D}[id_{A}({v})].s+1$

1513 $D_{i}\leftarrow D_{i}\cup\\{v\\}$

1614 $id_{A}({v})\leftarrow n_{A}$

1715 else stop expansion from $v$

1816 perform backward BFS from $v_{i}$, and for each visited $v$

1917 if $(L^{{i-1}}_{out}({v})\bigcap L^{{i-1}}_{in}({v_{i}})=\emptyset)$ then
/*$\mathcal{L}_{i-1}$*/

2018 if $(id_{D}({v})\not\in H_{A})$ then

2119 $n_{D}\leftarrow n_{D}+1$

2220 $H_{A}[id_{D}({v})]\leftarrow(n_{D},v,1)$

2321 else

2422 $H_{A}[id_{D}({v})].s\leftarrow H_{A}[id_{D}({v})].s+1$

2523 $A_{i}\leftarrow A_{i}\cup\\{v\\}$

2624 $id_{D}({v})\leftarrow n_{D}$

2725 else stop expansion from $v$

2826 $\lambda\leftarrow 0$

2927 foreach $((id,a,s_{A})\in H_{A},(id,d,s_{D})\in H_{A})$ do

3028 if $(L^{{i-1}}_{out}({a})\bigcap L^{{i-1}}_{in}({d})\neq\emptyset)$ then
/*$\mathcal{L}_{i-1}$*/

3129 $\lambda\leftarrow\lambda+|s_{A}|\times|s_{D}|$

3230 $n_{i}\leftarrow|A_{i}|\times|D_{i}|-1-\lambda$

3331 $N_{i}\leftarrow N_{i-1}+n_{i}$

3432 $\alpha\leftarrow N_{i}/TC(G)$ /*reachability ratio of $S_{i}$*/

3533 foreach $(a\in A_{i})$ do /*compute $\mathcal{L}_{i}$*/

3634 $L^{{i}}_{out}({a})\leftarrow L^{{i-1}}_{out}({a})\bigcup\\{v_{i}\\}$

3735 foreach $(d\in D_{i})$ do /*compute $\mathcal{L}_{i}$*/

3836 $L^{{i}}_{in}({d})\leftarrow L^{{i-1}}_{in}({d})\bigcup\\{v_{i}\\}$

3937 return $\alpha$ as reachability ratio of $S_{k}$

Algorithm 3 incRR${}^{+}(G=(V,E),k,TC(G))$

Analysis: Same as Algorithm 1 and Algorithm 2, Algorithm 3 completes Step-1 by
performing both forward and backward BFS from each hop-node, during which it
first computes the two sets $A_{i}$ and $D_{i}$ in lines 1-25, and at the same
time computes $H_{A}$ and $H_{D}$. Then, it computes the new partial 2-hop
labels $\mathcal{L}_{i}$ in lines 33-36. The time cost is $O(k^{2}(|V|+|E|)$.
Different with Algorithm 1 and Algorithm 2, the benefits of Algorithm 3 lies
in Step-2. The cost of Step-2 for each hop-node is
$O(i|\mathcal{A}{(i)}||\mathcal{D}{(i)}|)$. For $k$ hop-node, the cost is
$O(\sum_{i\in[1,k]}i|\mathcal{A}{(i)}||\mathcal{D}{(i)}|)$. Therefore, the
time complexity of Algorithm 3 is
$O(k^{2}(|V|+|E|)+\sum_{i\in[1,k]}i|\mathcal{A}{(i)}||\mathcal{D}{(i)}|)$.

Similar to Algorithm 1, we need to maintain the 2-hop labels w.r.t. at most
$k$ hop-nodes during the processing. As $A_{i}$, $D_{i}$, $H_{A}$ and $H_{D}$
are bounded by $V$, and $A_{i}(D_{i})$ can be used to store nodes of
$A_{i+1}(D_{i+1})$, the space complexity of Algorithm 2 is $O(k|V|)$.

By comparing Algorithm 1, Algorithm 2 and Algorithm 3, we know that the
difference of the three algorithms lies in how to compute the reachability
ratio, i.e., Step-2. In Table IV, we show the comparison of their time and
space complexities. For time complexity, we do not show the cost of Step-1,
due to that for Step-1, the cost is same for all three algorithms. We will
show in Experiment that the incRR+ algorithm works much more efficiently than
the blRR and incRR algorithms.

TABLE IV: Comparison of time and space complexities, where $A=\cup_{i\in[1,k]}A_{i}$, $D=\cup_{i\in[1,k]}D_{i}$, and $\mathcal{A}{(i)}(\mathcal{D}{(i)})$ is the partition of $A_{i}(D_{i})$. Algorithm | Time Complexity of Step-2 | Space Complexity
---|---|---
blRR | $O(k|A||D|)$ | $O(k|V|)$
incRR | $O(\sum_{i\in[1,k]}i|A_{i}||D_{i}|)$ | $O(k|V|)$
incRR+ | $O(\sum_{i\in[1,k]}i|\mathcal{A}{(i)}||\mathcal{D}{(i)}|)$ | $O(k|V|)$

###### Example 6

Consider $G$ in Figure 3. Assume that we want to compute the reachability
ratio of $S_{3}=\\{v_{1},v_{2},v_{3}\\}$.

For $v_{1}$, as it is the first processed node, there is no covered
reachability relationship, thus we do not need to test any reachability
relationship in lines 28. As $|A_{1}|=4$, $|D_{1}|=7$, thus
$n_{1}=|A_{1}|\times|D_{1}|-1=27$ in line 30 of Algorithm 3.

For $v_{2}$, as both $|\mathcal{A}{(2)}|=|\mathcal{D}{(2)}|=1$, we only need
to test one reachable query, i.e., whether ${v_{3}}?\rightsquigarrow{v_{10}}$
can be answered by $\mathcal{L}_{1}$. As $L^{{1}}_{out}({v_{3}})\cap
L^{{1}}_{in}({v_{10}})=\emptyset$, we know that
$n_{2}=|A_{2}|\times|D_{2}|-1=15$ in line 30 of Algorithm 3.

For $v_{3}$, as shown by Figure LABEL:graph:hash(c), we know that
$\mathcal{A}{(3)}=\\{\\{v_{3},v_{5}\\},\\{v_{4},v_{6},v_{11}\\}\\}$ and
$\mathcal{D}{(3)}=\\{\\{v_{3},v_{8},v_{14}\\},\\{v_{7},v_{9}\\}\\}$. In line
28, we only need to test $|\mathcal{A}{(3)}|\times|\mathcal{D}{(3)}|=2\times
2=4$ reachable queries. As $v_{4}$ can reach $v_{7}$ can be answered by
$\mathcal{L}_{2}$, we know that all nodes in $\\{v_{4},v_{6},v_{11}\\}$ can
reach every node in $\\{v_{7},v_{9}\\}$ can be answered by $\mathcal{L}_{2}$,
thus $\lambda=6$ for $v_{3}$. In line 30, we know that
$n_{3}=|A_{3}|\times|D_{3}|-1-\lambda=5\times 5-1-6=18$.

Then, we know that $N_{3}=n_{1}+n_{2}+n_{3}=27+15+18=60$, and the reachability
ratio is $\alpha=N_{3}/TC(G)=60/70=85.7$%. And during the processing, the
total number of tested reachability queries by Algorithm 3 is 5.

As a comparison, Algorithm 2 needs to test 16 reachability queries for
$v_{2}$, due to that $|A_{2}|=|D_{2}|=4$. For $v_{3}$, Algorithm 2 needs to
test 25 reachability queries, due to that $|A_{3}|=|D_{3}|=5$. The total
number of tested reachability queries for Algorithm 2 is 41.

Consider Algorithm 1, $|A_{1}\cup A_{2}\cup A_{3}|=8$, $|D_{1}\cup D_{2}\cup
D_{3}|=10$, thus the total number of tested reachability queries for Algorithm
1 is 80 to get the reachability ratio. $\Box$

TABLE V: Statistics of datasets, where $d=2|E|/|V|$ is the average degree of $G$, $TC(\cdot)$ is the average number of reachable nodes for nodes of $G$, and $n_{t}$ is the number of topological levels (the length of the longest path) of $G$. Dataset | $|V|$ | $|E|$ | $d$ | $TC(\cdot)$ | $n_{t}$
---|---|---|---|---|---
amaze | 3,710 | 3,600 | 1.94 | 639 | 16
human | 38,811 | 39,576 | 2.04 | 9 | 18
anthra | 12,499 | 13,104 | 2.10 | 12 | 16
agrocyc | 12,684 | 13,408 | 2.11 | 13 | 16
ecoo | 12,620 | 13,350 | 2.12 | 14 | 22
vchocyc | 9,491 | 10,143 | 2.14 | 14 | 21
kegg | 3,617 | 3,908 | 2.16 | 729 | 26
arxiv | 6,000 | 66,707 | 22.24 | 928 | 167
email | 231,000 | 223,004 | 1.93 | 11,698 | 7
LJ | 971,232 | 1,024,140 | 2.11 | 206,907 | 24
web | 371,764 | 517,805 | 2.79 | 55,055 | 34
10cit-Patent | 1,097,775 | 1,651,894 | 3.01 | 3 | 7
10citeseerx | 770,539 | 1,501,126 | 3.90 | 70 | 36
05cit-Patent | 1,671,488 | 3,303,789 | 3.95 | 8 | 12
05citeseerx | 1,457,057 | 3,002,252 | 4.12 | 116 | 36
citeseerx | 6,540,401 | 15,011,260 | 4.59 | 15,510 | 59
dbpedia | 3,365,623 | 7,989,191 | 4.75 | 83,659 | 146
patent | 3,774,768 | 16,518,947 | 8.75 | 1,544 | 32
twitter | 18,121,168 | 18,359,487 | 2.03 | 1,346,820 | 22
web-uk | 22,753,644 | 38,184,039 | 3.36 | 3,417,930 | 2793

##  6 Experiment

In this section, we show experimental results on reachability ratio
computation. The compared algorithms include blRR, incRR, and incRR+.
Moreover, we show the impacts of partial 2-hop labels on reachability queries
processing based on the state-of-the-art algorithm FL [12] in terms of index
size, index construction time, and query time. We implemented all algorithms
using C++ and compiled by G++ 6.2.0. All experiments were run on a PC with
Intel(R) Core(TM) i5-3230M CPU @ 3.0 GHz CPU, 16 GB memory, and Ubuntu 18.04.1
Linux OS. For algorithms that run $\geq 24$ hours or exceed the memory limit
(16GB), we will show their results as “–” in the tables.

Datasets: Table V shows the statistics of 20 real datasets, where the first
eight are small datasets ($|V|\leq 100,000$) downloaded from the same web
page333https://code.google.com/archive/p/grail/downloads. The following 12
datasets are large ones ($|V|>100,000$). These datasets are usually used in
the recent works w.r.t. reachability queries processing [16, 20, 3, 19, 21,
14, 12, 9, 7, 22]. Among these datasets, amaze and kegg are metabolic
networks, human, anthra, agrocyc, ecoo, vchocyc are graphs describing the
genome and biochemical machinery of E. coli K-12 MG1655.
email444http://snap.stanford.edu/data/index.html is an email network. LJ is an
online social network soc-LiveJournal1${}^{\text{\ref{dataset:stanford}}}$.
web is a web graph web-Google555https://code.google.com/p/ferrari-
index/downloads/list. arxiv, 10cit-Patent666http://pan.baidu.com/s/1bpHkFJx ,
10citeseerx${}^{\ref{dataset:baidu}}$, 05cit-Patent${}^{\ref{dataset:baidu}}$,
05citeseerx${}^{\ref{dataset:baidu}}$,
citeseerx${}^{\text{\ref{dataset:google-p}}}$ and
patent${}^{\text{\ref{dataset:google-p}}}$ (cit-Patents) are all citation
networks. dbpedia 777http://pan.baidu.com/s/1c00Jq5E is a knowledge graph
Dbpedia. twitter${}^{\text{\ref{dataset:ferrari}}}$ is a DAG transformed from
a large-scale social network obtained from a crawl of twitter.com [30]. web-
uk${}^{\text{\ref{dataset:ferrari}}}$ is a DAG of a web graph dataset. For
these datasets, email, LJ, web, and the first seven small graphs are directed
graphs initially. We transform each of them into a DAG by coalescing each
strongly connected component into a node. Note that this can be done in linear
time [28]. All other datasets are DAGs initially. The statistics in Table V
are that of DAGs.

###  6.1 Reachability Ratio Computation

Reachability Ratio and Index Size: We show the reachability ratio (RR) and the
index size ratio (ISR) of the 20 real datasets in Figure 5, where ISR denotes
the ratio of the size of partial 2-hop labels w.r.t. $k$ hop-nodes over the
size of the 2-hop labels w.r.t. all nodes. From Figure 5 we have the following
observation.

First, we can classify all datasets into three categories according to the
value of their reachability ratio. The first kind of datasets (D1) include
amaze, kegg, email, LJ, web, citeseerx, dbpedia, twitter, and web-uk, for
which the RR is more than 99% even when $k=1$, and both the RR and ISR almost
do not change with the increase of $k$. The second kind of datasets (D2)
includes human, anthra, agrocyc, ecoo, vchocyc, and arxiv, for which both RR
and ISR will become larger with the increase of $k$. The third kind of
datasets (D3) includes 10cit-Patent, 10citeseerx, 05cit-Patent, 05citeseerx,
and patent, for which both RR and ISR are very small or even approach zero;
and with the increase of $k$, both RR and ISR almost do not change. The value
of $k$, therefore, only affects the second kind of datasets, and the
reachability ratio is more than 80% when $k\geq 16$ for all datasets of the
second kind, which indicates that we may benefit from using partial 2-hop
labels on datasets of both the first and second kinds.

Second, the storage space used to maintain partial 2-hop labels is small
compared with the reachability ratio value. For example, for the first kind of
datasets, we can use about $1/4$ storage space (ISR $\approx 25$%) to maintain
more than 99% (RR $>99$%) reachability information.

(a) amaze

(b) human

(c) anthra

(d) agrocyc

(e) ecoo

(f) vchocyc

(g) kegg

(h) arxiv

(i) email

(j) LJ

(k) web

(l) 10cit-Patent

(m) 10citeseerx

(n) 05cit-Patent

(o) 05citeseerx

(p) citeseerx

(q) dbpedia

(r) patent

(s) twitter

(t) web-uk

Figure 5: Comparison of Reachability Ratio (RR) and Index Size Ratio (ISR),
where ISR is ratio of the index size of partial 2-hop labels w.r.t. $k$ hop
nodes over that of the total 2-hop label size w.r.t. all nodes.

Running Time: We show in Figure 6 the comparison of running time for
reachability ratio computation, from which we have the following observations.

First, incRR+ is much faster than both blRR and incRR on all datasets, and
incRR works faster than blRR on most datasets. For instance, incRR+ is faster
than blRR by more than two or three orders of magnitude on most datasets, and
incRR is ten times faster than blRR on amaze, email, LJ, web, citeseerx, and
dbpedia. The reason can be explained as follows. On one hand, Figure 5 shows
the reachability ratio of different graphs w.r.t. different $k$. From Figure 5
we know that for amaze, human, anthra, agrocyc, ecoo, vchocyc, kegg, arxiv,
email, LJ, web, citeseerx, dbpedia, twitter and web-uk, the reachability ratio
is more than 80% when $k=32$ for all datasets. On the other hand, according to
the last to the second column of Table V, we know that the average number of
reachable nodes for nodes of each graph is usually big. Therefore, the number
of tested reachability queries by blRR is significantly large. Even though
incRR can reduce the number of tested reachability queries, it still needs to
test much more reachability queries than incRR+ for some datasets. For
example, consider the number of tested reachability queries on kegg dataset
when $k=32$. The tested number of reachability queries of blRR (incRR) is 100
(10) times more than that of incRR+. Moreover, blRR and incRR cannot get the
value of reachability ratio on both twitter and web-uk for $k\geq 2$ in
limited time (24 hours), due to testing too many reachability queries.

(a) amaze

(b) human

(c) anthra

(d) agrocyc

(e) ecoo

(f) vchocyc

(g) kegg

(h) arxiv

(i) email

(j) LJ

(k) web

(l) 10cit-Patent

(m) 10citeseerx

(n) 05cit-Patent

(o) 05citeseerx

(p) citeseerx

(q) dbpedia

(r) patent

(s) twitter

(t) web-uk

Figure 6: Running Time of different algorithms on reachability ratio
computation (ms).

Second, both blRR and incRR work efficiently on datasets where the
reachability ratio is small. For instance, from Figure 6 we know that incRR+
is faster than blRR and incRR by less than ten times on 10cit-Patent,
10citeseerx, 05cit-Patent, 05citeseerx, and patent. The reason lies in that
for these datasets, the reachability ratio is very small according to Figure
5, which means that for all algorithms, the number of tested reachability
queries is much less than other datasets, therefore does not need to consume
more time.

It is worth noting that when $k=1$, the three algorithms consume similar time.
The reason is that when $k=1$, for the first hop-node $v_{1}$, after we get
$A_{v_{1}}$ and $D_{v_{1}}$, we immediately know the number of reachability
queries covered by $\mathcal{L}_{1}$ is $|A_{v_{1}}|\times|D_{v_{1}}|-1$, and
therefore do not need to actually test any reachability queries.

By the above experimental results, we know that our incRR+ algorithm can be
used to efficiently compute the reachability ratio for a given dataset, which
brings us a chance to determine whether we should use partial 2-hop labels to
facilitate reachability queries processing.

###  6.2 Reachability Queries Processing

In this section, we combine partial 2-hop labels with the state-of-the-art
algorithm, namely FELINE [12] (abbreviated as FL), to show the impact of
partial 2-hop labels on reachability queries processing, in terms of index
size, index construction time and query time. The experimental results are
shown, respectively, in Table VI, Table VII and Table VIII, where FL-$k$
denotes the FL algorithm combined with partial 2-hop labels that are generated
based on $k$ hop-nodes. Hence, FL-0 is the FL algorithm without partial 2-hop
labels. Note that for reachability queries processing, we do not set
$k=1,2,4,8$, due to that when $k=16$, we only need to use one integer as a
bit-vector for each node $v$ to represent both $L^{{16}}_{out}({v})$ and
$L^{{16}}_{in}({v})$.

Index Size: Table VI shows the impacts of $k$ on index size, from which we
know that with the increase of $k$, the index size will increase accordingly.
For example, for web-uk dataset, the index size of FL-128 is more than two
times bigger than that of FL-0 on all datasets. The reason is obvious. The
larger the value of $k$, the more the space we need to maintain the partial
2-hop labels.

Index Construction Time: Figure VII shows the impacts of $k$ on index
construction time, from which we know that with the increase of $k$, we need
more time for index construction. Note that partial 2-hop labels can be
constructed efficiently, and the increased time for index construction could
be omitted, due to that index construction is a one-time activity performed
off-line for reachability queries processing.

Query Time: We report the query time about equal workload, which contains
1,000,000 reachability queries for each dataset. The equal workload consists
of 50% reachable queries and 50% unreachable queries. The reason that we use
equal workload is: using completely random queries is heavily skewed towards
unreachable queries [15, 16], which is highly unlikely for the real workload
as the node pair in a query tends to have a certain connection [5]. Here,
unreachable queries are generated by sampling node pairs with the same
probability until we reach the required number of unreachable queries by
testing each query using the FL algorithm. For reachable queries, we cannot
choose them randomly by sampling the TC, because TC computation suffers from
high time and space complexity, we cannot get it within limited time and
memory size for large graphs. To this problem, we randomly pick a node $u$ in
each iteration, then randomly select an out-neighbor $v$ recursively until $v$
has no out-neighbor. Then, we have a path $p$ from $u$. At last, we randomly
select a node $v\neq u$ from $p$ to get a reachable query
${u}\rightsquigarrow{v}$. This operation will be continued until we reach the
required number of reachable queries.

We show the comparison of query time for FL-0 to FL-128 in Table VIII, from
which we have the following observations.

First, FL-16 and FL-32 usually need the least time on the first kind of
datasets D1, including amaze, kegg, email, LJ, web, citeseerx, dbpedia,
twitter and web-uk, where the reachability ratio is more than 99% even when
$k=1$. For these datasets, although the index size becomes larger and the
index construction time becomes longer than that of FL-0, we use the least
cost to achieve significant improvements. For example, compared with FL-0,
FL-16 and FL-32 use about 1.5 times index size and 1.2 times index
construction time to achieve more than 1,000 times improvements on query time.

Second, FL-128 suffers from the largest index size (about 3 times bigger than
FL-0) and longest index construction time (about 1.3 times longer than FL-0),
but achieves the best query performance on the second kind of datasets D2, due
to that on these datasets, the reachability ratio will become larger with the
increase of $k$. These datasets include human, anthra, agrocyc, ecoo, vchocyc
and arxiv.

Third, for the third kind of datasets D3, including 10cit-Patent, 10citeseerx,
05cit-Patent, 05citeseerx, and patent, the reachability ratio is very small or
even approach zero, and almost does not change with the increase of $k$. For
these datasets, FL-0 works best and the use of partial 2-hop labels cannot
bring us any positive results. For example, compared with FL-0 on 05cit-
Patent, the index size of FL-128 is 2.6 times bigger than FL-0, and the index
construction time and query time of FL-128 are 1.04 and 1.5 times longer than
that of FL-0.

At last, we choose one dataset from each kind and show the trend of its query
time w.r.t. $k$ in Figure 7, from which we can give out the suggestions on how
to use partial 2-hop labels: (1) For the first kind of datasets D1, we highly
recommend using partial 2-hop labels with $k=16$ to process reachability
queries, due to that we can speed up reachability queries answering
significantly by affording only a little more index size and index
construction time. (2) For the second kind of datasets D2, we also recommend
using partial 2-hop labels, due to that we can speed up reachability queries
answering by partial 2-hop labels. But for the value of $k$, it depends on
your concerns on how much you could and would like to afford for the increased
index size and index construction time. In general, the larger the value of
$k$, the less the query time, but the more the index construction time and the
bigger the index size. (3) For the third kind of datasets D3, we do not
recommend using partial 2-hop labels to process reachability queries.

TABLE VI: Comparison of the index size (MB). Dataset |  FL-0 |  FL-16 |  FL-32 |  FL-64 |  FL-128
---|---|---|---|---|---
amaze | 0.07 | 0.08 | 0.10 | 0.13 | 0.18
human | 0.74 | 0.89 | 1.04 | 1.33 | 1.92
anthra | 0.24 | 0.29 | 0.33 | 0.43 | 0.62
agrocyc | 0.24 | 0.29 | 0.34 | 0.43 | 0.63
ecoo | 0.24 | 0.29 | 0.34 | 0.43 | 0.62
vchocyc | 0.18 | 0.22 | 0.25 | 0.32 | 0.47
kegg | 0.07 | 0.08 | 0.10 | 0.12 | 0.18
arxiv | 0.11 | 0.14 | 0.16 | 0.20 | 0.30
email | 4.4 | 5.3 | 6.2 | 7.9 | 11.5
LJ | 18.5 | 22.2 | 25.9 | 33.3 | 48.2
web | 7.1 | 8.5 | 9.9 | 12.8 | 18.4
10cit-Patent | 20.9 | 25.1 | 29.3 | 37.7 | 54.4
10citeseerx | 14.7 | 17.6 | 20.6 | 26.5 | 38.2
05cit-Patent | 31.9 | 38.3 | 44.6 | 57.4 | 82.9
05citeseerx | 27.8 | 33.3 | 38.9 | 50.0 | 72.3
citeseerx | 124.7 | 149.7 | 174.6 | 224.5 | 324.3
dbpedia | 64.2 | 77.0 | 89.9 | 115.5 | 166.9
patent | 72.0 | 86.4 | 100.8 | 129.6 | 187.2
twitter | 345.6 | 414.8 | 483.9 | 622.1 | 898.6
web-uk | 434.0 | 520.8 | 607.6 | 781.2 | 1,128.4
TABLE VII: Comparison of the index construction time (ms). Dataset |  FL-0 |  FL-16 |  FL-32 |  FL-64 |  FL-128
---|---|---|---|---|---
amaze | 1.03 | 1.10 | 1.35 | 1.41 | 1.49
human | 9.01 | 10.01 | 11.50 | 11.65 | 11.67
anthra | 2.89 | 2.99 | 3.67 | 3.72 | 3.85
agrocyc | 2.96 | 3.27 | 3.63 | 4.19 | 3.96
ecoo | 3.08 | 3.27 | 3.91 | 6.05 | 4.00
vchocyc | 2.22 | 2.37 | 3.16 | 3.47 | 3.65
kegg | 1.11 | 1.20 | 1.62 | 1.65 | 1.39
arxiv | 4.71 | 4.61 | 6.34 | 7.25 | 8.44
email | 81.3 | 77.2 | 91.0 | 86.5 | 87.1
LJ | 325.1 | 327.3 | 383.9 | 376.3 | 387.8
web | 178.5 | 177.9 | 203.8 | 202.7 | 207.6
10cit-Patent | 801.3 | 803.3 | 862.0 | 832.0 | 862.1
10citeseerx | 376.3 | 385.3 | 415.5 | 419.1 | 437.6
05cit-Patent | 1,517.8 | 1,495.2 | 1,518.4 | 1,566.9 | 1,577.2
05citeseerx | 775.6 | 784.8 | 840.0 | 828.8 | 899.1
citeseerx | 4,063.9 | 4,053.7 | 4,500.5 | 4,441.1 | 4,562.0
dbpedia | 2,264.3 | 2,371.0 | 2,588.6 | 2,607.1 | 2,598.4
patent | 5,022.8 | 5,152.1 | 5,328.3 | 5,400.1 | 5,372.3
twitter | 6,287.6 | 6,446.3 | 7,236.2 | 7,233.9 | 7,719.2
web-uk | 8,689.7 | 8,774.7 | 9,945.0 | 9,991.6 | 10,366.0
TABLE VIII: Comparison of the query time (ms). Dataset |  FL-0 |  FL-16 |  FL-32 |  FL-64 |  FL-128
---|---|---|---|---|---
amaze | 592 | 30 | 28 | 30 | 30
human | 190 | 37 | 36 | 35 | 33
anthra | 133 | 32 | 32 | 31 | 32
agrocyc | 137 | 33 | 31 | 31 | 31
ecoo | 143 | 35 | 36 | 36 | 30
vchocyc | 126 | 33 | 31 | 32 | 28
kegg | 533 | 45 | 39 | 40 | 36
arxiv | 1,105 | 594 | 566 | 554 | 511
email | 8,091 | 21 | 24 | 26 | 40
LJ | 50,811 | 37 | 42 | 55 | 83
web | 39,902 | 58 | 59 | 71 | 96
10cit-Patent | 248 | 277 | 285 | 304 | 412
10citeseerx | 347 | 377 | 409 | 427 | 509
05cit-Patent | 405 | 475 | 482 | 528 | 605
05citeseerx | 452 | 485 | 489 | 533 | 633
citeseerx | 162,696 | 575 | 544 | 554 | 587
dbpedia | 25,344 | 99 | 104 | 128 | 176
patent | 13,180 | 13,493 | 13,566 | 13,752 | 13,898
twitter | — | 88 | 91 | 117 | 176
web-uk | — | 3,197 | 3,230 | 3,478 | 3,701
Figure 7: Impacts of $k$ on query time (ms) over different datasets.

##  7 Conclusion

Partial 2-hop label is a useful pruning technique for reachability queries
processing. In practice, it may be powerful to answer most queries by a larger
reachability ratio for some graphs, but for other graphs, its pruning ability
may not be as powerful as expected, or even makes query performance
degenerated on some graphs, due to small reachability ratio. In this paper, we
aim at figuring out an important problem: whether we should use partial 2-hop
labels for reachability queries processing for a given graph. To solve this
problem, we formally defined the reachability ratio problem and proposed a set
of algorithms for efficient reachability ratio computation. Our first
experimental results show that compared with the baseline algorithm, our
optimized algorithm can efficiently compute the reachability ratio for a given
graph. Our second experimental results show that by combining partial 2-hop
labels with an existing reachability algorithm, the query performance has
different trends with the increase of the number of hop-nodes $k$. And based
on the second experimental results, we finally give out our findings on
whether we should use partial 2-hop labels for reachability queries
processing. Specifically, (1) for datasets with large reachability ratio,
partial 2-hop labels should be used with $k=16$; (2) for datasets with small
reachability ratio, we do not recommend using partial 2-hop labels; and (3)
for the remaining datasets, partial 2-hop labels can be used, and users can
determine $k$’s value themselves according to their requirements on index
size, index construction time and query time.

##  8 Acknowledgments

This work was partly supported by the grants from the Natural Science
Foundation of Shanghai (No. 20ZR1402700), and from the Natural Science
Foundation of China (No.: 61472339, 61572421, 61272124). The authors would
like to thank the anonymous referees for their insightful and valuable
comments.

## References

  * [1] R. Agrawal, A. Borgida, and H. V. Jagadish, “Efficient management of transitive relationships in large data and knowledge bases,” in SIGMOD, pp. 253–262, 1989.
  * [2] Y. Chen and Y. Chen, “An efficient algorithm for answering graph reachability queries,” in ICDE, pp. 893–902, 2008.
  * [3] J. Cheng, S. Huang, H. Wu, and A. W. Fu, “Tf-label: a topological-folding labeling scheme for reachability querying in a large graph,” in SIGMOD, pp. 193–204, 2013.
  * [4] E. Cohen, E. Halperin, H. Kaplan, and U. Zwick, “Reachability and distance queries via 2-hop labels,” in ACM-SIAM, pp. 937–946, 2002.
  * [5] R. Jin, N. Ruan, S. Dey, and J. X. Yu, “SCARAB: scaling reachability computation on large graphs,” in SIGMOD, pp. 169–180, 2012.
  * [6] R. Jin, N. Ruan, Y. Xiang, and H. Wang, “Path-tree: An efficient reachability indexing scheme for large directed graphs,” ACM Trans. Database Syst., vol. 36, no. 1, p. 7, 2011.
  * [7] R. Jin and G. Wang, “Simple, fast, and scalable reachability oracle,” PVLDB, vol. 6, no. 14, pp. 1978–1989, 2013.
  * [8] R. Jin, Y. Xiang, N. Ruan, and D. Fuhry, “3-hop: a high-compression indexing scheme for reachability query,” in SIGMOD, pp. 813–826, 2009.
  * [9] S. Seufert, A. Anand, S. J. Bedathur, and G. Weikum, “FERRARI: flexible and efficient reachability range assignment for graph indexing,” in ICDE, pp. 1009–1020, 2013.
  * [10] S. Trißl and U. Leser, “Fast and practical indexing and querying of very large graphs,” in SIGMOD, pp. 845–856, 2007.
  * [11] S. J. van Schaik and O. de Moor, “A memory efficient reachability data structure through bit vector compression,” in SIGMOD, pp. 913–924, 2011\.
  * [12] R. R. Veloso, L. Cerf, W. M. Junior, and M. J. Zaki, “Reachability queries in very large graphs: A fast refined online search approach,” in EDBT, pp. 511–522, 2014.
  * [13] H. Wang, H. He, J. Yang, P. S. Yu, and J. X. Yu, “Dual labeling: Answering graph reachability queries in constant time,” in ICDE, p. 75, 2006.
  * [14] H. Wei, J. X. Yu, C. Lu, and R. Jin, “Reachability querying: An independent permutation labeling approach,” PVLDB, vol. 7, no. 12, pp. 1191–1202, 2014.
  * [15] H. Yildirim, V. Chaoji, and M. J. Zaki, “GRAIL: scalable reachability index for large graphs,” PVLDB, vol. 3, no. 1, pp. 276–284, 2010.
  * [16] H. Yildirim, V. Chaoji, and M. J. Zaki, “GRAIL: a scalable index for reachability queries in very large graphs,” VLDB J., vol. 21, no. 4, pp. 509–534, 2012.
  * [17] J. X. Yu and J. Cheng, “Graph reachability queries: A survey,” in Managing and Mining Graph Data, pp. 181–215, 2010.
  * [18] Z. Zhang, J. X. Yu, L. Qin, Q. Zhu, and X. Zhou, “I/O cost minimization: reachability queries processing over massive graphs,” in EDBT, pp. 468–479, 2012.
  * [19] A. D. Zhu, W. Lin, S. Wang, and X. Xiao, “Reachability queries on large dynamic graphs: a total order approach,” in SIGMOD, pp. 1323–1334, 2014\.
  * [20] Y. Yano, T. Akiba, Y. Iwata, and Y. Yoshida, “Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths,” in CIKM, pp. 1601–1606, 2013.
  * [21] J. Su, Q. Zhu, H. Wei, and J. X. Yu, “Reachability querying: Can it be even faster?,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 3, pp. 683–697, 2017.
  * [22] J. Zhou, S. Zhou, J. X. Yu, H. Wei, Z. Chen, and X. Tang, “DAG reduction: Fast answering reachability queries,” in SIGMOD, pp. 375–390, 2017.
  * [23] J. Zhou, J. X. Yu, N. Li, H. Wei, Z. Chen, and X. Tang, “Accelerating reachability query processing based on DAG reduction,” VLDB J., vol. 27, no. 2, pp. 271–296, 2018.
  * [24] N. Sengupta, A. Bagchi, M. Ramanath, and S. Bedathur, “ARROW: approximating reachability using random walks over web-scale graphs,” in 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019, pp. 470–481, 2019.
  * [25] S. Wadhwa, A. Prasad, S. Ranu, A. Bagchi, and S. Bedathur, “Efficiently answering regular simple path queries on large labeled networks,” in SIGMOD 2019, 2019.
  * [26] M. Du, A. Yang, J. Zhou, X. Tang, Z. Chen, and Y. Zuo, “ _HT_ : A novel labeling scheme for k-hop reachability queries on dags,” IEEE Access, vol. 7, pp. 172110–172122, 2019.
  * [27] X. Tang, Z. Chen, K. Li, and X. Liu, “Efficient computation of the transitive closure size,” Clust. Comput., vol. 22, no. Supplement, pp. 6517–6527, 2019.
  * [28] R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM J. Comput., vol. 1, no. 2, pp. 146–160, 1972.
  * [29] T. Akiba, Y. Iwata, and Y. Yoshida, “Fast exact shortest-path distance queries on large networks by pruned landmark labeling,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013, pp. 349–360, 2013.
  * [30] M. Cha, H. Haddadi, F. Benevenuto, and P. K. Gummadi, “Measuring user influence in twitter: The million follower fallacy,” in ICWSM, 2010.