# Efficient Top-$k$ Ego-Betweenness Search

Qi Zhang†, Rong-Hua Li†, Minjia Pan†, Yongheng Dai‡, Guoren Wang†, Ye Yuan†
†Beijing Institute of Technology, Beijing, China; ‡Diankeyun Technologies Co.
, Ltd.;
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Betweenness centrality, measured by the number of times a vertex occurs on all
shortest paths of a graph, has been recognized as a key indicator for the
importance of a vertex in the network. However, the betweenness of a vertex is
often very hard to compute because it needs to explore all the shortest paths
between the other vertices. Recently, a relaxed concept called ego-betweenness
was introduced which focuses on computing the betweenness of a vertex in its
ego network. In this work, we study a problem of finding the top-$k$ vertices
with the highest ego-betweennesses. We first develop two novel search
algorithms equipped with a basic upper bound and a dynamic upper bound to
efficiently solve this problem. Then, we propose local-update and lazy-update
solutions to maintain the ego-betweennesses for all vertices and the top-$k$
results when the graph is updated, respectively. In addition, we also present
two efficient parallel algorithms to further improve the efficiency. The
results of extensive experiments on five large real-life datasets demonstrate
the efficiency, scalability, and effectiveness of our algorithms.

##  I Introduction

Betweenness centrality is a fundamental metric in network analysis [1, 2]. The
betweenness centrality of a vertex $v$ is the sum of the ratio of the shortest
paths that pass through $v$ between other vertices in a graph. Such a
centrality metric has been successfully used in a variety of network analysis
applications, such as social network analysis [3], biological network analysis
[4], communication network analysis [5] and so on. More specifically, in
social networks, a vertex with a high betweenness centrality is plausibly an
influential user who can decide whether to share information or not [3]. In
protein interaction networks, the high-betweenness proteins represent
important connectors that link some modular organizations [4]. In
communication networks, the nodes with higher betweennesses might have more
control over the network, thus attacking these nodes may cause severe damage
to the network [5].

Although betweenness centrality plays a critical role in network analysis,
computing betweenness scores for all vertices is notoriously expensive because
it requires exploring the shortest paths between all vertices in a graph. The
state-of-the-art algorithm for betweenness computation is the Brandes’
algorithm [6] which takes ${\mathcal{O}}(nm)$ time. Such a time complexity is
acceptable only in small graphs with a few tens of thousands of vertices and
edges, but it is prohibitively expensive on modern networks with millions of
vertices and tens of millions of edges.

To avoid the high computational cost problem, Everett _et al._ [7] introduced
a relaxed concept called ego-betweenness centrality which focuses on computing
a vertex’s betweenness in its ego network, where the ego network of a vertex
$u$ is the subgraph induced by $u$ and $u$’s neighbors. More specifically, the
ego-betweenness of a vertex $u$ is measured by the sum of the ratio of the
shortest paths that pass through $u$ between $u$’s neighbors in the ego
network. Everett _et al._ showed that the ego-betweenness centrality is highly
correlated with the traditional betweenness centrality in networks, thus it
can be considered as a good approximation of the traditional betweenness.
Hence, like betweenness centrality, ego-betweenness can measure the importance
of a node as a “link” between different parts of the graph. For vertices $v$
and $w$, if $u$ is the only vertex that connects $v$ and $w$ in $u$’s ego
network, then $u$ is important to control the information flow between $v$ and
$w$. On the other hand, there are alternative vertices to connect the two
vertices and $u$ can be easily bypassed. A vertex with a high ego-betweenness
indicates that it has higher control over its ego network and is not easily
replaced by other vertices, thus it plays an important role in the graph.
Moreover, real-life applications often require retrieving the top-$k$ vertices
with the highest ego-betweenness scores, rather than the exact ego-betweenness
scores for all vertices. Motivated by this, we in this paper study the problem
of identifying the top-$k$ vertices in a graph with the highest ego-
betweennesses.

To solve the top-$k$ ego-betweenness search problem, a straightforward
algorithm is to calculate the ego-betweennesses for all vertices and then
select the top-$k$ results. However, such a straightforward algorithm is very
costly for large graphs, because the total cost for constructing the ego
network for each vertex is very expensive in large graphs. To efficiently
compute the top-$k$ vertices, the general idea of top-$k$ search frameworks
[8, 9, 10] can be used, which explores the vertices based on a predefined
ordering and then applies some upper-bounding rules to prune the unpromising
vertices. Inspired by these algorithms, we first derive a basic upper bound
and a dynamic upper bound of ego-betweenness. Then, we develop two top-$k$
search algorithms with those bounds to efficiently solve the top-$k$ ego-
betweenness search problem. To handle dynamic graphs, we present local-update
solutions to maintain ego-betweennesses for all vertices, and also develop
lazy-update techniques to maintain the top-$k$ results. Additionally, we
propose two efficient parallel algorithms to improve the efficiency of ego-
betweenness computation. In summary, we make the following contributions.

$\mathsf{Top}$-$k$ $\mathsf{search~{}algorithms}$. We develop a basic
algorithm with a static upper bound and an improved algorithm with a tighter
and dynamically-updating upper bound to find the top-$k$ vertices with the
highest ego-betweennesses. Both the algorithms consume $O(\alpha md_{\max})$
time using $O(md_{\max})$ space in the worst case. Here $\alpha$ is the
arboricity of the graph [11] which is typically very small in real-life graphs
[12]. We show that both algorithms can significantly prune the vertices that
are definitely not contained in the top-$k$ results. Moreover, the improved
algorithm can achieve more effective pruning performance due to the tighter
and dynamically-updating upper bound.

$\mathsf{Ego}$-$\mathsf{betweenness~{}maintenance~{}and~{}parallel~{}algorithms}$.
We develop local-update algorithms to maintain the ego-betweennesses for all
vertices when the graph is updated. We also propose lazy-update techniques to
maintain the top-$k$ results for dynamic graphs. To further improve the
efficiency, we present two efficient parallel algorithms to compute all
vertices’ ego-betweennesses. Compared with the sequential algorithms, our
parallel solutions can achieve a high degree of parallelism, thus improving
the efficiency of ego-betweenness computation significantly.

$\mathsf{Extensive~{}experiments}$. We conduct comprehensive experimental
studies to evaluate the proposed algorithms using five large real-world
datasets. The results show that 1) our improved algorithm with a dynamic upper
bound is roughly 3-23 times faster than the basic algorithm; 2) our
maintenance algorithms can maintain the top-$k$ results in less than 0.3
seconds in a large graph with 3,997,962 vertices and 34,681,189 edges; 3) our
best parallel algorithm can achieve near 16 speedup ratio when using 16
threads; 4) the top-$k$ results of ego-betweenness are highly similar to the
top-$k$ results of traditional betweenness. Thus, our results indicate that
the ego-betweenness metric can be seen as a very good approximation of the
traditional betweenness metric, but it is much cheaper to compute by utilizing
the proposed algorithms.

$\mathsf{Reproducibility}$. For reproducibility, the source code of this paper
is released at github: https://github.com/QiZhang1996/egobetweenness.

Organization. We introduce some important notations and formulate our problem
in Section II. Section III presents the top-$k$ search algorithms. The ego-
betweenness maintenance algorithms are developed in Section IV. We propose two
parallel algorithms to speed up the ego-betweenness computation in Section V.
Section VI reports the experimental results. We survey related studies in
Section VII and conclude this work in Section VIII.

##  II Preliminaries

Let $G=(V,E)$ be an undirected and unweighted graph with $n=|V|$ vertices and
$m=|E|$ edges. We denote the set of neighbors of a vertex $u$ by $N(u)$, i.e.,
$N(u)=\\{v\in V|(u,v)\in E\\}$, and the degree of $u$ by $d(u)=|{N(u)}|$.
Similarly, the neighbors of an edge $(u,v)$, denoted by $N(u,v)$, are the
vertices that are adjacent to both $u$ and $v$, i.e., $N(u,v)=\\{w\in
V|(u,w)\in E,(v,w)\in E\\}$. For a subset $S\subseteq V$, the subgraph of $G$
induced by $S$ is defined as ${G_{S}}=({V_{S}},{E_{S}})$ where ${V_{S}}=S$ and
${E_{S}}=\\{(u,v)|u,v\in S,(u,v)\in E\\}$.

We define a total order $\prec$ on $V$ as follows. For vertices $u$ and $v$ in
$V$, we say $u\prec v$, if and only if 1) $d(u)>d(v)$ or 2) $d(u)=d(v)$ and
$u$ has a larger ID than $v$. Based on such a degree ordering $\prec$, we can
construct a directed graph $G^{+}$ from $G$ by orientating each undirected
edge $(u,v)\in G$ to respect the total order $u\prec v$. We denote the out-
neighborhood of $u$ in $G^{+}$ as $N^{+}(u)=\\{v\in V|(u,v)\in E^{+}\\}$.

We give an essential concept, called _ego network_ , as follows.

###### Definition 1

$\mathsf{(Ego}$ $\mathsf{network)}$ For vertex $p$ in $G=(V,E)$, the _ego
network_ of $p$, denoted by $G_{E(p)}$, is a subgraph of $G$ induced by the
vertex set $N(p)\cup\\{p\\}$.

Given a graph $G=(V,E)$ and a vertex $p\in V$. We use $\bar{S}_{E(p)}$ to
denote the edges between the neighbors of $p$, i.e.,
$\bar{S}_{E(p)}=\left\\{(u,v)|u,v\in N(p),(u,v)\in E\right\\}$. For vertices
$u,v\in N(p)$ and $(u,v)\notin E$, we suppose that $u\prec v$. Let
$\hat{S}_{p}(u,v)$, which does not include $p$, be the set of vertices that
connect $u$ and $v$ in $G_{E(p)}$, i.e., $\hat{S}_{p}(u,v)=\left\\{w|u,v,w\in
N(p),(u,v)\notin E,(u,w)\in E,(v,w)\in E\right\\}$. If there is only one
vertex $p$ that links $u$ and $v$ in $G_{E(p)}$, we add the pair $(u,v)$ into
the set $\ddot{S}_{E(p)}$, i.e., $\ddot{S}_{E(p)}=\\{(u,v)|u,v,w\in
N(p),(u,v)\notin E,(u,w)\notin E||(v,w)\notin E\\}$. Denote by
$\hat{S}_{E(p)}$ the set of all $\hat{S}_{p}(u,v)$s. We use $\bar{C}_{p}$ to
represent the size of $\bar{S}_{E(p)}$, i.e., $\bar{C}_{p}=|\bar{S}_{E(p)}|$.
Similarly, we denote $\hat{C}_{p}=|\hat{S}_{E(p)}|$ and
$\ddot{C}_{p}=|\ddot{S}_{E(p)}|$.

(a) $G$

(b) $G_{E(d)}$

Figure 1: Running example

Given a vertex $p$ in $G$ and its ego network $G_{E(p)}$, for $u,v\in N(p)$,
let $g_{uv}$ be the number of the shortest paths connecting $u$ and $v$ in
$G_{E(p)}$ and $g_{uv}(p)$ be the number of those shortest paths that contain
vertex $p$. Note that in $G_{E(p)}$, $g_{uv}(p)$ is either $0$ or $1$. Denote
by $b_{uv}(p)=g_{uv}(p)/g_{uv}$ the probability that a randomly selected
shortest path connecting $u$ with $v$ contains $p$ in $G_{E(p)}$. Based on the
above notions, the definition of _ego-betweenness_ is following.

###### Definition 2

$\mathsf{(Ego}$-$\mathsf{betweenness)}$ For a vertex $p$ in $G$ , the ego-
betweenness of $p$, denoted by ${C_{B}(p)}$, is defined as
$C_{B}(p)=\sum_{u\prec v}b_{uv}(p),u,v\in{N(p)}$.

###### Example 1

Consider a graph $G$ in Fig. 1(a) and a vertex $d\in G$ with the ego network
$G_{E(d)}$ illustrated in Fig. 1(b). For vertices $c$ and $i$, there are three
shortest paths connecting $c$ and $i$ in $G_{E(d)}$, namely, $c\rightarrow
g\rightarrow i$, $c\rightarrow h\rightarrow i$, and $c\rightarrow d\rightarrow
i$, thus $g_{ci}=3$ and $g_{ci}(d)=1$, further
$b_{ci}(d)=g_{ci}(d)/g_{ci}=1/3$ holds. Analogously, we have $b_{hg}(d)=1/3$,
$b_{ga}(d)=b_{gb}(d)=b_{ha}(d)=b_{hb}(d)=1/2$, $b_{ia}(d)=b_{ib}(d)=1$ and the
probabilities for other vertex pairs in $G_{E(d)}$ are equal to 0, thus
${C_{B}(d)}=14/3$.

Problem definition. Given a graph $G$ and an integer $k$, the top-$k$ ego-
betweenness search problem is to identify the $k$ vertices in $G$ with the
highest ego-betweenness scores.

The following example illustrates the definition of our problem.

###### Example 2

Reconsider the graph $G$ shown in Fig. 1(a). Based on the definition of ego-
betweenness, we can easily derive the ego-betweennesses of all vertices. For
instance, we have $C_{B}(f)=11$, $C_{B}(x)=10$, and $C_{B}(i)=8$. Suppose that
$k=1$, $f$ is the answer because it has the highest ego-betweenness score
among all vertices. When $k=3$, the answers are $f$, $x$ and $i$. This is
because there is no other vertex with the ego-betweenness greater than $8$ in
$G$.

In addition, real-world networks undergo dynamically updates. To this end, we
also investigate the problem of top-$k$ ego-betweenness maintenance when the
graph is updated.

Challenges. To solve the top-$k$ ego-betweenness search problem, a
straightforward algorithm is to compute the ego-betweenness for each vertex,
and then pick the top-$k$ vertices as the answers. Such an approach, however,
is costly for large graphs. This is because the algorithm needs to explore the
ego network $G_{E(p)}$ to compute the ego-betweenness for each vertex $p$. The
total size of all ego networks could be very large, thus the straightforward
algorithm might be very expensive for large graphs. Since we are only
interested in the top-$k$ results, we do not need to compute all vertices’
ego-betweenness scores exactly. The challenges of the problem are: 1) how to
efficiently prune the vertices that are definitely not contained in the
top-$k$ results; 2) how to efficiently compute the ego-betweenness for each
vertex; 3) how to maintain the top-$k$ vertices with the highest ego-
betweennesses in dynamic networks. To tackle these challenges, we will develop
two new online search algorithms with two non-trivial punning techniques to
efficiently search the top-$k$ ego-betweenness vertices. Then, We also design
local update techniques and lazy update techniques to handle frequent updates
and maintain the top-$k$ results.

##  III Top-$k$ ego-betweenness search

In this section, we first present a top-$k$ ego-betweenness search algorithm,
called $\mathsf{BaseBSearch}$, which is equipped with an upper-bounding
strategy to prune the search space. Then, to further improve the efficiency,
we propose the $\mathsf{OptBSearch}$ algorithm with a dynamic upper bound
which is tighter than that of $\mathsf{BaseBSearch}$.

###  III-A The $\mathsf{BaseBSearch}$ algorithm

Before introducing the $\mathsf{BaseBSearch}$ algorithm, we first give some
useful lemmas which lead to an upper bound of ego-betweenness for pruning
search space in $\mathsf{BaseBSearch}$.

###### Lemma 1

For any vertex $p$ in $G$, we have
$\bar{C}_{p}+\hat{C}_{p}+\ddot{C}_{p}=\frac{d(p)*(d(p)-1)}{2}$.

###### Proof:

Clearly, the vertex pairs between vertex $p$’s neighbors are divided into
three categories, namely, $\bar{S}_{E(p)}$, $\hat{S}_{E(p)}$ and
$\ddot{S}_{E(p)}$. Therefore, the sum of $\bar{C}_{p}$, $\hat{C}_{p}$ and
$\ddot{C}_{p}$ is the number of all vertex pairs between $N(p)$, i.e.,
$\bar{C}_{p}+\hat{C}_{p}+\ddot{C}_{p}=\frac{d(p)*(d(p)-1)}{2}$. ∎

###### Lemma 2

For any vertex $p$ in $G$,
$C_{B}(p)=\frac{d(p)*(d(p)-1)}{2}-\bar{C}_{p}-\hat{C}_{p}+\sum_{(u,v)}\frac{1}{|\hat{S}_{p}(u,v)|+1}\leq{\mathsf{\overline{ub}}}(p)=\frac{d(p)*(d(p)-1)}{2}$
holds.

###### Proof:

Based on Definition 2, $C_{B}(p)$ is closely related to the number of shortest
paths between $u$ and $v$ in $G_{E(p)}$. First, for each
$(u,v)\in\ddot{S}_{E(p)}$, there is only one vertex $p$ that can link $u$ and
$v$, so $b_{uv}(p)$ is equal to $1$. Thus, $\ddot{C}_{p}$ is a part of
$C_{B}(p)$ which equals $\frac{d(p)*(d(p)-1)}{2}-\bar{C}_{p}-\hat{C}_{p}$
according to Lemma 1. Second, for every vertex pair $(u,v)\in\hat{S}_{E(p)}$,
$\hat{S}_{p}(u,v)$ is the set of vertices connecting $u$ with $v$ in
$G_{E(p)}$ but does not include $p$, thus the probability $b_{uv}(p)$ is equal
to $\frac{1}{|\hat{S}_{p}(u,v)|+1}$. To sum up,
$C_{B}(p)=\frac{d(p)*(d(p)-1)}{2}-\bar{C}_{p}-\hat{C}_{p}+\sum_{(u,v)}\frac{1}{|\hat{S}_{p}(u,v)|+1}$.
As
$\hat{C}_{p}=|\hat{S}_{E(p)}|=\sum_{(u,v)\in\hat{S}_{p}(u,v)}1\geq\sum_{(u,v)}\frac{1}{|\hat{S}_{p}(u,v)|+1}$,
thus $C_{B}(p)\leq{\mathsf{\overline{ub}}}(p)$ holds. ∎

Input: $G=(V,E)$, an integer $k\geq 1$.

Output: The top-$k$ vertex set $R$.

for  _$u\in V$_ do

${\mathsf{\overline{ub}}}(u)\leftarrow\frac{d(u)*(d(u)-1)}{2}$;
$C_{B}(u)\leftarrow{\mathsf{\overline{ub}}}(u)$;

$R\leftarrow\emptyset$;

Construct the oriented graph $G^{+}=(V,E^{+})$ of $G$;

Initialize an array $B$ with $B(i)=false,0\leq i<n$;

for  _$u\in V$ according to the total order_ do

if $|R|=k$ and $\min_{v\in R}C_{B}(v)\geq{\mathsf{\overline{ub}}}(u)$ then
break;

for $v\in N^{+}(u)$ do $B(v)\leftarrow true$;

for  _$v\in N^{+}(u)$_ do

for  _$w\in N^{+}(v)$_ do

if  _$B(w)=true$_ then

${\mathsf{UptSMap}}(S_{u},v,w)$; ${\mathsf{UptSMap}}(S_{v},u,w)$;

if $\nexists S_{w}(u,v)$ then $S_{w}.{{\mathsf{insert}}}((u,v),0)$;

for $v\in N^{+}(u)$ do $B(v)\leftarrow false$;

for  _$((i,j),val)\in S_{u}$_ do

$C_{B}(u)\leftarrow C_{B}(u)-1$;

if $val\neq 0$ then $C_{B}(u)\leftarrow C_{B}(u)+\frac{1}{val+1}$;

Update $R$ based on $u$ and $C_{B}(u)$;

return $R$;

Procedure ${\mathsf{UptSMap}}(S_{u},v,w)$

for  _$x\in N(u)$_ do

if $(x,v)\in E$ and $\nexists S_{u}(x,v)$ then
$S_{u}.{{\mathsf{insert}}}((x,v),0)$;

if $(x,w)\in E$ and $\nexists S_{u}(x,w)$ then
$S_{u}.{{\mathsf{insert}}}((x,w),0)$;

if  _$(x,v)\in E$ and $(x,w)\notin E$_ then

if $\nexists S_{u}(x,w)$ then $S_{u}.{{\mathsf{insert}}}((x,w),1)$;

else if $S_{u}(x,w).val\neq 0$ then $S_{u}(x,w).val$++;

if  _$(x,v)\notin E$ and $(x,w)\in E$_ then

Update $S_{u}$ and $S_{w}$ as lines 25-26;

Algorithm 1 $\mathsf{BaseBSearch}$ $(G,k)$

Equipped with Lemma 2, we present a basic search approach, called
$\mathsf{BaseBSearch}$, which computes the vertices’ ego-betweennesses in non-
increasing order of their upper bounds. The main idea of
$\mathsf{BaseBSearch}$ is that a vertex with a large upper bound may have a
high chance contained in the top-$k$ results. Based on this idea, the exact
computations for the vertices with small upper bounds will be postponed or
even avoided, thus $\mathsf{BaseBSearch}$ can significantly improve the
efficiency compared with the algorithm calculating all ego-betweennesses.

The pseudo-code of $\mathsf{BaseBSearch}$ is outlined in Algorithm 1. For each
vertex $u$, $S_{u}$ is a map to maintain the number of the shortest paths that
do not go through $u$ for all neighbor pairs. Algorithm 1 works as follows. It
first calculates the upper bound ${\mathsf{\overline{ub}}}(u)$ for each vertex
$u$ based on Lemma 2 and initializes $C_{B}(u)$ as
${\mathsf{\overline{ub}}}(u)$ (lines 1-2). Then, it sorts the vertices in non-
increasing order with respect to their upper bounds, and picks an unexplored
vertex $u$ with the maximum ${\mathsf{\overline{ub}}}(u)$ to calculate
$C_{B}(u)$ until the top-$k$ vertices are found (lines 6-19). During the
processing of vertex $u$, if the result set $R$ has $k$ vertices and the
$\min_{v\in R}C_{B}(v)\geq{\mathsf{\overline{ub}}}(u)$ holds, the algorithm
terminates (line 7). Otherwise, $\mathsf{BaseBSearch}$ computes $C_{B}(u)$ and
identifies whether $u$ should be added into the answer set $R$ (lines 8-18).
For vertex $u$, we explore the number of shortest paths between $u$’s
neighbors by enumerating the triangles including $u$ and maintain them in the
hash map $S_{u}$. In $S_{u}$, we always keep a vertex pair $(i,j)$ with
$val=0$ if $i$ and $j$ are connected in $G_{E(u)}$; on the other hand, $val$
records the number of vertices that link $i$ and $j$ but not contain $u$. When
a $\triangle_{(u,v,w)}$ is found, we update the hash maps for $u$, $v$ and $w$
(lines 12-13). Note that $\mathsf{BaseBSearch}$ processes vertices in the
order of the upper bounds (i.e., the total order), all triangles containing
$u$ can be touched without omission after handling $u$ and $S_{u}$ maintains
the number of the shortest paths correctly. Further, the algorithm calculates
$C_{B}(u)$ according to Lemma 2 and updates $R$ (lines 15-18). Finally,
$\mathsf{BaseBSearch}$ outputs the answer set $R$.

###### Example 3

Consider a graph $G$ as shown in Fig. 1(a) and an integer $k=5$. The running
process of Algorithm 1 on this graph is illustrated in Fig. 2. The algorithm
computes the ego-betweennesses of $c,i,f,d,x,e,h,g,b,a$ in turn based on their
upper bounds (i.e., the total order). After computing $C_{B}(a)$, the largest
upper bound among the remaining vertices: $j,k,u,v,x,y,z$ is
${\mathsf{\overline{ub}}}(j)=3<C_{B}(d)=14/3$ ($d$ is the $5$-th element in
$R$), thus Algorithm 1 terminates. Compared with calculating the ego-
betweennesses of all vertices, $\mathsf{BaseBSearch}$ can save 6 ego-
betweenness computations by utilizing the upper bound
$\mathsf{\overline{ub}}$.

Figure 2: The running process of $\mathsf{BaseBSearch}$ on $G$

###  III-B The $\mathsf{OptBSearch}$ algorithm

$\mathsf{BaseBSearch}$ may not be very efficient for top-$k$ search because
the upper bound $\mathsf{\overline{ub}}$ is not very tight. To further improve
the efficiency, we propose the $\mathsf{OptBSearch}$ algorithm with a dynamic
upper bound $\mathsf{\widetilde{ub}}$ which is tighter than
$\mathsf{\overline{ub}}$.

Recall that we calculate $C_{B}(u)$ with the information of the shortest paths
which is derived by touching the triangles including vertex $u$. In this
processing, some useful information about the number of shortest paths for
$u$’s neighbors can also be obtained. We refer to those information as
identified information which include some vertex pairs and edges. Below, we
will use these identified information to derive a tighter and dynamically-
updated upper bound of ego-betweenness.

Given a vertex $p$, let $*\bar{S}_{E(p)}$ be the collection of identified
edges in $G_{E(p)}$ and $*\hat{S}_{E(p)}$ be the set of the currently
identified vertex pairs whose property is the same as the pairs in
$\hat{S}_{E(p)}$. For a vertex pair $(u,v)$ in $*\hat{S}_{E(p)}$, denote by
$*\hat{S}_{p(u,v)}$ the set of identified vertices that link $u$ and $v$ but
does not contain $p$. Let $*\bar{C}_{p}$ and $*\hat{C}_{p}$ be the size of
$*\bar{S}_{E(p)}$ and $*\hat{S}_{E(p)}$, respectively. We develop a tighter
upper bound of ego-betweenness $\mathsf{\widetilde{ub}}$ in Lemma 3.

###### Lemma 3

For a vertex $p$ in $G$,
$C_{B}(p)\leq{\mathsf{\widetilde{ub}}}=\frac{d(p)*(d(p)-1)}{2}-*\bar{C}_{p}-*\hat{C}_{p}+\sum_{(u,v)}\frac{1}{|*\hat{S}_{p(u,v)}|+1}$
holds.

###### Proof:

By definition, we have $*\bar{C}_{p}\leq\bar{C}_{p}$,
$*\hat{C}_{p}\leq\hat{C}_{p}$ and $|*\hat{S}_{p(u,v)}|\leq|\hat{S}_{p(u,v)}|$.
Further,
$\sum_{(u,v)}\frac{1}{|*\hat{S}_{p(u,v)}|+1}\geq\sum_{(u,v)}\frac{1}{|\hat{S}_{p(u,v)}|+1}$
holds. According to Lemma 2, we can obtain
$C_{B}(p)\leq{\mathsf{\widetilde{ub}}}=\frac{d(p)*(d(p)-1)}{2}-*\bar{C}_{p}-*\hat{C}_{p}+\sum_{(u,v)}\frac{1}{|*\hat{S}_{p(u,v)}|+1}$.
∎

Input: $G=(V,E)$, an integer $k\geq 1$, a gradient ratio $\theta\geq 1$.

Output: The top-$k$ vertex set $R$.

1 $H\leftarrow\emptyset$; $R\leftarrow\emptyset$;

2 Initialize an array $B$ with $B(i)=false,0\leq i<n$;

3 for  _$v\in V$_ do

4 ${\mathsf{\widetilde{ub}}}(v)\leftarrow\frac{d(v)*(d(v)-1)}{2}$;
$C_{B}(v)\leftarrow{\mathsf{\widetilde{ub}}}(v)$;
$H.push(v,{\mathsf{\widetilde{ub}}}(v))$;

5

6while  _$H\neq\emptyset$_ do

7 $(v^{*},{\mathsf{\widehat{tb}}})\leftarrow H.pop()$;

8 Compute ${\mathsf{\widetilde{ub}}}(v^{*})$ according to Lemma 3;

9 if  _$\theta\cdot{\mathsf{\widetilde{ub}}}(v^{*}) <{\mathsf{\widehat{tb}}}$_
then

10 if  _$|R| <k$ or ${\mathsf{\widetilde{ub}}}(v^{*})>\min_{v\in R}C_{B}(v)$_
then

11 $H.push(v^{*},{\mathsf{\widetilde{ub}}}(v^{*}))$;

12 continue;

13

14 if $|R|=k$ and ${\mathsf{\widehat{tb}}}\leq\min_{v\in R}C_{B}(v)$ then
break;

15 $\mathsf{EgoBWCal}$ ($G,v^{*},B$);

16 if $|R|<k$ then $R\leftarrow R\cup\\{v^{*}\\}$;

17 else if  _$C_{B}(v^{*}) >\min_{v\in R}C_{B}(v)$_ then

18 $u\leftarrow\arg\min_{v\in R}C_{B}(v)$;
$R\leftarrow(R-\\{u\\})\cup\\{v^{*}\\}$;

19

20 $B(v^{*})\leftarrow true$;

21

22return $R$;

Algorithm 2 $\mathsf{OptBSearch}$ $(G,k,\theta)$

(a) Pop out $f$

(b) Pop out $d$

(c) Pop out $e$

(d) Pop out $h,g,b,a$

(e) Pop out $e$

(f) Pop out $j$

Figure 3: The running process of $\mathsf{OptBSearch}$ on $G$

Note that the upper bound $\mathsf{\widetilde{ub}}$ in Lemma 3 will be
dynamically updated during the execution of the top-$k$ search algorithm,
because $*\bar{C}_{p}$, $*\hat{C}_{p}$ and $|*\hat{S}_{p(u,v)}|$ will be
updated when calculating vertices’ ego-betweennesses exactly. The
$\mathsf{OptBSearch}$ framework with such a dynamic upper bound
$\mathsf{\widetilde{ub}}$ is depicted in Algorithm 2. It first calculates
${\mathsf{\widetilde{ub}}}(v)$ and $C_{B}(v)$ for each vertex $v$, and pushes
$v$ with the initial bound ${\mathsf{\widetilde{ub}}}(v)$ into a sorted list
$H$ (lines 3-4). Then, the $\mathsf{OptBSearch}$ iteratively finds the top-$k$
results (lines 5-17). It pops the vertex $v^{*}$ with the largest upper bound
value $\mathsf{\widehat{tb}}$ from $H$. As the number of shortest paths
between $v^{*}$’s neighbors may be updated, the algorithm calculates
${\mathsf{\widetilde{ub}}}(v^{*})$ based on Lemma 3. $\mathsf{OptBSearch}$
then compares ${\mathsf{\widetilde{ub}}}(v^{*})$ with the old bound
${\mathsf{\widehat{tb}}}$ by employing a parameter $\theta\geq 1$ to avoid
frequently calculating the upper bounds and updating $H$. When
$\theta\cdot{\mathsf{\widetilde{ub}}}(v^{*})<{\mathsf{\widehat{tb}}}$, that
means ${\mathsf{\widetilde{ub}}}(v^{*})$ is substantially smaller than
${\mathsf{\widehat{tb}}}$. If $|R|<k$ or
${\mathsf{\widetilde{ub}}}(v^{*})>\min_{v\in R}C_{B}(v)$, we push $v^{*}$ to
$H$ again with the tighter bound ${\mathsf{\widetilde{ub}}}(v^{*})$ (line 10).
Otherwise, $v^{*}$ does not belong to the top-$k$ answers and thus can be
pruned. In both cases, the algorithm needs to pop the next vertex from $H$. If
the early termination condition (line 12) is not satisfied, the algorithm
performs $\mathsf{EgoBWCal}$ to compute $C_{B}(v^{*})$ exactly and updates $R$
based on $C_{B}(v^{*})$ (lines 13-17). Note that we use an array $B$ to record
the vertices whose ego-betweennesses have been calculated, which can reduce
redundant computations in the $\mathsf{EgoBWCal}$ procedure.

Input: $G=(V,E)$, vertex $u$, an array $B$.

Output: $C_{B}(u)$.

1 Initialize $DN$ and $EN$ according to $B$;

2 Initialize an array $V_{is}$ with $V_{is}(i)=false,0\leq i<n$;

3 for $i\in N(u)$ do $rd(i)\leftarrow\emptyset$;

4 for  _$((i,j),val)\in S_{u}$_ do

5 if  _$val=0$_ then

6 $rd(i)\leftarrow rd(i)\cup\\{j\\}$; $rd(j)\leftarrow rd(j)\cup\\{i\\}$;

7

8

9

10for  _$i\in DN$_ do

11 for $p\in rd(i)$ do $V_{is}(p)\leftarrow true$;

12 for  _$j\in DN-\\{i\\}$_ do

13 if  _$V_{is}(j)=false$_ then

14 for  _$p\in rd(j)$_ do

15 if  _$V_{is}(p)=true$ and $B(p)=false$_ then

16

17 $S_{u}(i,j).val$++; $S_{p}(i,j).val$++;

18

19

20

21

22

23for  _$i\in EN$_ do

24 for  _$j\in EN-\\{i\\}$_ do

25 if  _$(i,j)\in E$_ then

26 $S_{u}.{{\mathsf{insert}}}((i,j),0)$; $S_{i}.{{\mathsf{insert}}}((u,j),0)$;

27 $S_{j}.{{\mathsf{insert}}}((u,i),0)$;

28 for  _$k\in rd(j)$_ do

29 if  _$\nexists S_{u}(i,k)$_ then

30 $S_{u}.{{\mathsf{insert}}}((i,k),1);S_{j}.{{\mathsf{insert}}}((i,k),1)$;

31 else if  _$S_{u}(i,k).val\neq 0$_ then

32 $S_{u}(i,k).val$++; $S_{j}(i,k).val$++;

33

34

35 Update $S_{u},S_{i}$ by $rd(i)$ as lines 19-23;

36 $rd(i)\leftarrow rd(i)\cup\\{j\\}$; $rd(j)\leftarrow rd(j)\cup\\{i\\}$;

37

38

39

40Calculate $C_{B}(u)$ as lines 15-17 of Algorithm 1;

41 return $C_{B}(u)$;

Algorithm 3 $\mathsf{EgoBWCal}$ $(G,u,B)$

Algorithm 3 outlines the $\mathsf{EgoBWCal}$ procedure. Like
$\mathsf{BaseBSearch}$, a key issue is maintaining the number of the shortest
paths in $S_{u}$ correctly by finding the triangles containing $u$. To avoid
reduction, a simple but efficient approach is to record those enumerated
triangles and update $S_{u}$ by deriving the shortest paths from these
triangles. To this end, for each neighbor $i$ of $u$, Algorithm 3 uses $rd(i)$
to store such vertices that are contained in the touched triangles
$\triangle_{(i,*,u)}$. It first initializes $rd(i)$ for every $i\in N(u)$ with
the current $S_{u}$ as $S_{u}(i,j).val$ equals $0$ indicates a visited
triangle $\triangle_{(i,j,u)}$ (lines 3-6). Then, the procedure handles $u$’s
neighbors to maintain $S_{u}$ according to whether they have been processed
(lines 7-25). Specifically, if $B(i)=true$, we put $i$ into the set $DN$ and
call it a processed vertex; otherwise, $i$ is added into the set $EN$ where
stores the vertices to be processed. For the vertices $i,j\in DN$,
$\mathsf{EgoBWCal}$ finds their common neighbors (denote by $p$) based on
$rd(i)$ and $rd(j)$ and updates the number of the shortest paths between $i$
and $j$ for $S_{u}$ and $S_{p}$ (lines 7-13). On the other hand, given $i,j\in
EN$, the procedure enumerates new triangles and maintains related hash maps
with $rd(i)$ and $rd(j)$ (lines 14-25). Note that with the discovery of new
triangles, $\mathsf{EgoBWCal}$ also updates the related $rd(i)$s to avoid
reduction (line 25). Finally, $\mathsf{EgoBWCal}$ calculates $C_{B}(u)$ with
the same method as used in $\mathsf{BaseBSearch}$.

###### Example 4

Reconsider the graph $G$ in Fig. 1(a). Suppose that $k=5$ and $\theta=1$. The
running process of Algorithm 2 is illustrated in Fig. 3. The vertices colored
red are computed their ego-betweennesses exactly and the vertices in gray
grids need to update their upper bounds and push back into $H$ again. The
algorithm pushes all vertices with the initial upper bounds into $H$ and then
processes them based on $H$. First, it pops $c$ with the largest upper bound
${\mathsf{\widehat{tb}}}=21$ and calculates ${\mathsf{\widetilde{ub}}}(c)$ and
$C_{B}(c)$. Due to $R=\emptyset$, $c$ is added into $R$ and
$\mathsf{OptBSearch}$ does the same operation for $i$. Then, $f$ is popped
with ${\mathsf{\widehat{tb}}}=15$ and Algorithm 2 calculates
${\mathsf{\widetilde{ub}}}(f)$ as shown in Fig. 3(a). Since
${\mathsf{\widetilde{ub}}}(f)=23/2$ is substantially smaller than
${\mathsf{\widehat{tb}}}$ based on $\theta=1$, we push $(f,23/2)$ into $H$
again and pops $d$ as the next processing vertex in Fig. 3(b). The tighter
bound ${\mathsf{\widetilde{ub}}}(d)=19/3$ is less than $15$, thus
$\mathsf{OptBSearch}$ pushes $d$ into $H$ again with
${\mathsf{\widetilde{ub}}}(d)$. In the following three iterations,
$\mathsf{OptBSearch}$ computes $C_{B}(f)$ and $C_{B}(x)$ and adds them into
$R$, and then processes $e$ as shown in Fig. 3(c). $e$ is pushed into $H$ with
${\mathsf{\widetilde{ub}}}(e)=4$ and the algorithm pops $d$ to calculate
$C_{B}(d)$ and adds $d$ into $R$ in Fig. 3(d). Due to
${\mathsf{\widehat{tb}}}=6>C_{B}(d)$, $h$ is popped and we calculate
${\mathsf{\widetilde{ub}}}(h)$ to update $H$. Similarly, we push $g,b,a$ into
$H$ again with
${\mathsf{\widetilde{ub}}}(g),{\mathsf{\widetilde{ub}}}(b),{\mathsf{\widetilde{ub}}}(a)$
as shown in Fig. 3(e). When $e$ is processed, $C_{B}(e)=9/2<C_{B}(d)$ and
$|R|=k=5$ hold, thus $e$ is not an answer of top-$k$ results. When pops $j$ in
Fig. 3(f), the algorithm safely prunes $j$ since
${\mathsf{\widetilde{ub}}}(j)<C_{B}(d)$. Obviously, the remaining vertices can
also be pruned. In $\mathsf{OptBSearch}$, we invoke $\mathsf{EgoBWCal}$ six
times to calculate the ego-betweennesses, while $\mathsf{BaseBSearch}$
performs ten ego-betweenness computations.

###  III-C Analysis of the proposed algorithms

Below, we mainly analyze the correctness of Algorithm 1. The correctness
analysis of Algorithm 2 is similar to that of Algorithm 1, thus we omit it for
brevity.

###### Theorem 1

Given a graph $G=(V,E)$ and an integer $k$, Algorithm 1 correctly computes the
top-$k$ vertices with the highest ego-betweennesses.

###### Proof:

Recall that Algorithm 1 iteratively processes the vertices based on their
upper bounds (Lemma 2). When a vertex $u$ is handled, if the answer set $R$
has $k$ vertices and $\min_{v\in R}C_{B}(v)\geq{\mathsf{\overline{ub}}}(u)$,
then $C_{B}(u)\leq{\mathsf{\overline{ub}}}(u)\leq\min_{v\in R}C_{B}(v)$ holds.
For any vertex $w\in V$ with a smaller degree, we have
$C_{B}(w)\leq{\mathsf{\overline{ub}}}(w)\leq{\mathsf{\overline{ub}}}(u)\leq\min_{v\in
R}C_{B}(v)$. Therefore, the algorithm can safely prune the remaining vertices
and terminate, thereby the set $R$ exactly contains the top-$k$ answers. ∎

Below, we analyze the time and space complexity of Algorithm 1 and Algorithm
2. Let $d_{\max}$ be the maximum degree of the vertices in $G$, and $\alpha$
be the arboricity of $G$ [13, 12].

###### Theorem 2

In the worst case, both Algorithm 1 and Algorithm 2 take $O(\alpha md_{\max})$
time using $O(d_{\max}m)$ space.

###### Proof:

We mainly show the complexity of Algorithm 1, and the complexity analysis of
Algorithm 2 is similar. First, in lines 6-18 of Algorithm 1, the algorithm
needs to enumerate each triangle once which takes $O(\alpha m)$ time. Note
that when a triangle $\triangle_{(u,v,w)}$ is enumerated, the algorithm
requires to maintain $S_{u},S_{v},S_{w}$. The time overhead of the update
operator can be bounded by $O(d(u))\leq O(d_{\max})$. Hence, the time
complexity of Algorithm 1 is $O(\alpha md_{\max})$. Second, we analyze the
space complexity of Algorithm 1. Clearly, the space overhead is dominated by
the size of the map structure $S_{u}$. For $u\in V$, the map structure $S_{u}$
contains $O(d(u)^{2})$ vertex pairs, thus the space complexity is
$O(\sum_{u\in V}d(u)^{2})\leq O(d_{\max}m)$. ∎

Although Algorithm 1 and Algorithm 2 have the same worst-case time complexity,
the practical performance of Algorithm 2 is much faster than that of Algorithm
1 due to the dynamic and tight upper bound, which is also confirmed in our
experiments.

##  IV The update algorithms

Real-world networks are often frequently updated. In this section, we develop
local update algorithms to maintain the ego-betweennesses for all vertices
when the graph is updated. We also propose lazy update techniques to
efficiently maintain the top-$k$ results. We mainly focus on the cases of edge
insertion and deletion, as vertex insertion and deletion can be seen as a
series of edge insertions and deletions.

Our update algorithms are based on the following key observation.

###### Observation 1

After inserting/deleting an edge $(u,v)$ into/from $G$, the ego-betweennesses
of the vertices in $N(u,v)\cup\\{u,v\\}$ need to be updated, and the ego-
betweennesses of the vertices that are not in $N(u,v)\cup\\{u,v\\}$ remain
unchanged.

###### Proof:

Here, we prove the edge insertion case and the proof for edge deletion is
similar. The insertion of $(u,v)$ causes the insertions of vertex $v/u$ and a
series of edges $\\{(v,w)|w\in N(u,v)\\}/\\{(u,w)|w\in N(u,v)\\}$ into $u/v$’s
ego network $G_{E(u)}/G_{E(v)}$, thus the ego-betweennesses of $u$ and $v$
need to be updated. In addition, for a common neighbor $w\in N(u,v)$, there is
a new edge $(u,v)$ in $G_{E(w)}$, thus the ego-betweenness of $w$ should be
re-computed. ∎

###  IV-A Local-update for edge insertion

We present the update rules for the vertices $u$, $v$ and $w\in N(u,v)$ when
inserting an edge $(u,v)$. For brevity, let $L=N(u,v)$ denote the common
neighbors of $u$ and $v$ and $S_{u}(x,y)$ be the number of vertices that link
$x$ and $y$ but does not include $u$. Unless otherwise specified, $S_{u}(x,y)$
represents the value after inserting the edge.

Input: $G=(V,E)$, ego-betweenness array $C_{B}$, an inserted edge $(u,v)$.

Output: the updated $\cal C_{B}$.

1 Insert $(u,v)$ into $G$;

2 ${\mathcal{S}}\leftarrow{\mathsf{LocalUptSMap}}(G,(u,v))$;

3 $L\leftarrow N(u)\cap N(v)$;

4 for  _$(x,y)\in S_{u}$_ do

5 if  _$x=v$ or $y=v$_ then

6 ${C_{B}}(u)\leftarrow{C_{B}}(u)+1/(S_{u}(x,y)+1)$;

7

8 else

9 ${C_{B}}(u)\leftarrow{C_{B}}(u)+1/(S_{u}(x,y)+1)-1/S_{u}(x,y)$;

10

11

12Update ${C_{B}}(v)$ as lines 4-8;

13 for  _$x\in L$_ do

14 for  _$(y,z)\in S_{x}$_ do

15 if  _( $y=u$ and $z=v$) or ($y=v$ and $z=u$)_ then

16 ${C_{B}}(x)\leftarrow{C_{B}}(x)-1/(S_{x}(y,z)+1)$;

17

18 else

19 ${C_{B}}(x)\leftarrow{C_{B}}(x)+1/(S_{x}(y,z)+1)-1/S_{x}(y,z)$;

20

21

22

23return ${C_{B}}$;

Algorithm 4 $\mathsf{LocalInsert}$

###### Lemma 4

Consider an inserted edge $(u,v)$, the updated ego-betweenness of $u$ is:
$C_{B}(u)=C_{B}(u)+\sum_{x,y\in L,(x,y)\notin
E}(1/(S_{u}(x,y)+1)-1/S_{u}(x,y))+\sum_{x\in N(u),x\notin L}1/(S_{u}(v,x)+1)$.
The case of updating $C_{B}(v)$ is similar.

###### Proof:

For vertex $u$, after inserting an edge $(u,v)$ into $G$, $v$ is a new
neighbor and is added into $G_{E}(u)$. For $x,y\in L$ and $(x,y)\notin E$,
$C_{B}(u)$ has included the contribution of vertex pair $(x,y)$, thus we
should update this part. $v$ is a new vertex that connects $x$ and $y$, and
the number of the shortest paths between $x$ and $y$ only adds 1, thus we can
calculate $S_{u}(x,y)$ and reveal the previous contribution to update
$C_{B}(u)$, i.e., $C_{B}(u)=C_{B}(u)+1/(S_{u}(x,y)+1)-1/S_{u}(x,y)$. In
addition, for $x\in L$, $x$ and $v$ are connected, thus it does not contribute
to $C_{B}(u)$. For $x\notin L$, $(v,x)$ is a new vertex pair which makes
$C_{B}(u)$ increase, thus we need to compute $S_{u}(v,x)$ and update
$C_{B}(u)$ by adding $1/(S_{u}(v,x)+1)$. ∎

###### Lemma 5

Consider an inserted edge $(u,v)$, the updated ego-betweenness of $w\in L$ is:
$C_{B}(w)=C_{B}(w)-1/(S_{w}(u,v)+1)+\sum_{x\in N(w)\cap
N(u)-\\{v\\},(x,v)\notin E}(1/(S_{w}(x,v)+1)-1/S_{w}(x,v))+\sum_{x\in N(w)\cap
N(v)-\\{u\\},(x,u)\notin E}(1/(S_{w}(x,u)+1)-1/S_{w}(x,u))$.

###### Proof:

For vertex $w\in L$, the insertion of $(u,v)$ causes the direct connection
between $u$ and $v$ in $G_{E}(w)$ which makes $C_{B}(w)$ decrease. We need to
compute $S_{w}(u,v)$ before the insert operation and update $C_{B}(w)$ as:
$C_{B}(w)=C_{B}(w)-1/(S_{w}(u,v)+1)$. In addition, for $x\in N(w)\cap N(v)$
and $(u,x)\notin E$, $v$ now is a new vertex that links $u$ and $x$, thus we
calculate $S_{w}(u,x)$ and update $C_{B}(w)$ as:
$C_{B}(w)=C_{B}(w)+1/(S_{w}(u,x)+1)-1/S_{w}(u,x)$. Analogously, for $x\in
N(w)\cap N(u)$ and $(v,x)\notin E$, $u$ is a new vertex that connects $v$ and
$x$, we update $C_{B}(w)$ as the above operation. ∎

Equipped with the above lemmas, we propose a local update algorithm, called
$\mathsf{LocalInsert}$, to maintain the ego-betweennesses for handling edge
insertion. The pseudo-code of $\mathsf{LocalInsert}$ is illustrated in
Algorithm 4. $\mathsf{LocalInsert}$ first inserts the edge $(u,v)$ into $G$
(line 1). Then, it invokes the $\mathsf{LocalUptSMap}$ (Algorithm 5) to
recompute the number of shortest paths of the affected vertex pairs in the ego
networks of $u,v$ and their common neighbors (Observation 1). Finally,
$\mathsf{LocalInsert}$ updates the ego-betweennesses for affected vertices.
For the endpoints $u,v$ of the inserted edge, we calculate $C_{B}(u)$ and
$C_{B}(v)$ based on Lemma 4 (lines 4-9); On the other hand, for the common
neighbor $w$, $\mathsf{LocalInsert}$ updates $C_{B}(w)$ according to Lemma 5
(lines 10-15).

Input: $G=(V,E)$, an edge $(u,v)$.

Output: The map set $\mathcal{S}$.

1 $L\leftarrow N(u)\cap N(v)$;

2 for $x\in N(u)\backslash L$ do $S_{u}.{{\mathsf{insert}}}((x,v),0)$;

3 for $x\in N(v)\backslash L$ do $S_{v}.{{\mathsf{insert}}}((x,u),0)$;

4 for $x\in L$ do $S_{x}.{{\mathsf{insert}}}((u,v),0)$;

5 for  _$p\in L$_ do

6 for  _$x\in N(u)\cap N(p)$_ do

7 if  _$(x,v)\notin E$ and $x\neq v$_ then

8 $S_{u}(x,v)$++;

9 for  _$y\in N(x)\cap N(v)\cap N(p)$_ do

10 if $\nexists S_{p}(x,v)$ then $S_{p}.{{\mathsf{insert}}}((x,v),0)$;

11 $S_{p}(x,v)$++;

12

13

14

15 Update $S_{v}$, $S_{p}$ as lines 6-11;

16 for  _$q\in L$_ do

17 if  _$(p,q)\notin E$ and $q\prec p$ _ then

18 for  _$y\in N(u)\cap N(p)\cap N(q)$_ do

19 if $\nexists S_{u}(p,q)$ then $S_{u}.insert((p,q),0)$;

20 $S_{u}(p,q)$++;

21

22 Update $S_{v}$ as lines 15-17;

23

24 if  _$(p,q)\in E$ and $p\prec q$_ then

25 $S_{p}(u,v)$++; $S_{q}(u,v)$++;

26

27

28

29${\mathcal{S}}\leftarrow\\{S_{x}|x\in L\cup\\{u,v\\}\\}$;

30 return ${\mathcal{S}}$;

Algorithm 5 $\mathsf{LocalUptSMap}$

(a) $G_{E(k)}$

(b) $G_{E(i)}$

(c) $G_{E(f)}$

Figure 4: Running example

###### Example 5

Reconsider the graph $G$ in Fig. 1(a). Suppose that we insert an edge $(i,k)$
into $G$. Clearly, the ego-betweennesses of $i,k$ and their common neighbor
change based on Observation 1. Fig. 4(a) and Fig. 4(b) depict the ego networks
of $k$ and $i$, respectively. In Fig. 4(a), the new pairs, i.e., $(f,i)$ and
$(j,i)$, are generated due to the connection of $i$ and $k$, thus $C_{B}(k)$
changes. According to Lemma 4, the new $C_{B}(k)$ is
$C_{B}(k)=C_{B}(k)+1/(S_{k}(f,j)+1)-1/S_{k}(f,j)=1+1/(1+1)-1/1=1/2$.
Similarly, we can easily check that the updated ego-betweenness of $i$ is
$C_{B}(i)=10.5$ from $G_{E(i)}$. For the common neighbor $f$, its ego network
$G_{E(f)}$ is shown in Fig. 4(c). After the insertion of $(i,k)$, $C_{B}(f)$
decreases from 11 to 9.5. This is because $i$ is a neighbor of $k$ and they no
longer need intermediate vertices to reach each other. In addition, the
shortest paths for some vertex pairs may pass through $i$ or $j$ and the
number of shortest paths of these pairs increases, thus makes $C_{B}(f)$
decrease.

###  IV-B Local update for edge deletion

Here we consider the case of deleting an edge $(u,v)$ from $G$. When $(u,v)$
is deleted, only the vertices in $L\cup\\{u,v\\}$ need to update their ego-
betweennesses according to Observation 1. Below we introduce the update rules
for $u$, $v$ and $w\in L$. Since the proofs of the following lammas are
similar to that of Lemma 4 and Lemma 5, we omit them due to the space
limitation.

###### Lemma 6

Consider a deleted edge $(u,v)$, the updated ego-betweenness of $u$ is:
$C_{B}(u)=C_{B}(u)+\sum_{x,y\in L,(x,y)\notin
E}(1/S_{u}(x,y)-1/(S_{u}(x,y)+1))-\sum_{x\in N(u),x\notin L}1/(S_{u}(v,x)+1)$.
The case of updating $C_{B}(v)$ is similar.

###### Lemma 7

Consider a deleted edge $(u,v)$, the updated ego-betweenness of $w\in L$ is:
$C_{B}(w)=C_{B}(w)+1/(S_{w}(u,v)+1)+\sum_{x\in{N(w)\cap
N(u)-\\{v\\}},(x,v)\notin
E}(1/S_{w}(x,v)-1/(S_{w}(x,v)+1))+\sum_{x\in{N(w)\cap
N(v)-\\{u\\}},(x,u)\notin E}(1/S_{w}(x,u)-1/(S_{w}(x,u)+1))$.

Note that $S_{u}(x,y)$ in Lemma 6 and Lemma 7 represents the value before
deleting the edge. In particular, $S_{w}(u,v)$ in Lemma 7 is the value after
the deleting update. Based on these lemmas, we present a local update
algorithm, called $\mathsf{LocalDelete}$, to maintain the ego-betweennesses
when an edge $(u,v)$ is deleted. The framework of $\mathsf{LocalDelete}$ is
similar to that of $\mathsf{LocalInsert}$. We only need to make the following
minor changes. For $u$ and $v$, $\mathsf{LocalDelete}$ modifies line 6 and
line 8 of Algorithm 4 to $C_{B}(u)\leftarrow C_{B}(u)-1/(S_{u}(x,y)+1)$ and
$C_{B}(u)\leftarrow C_{B}(u)+1/S_{u}(x,y)-1/(S_{u}(x,y)+1)$ based on Lemma 6.
According to Lemma 7, $\mathsf{LocalDelete}$ calculates $C_{B}(x)$ for a
common neighbor $x$ as $C_{B}(x)\leftarrow C_{B}(x)+1/(S_{x}(y,z)+1)$ and
$C_{B}(x)\leftarrow C_{B}(x)+1/S_{x}(y,z)-1/(S_{x}(y,z)+1)$ corresponding to
line 13 and line 15 of Algorithm 4. Note that $\mathsf{LocalDelete}$ first
performs $\mathsf{LocalUptSMap}$ (Algorithm 5) before deleting $(u,v)$ and
then updates the ego-betweennesses of the affected vertices. Finally, it
removes $(u,v)$ from $G$ and terminates. We omit the pseudo-code of
$\mathsf{LocalDelete}$ due to the space limit.

(a) $G_{E(c)}$

(b) $G_{E(g)}$

(c) $G_{E(e)}$

Figure 5: Running example

###### Example 6

Reconsider the graph $G$ in Fig. 1(a). Suppose that we delete an edge $(c,g)$
from $G$. The ego networks of $c,g$ and their common neighbor change; further
their ego-betweennesses need to be updated. For vertices $c$ and $g$, their
ego networks are depicted in Fig. 5(a) and Fig. 5(b). Since $c$ and $g$ are
disconnected, the pair $(c,i)$ in Fig. 5(b) no longer exists and the number of
shortest paths for the vertex pair $(e,d)$ changes. According to Lemma 6,
$C_{B}(g)$ should be updated as
$C_{B}(g)=C_{B}(g)-1/(S_{g}(c,i)+1)+1/S_{g}(e,d)-1/(S_{g}(e,d)+1)=2/3-1/3+1/2-1/3=1/2$.
Analogously, the $C_{B}(c)$ changes from $41/6$ to $55/6$ which can be easily
checked from Fig. 5(a). For the common neighbor $e$, its ego network
$G_{E(e)}$ is shown in Fig. 5(c). After deleting $(c,g)$, $C_{B}(e)$ is still
equal to $4.5$ according to Lemma 7.

###  IV-C Updating the top-$k$ results

Here we present lazy update techniques to maintain the top-$k$ results when
the graph is updated. The lazy-update techniques for edge insertion and edge
deletion are designed by maintaining a sorted list of the vertices.
Specifically, the sorted list, denoted by $H$, contains all vertices in $G$.
For each vertex $u$ in $H$, $u$ associates with two variables, namely,
$H(u).C_{B}$ and $H(u).F_{G}$, which represent the ego-betweenness $C_{B}(u)$
and the update state of $u$. If $H(u).F_{G}$ equals true, that means
$H(u).C_{B}$ is not the exact value and should be re-calculated. Otherwise,
$H(u).C_{B}$ is accurate. We calculate $H(u).C_{B}$ for each vertex $u$ and
initialize $H(u).F_{G}$ as false, and then sort all vertices in non-increasing
order of their ego-betweennesses to obtain $H$. Equipped with $H$, the lazy
update techniques for edge insertion and edge deletion are as follows.

Lazy update for edge insertion. Consider an insertion edge $(u,v)$ and a
common neighbor $w\in N(u)\cap N(v)$. The calculations of $C_{B}(u)$,
$C_{B}(v)$ and $C_{B}(w)$ are described in Lemma 4 and Lemma 5, respectively.
Obviously, $S_{*}(*,*)+1>S_{*}(*,*)$ holds, thus we have
$1/(S_{u*}(*,*)+1)<1/S_{*}(*,*)$. For vertex $w$, the parts $\sum_{x\in
N(w)\cap N(u)-\\{v\\},(x,v)\notin E}(1/(S_{w}(x,v)+1)-1/S_{w}(x,v))$ and
$\sum_{x\in N(w)\cap N(v)-\\{u\\},(x,u)\notin
E}(1/(S_{w}(x,u)+1)-1/S_{w}(x,u))$ are both less than $0$, and
$1/(S_{w}(u,v)+1)$ is subtracted from $C_{B}(w)$, thus $C_{B}(w)$ tends to
decrease. However, for vertex $u$ (as well as $v$), the part $\sum_{x\in
N(u),x\notin L}1/(S_{u}(v,x)+1)$ increases, but the part $\sum_{x,y\in
L,(x,y)\notin E}(1/(S_{u}(x,y)+1)-1/S_{u}(x,y))$ decreases, thus the changes
of $C_{B}(u)$ and $C_{B}(v)$ are unclear. Nevertheless, an interesting finding
is that with the insertion operation, the degrees of $u$ and $v$ increase and
the upper bounds of $C_{B}(u)$ and $C_{B}(v)$ also increase. Based on these
findings, we can implement a lazy update rule to maintain the top-$k$ results
for edge insertion.

Input: $G=(V,E)$, $H$, an inserted edge $(u,v)$, top-$k$ result set $R$.

Output: the updated $R$.

1 if  _$u\in R$_ then

2 Compute $H(u).C_{B}$; $H(u).F_{G}\leftarrow false$;

3 if  _$H(u).C_{B} <\min_{p\in R\backslash\\{u\\}}C_{B}(p)$_ then

4 while  _$true$_ do

5 $y\leftarrow\arg\max_{p\in H-R}H(p).C_{B}$;

6 if  _$H(y).F_{G}=false$ and $H(u).C_{B}<H(y).C_{B}$_ then

7 $R\leftarrow(R-\\{u\\})\cup\\{y\\}$; break;

8

9 else Compute $H(y).C_{B}$; $H(y).F_{G}\leftarrow false$;

10

11

12

13else

14 ${\mathsf{\overline{ub}}}(u)\leftarrow\frac{d(u)*(d(u)-1)}{2}$;

15 if  _${\mathsf{\overline{ub}}}(u) >\min_{p\in R}C_{B}(p)$_ then

16 Compute $H(u).C_{B}$; $H(u).F_{G}\leftarrow false$;

17 if  _$H(u).C_{B} >\min_{p\in R}C_{B}(p)$_ then

18 $y\leftarrow\arg\min_{p\in R}C_{B}(p)$;

19 $R\leftarrow(R-\\{y\\})\cup\\{u\\}$;

20

21

22 else $H(u).F_{G}\leftarrow true$;

23

24Update $H$ and $R$ according to $v$ as lines 1-16;

25 $L\leftarrow N(u)\cap N(v)$;

26 for  _$x\in L$_ do

27 if $x\in R$ then Update $H$ and $R$ according to $x$ as lines 2-8;

28 else $H(x).F_{G}\leftarrow true$;

29

30return $R$;

Algorithm 6 $\mathsf{LazyInsert}$

The lazy update algorithm to handle edge insertion, called
$\mathsf{LazyInsert}$, is shown in Algorithm 6. For the endpoint $u$ of the
inserted edge, $\mathsf{LazyInsert}$ first identifies whether $u$ is included
in the top-$k$ result set $R$. If $u\in R$, it calculates the ego-betweenness
$H(u).C_{B}$ and sets $H(u).F_{G}$ to false to indicate the correctness of
$H(u).C_{B}$. As $H(u).C_{B}$ is updated, we need to determine whether $u$
still belongs to $R$. If $H(u).C_{B}>=\min_{p\in R\backslash\\{u\\}}C_{B}(p)$
holds, $u$ is still included in the top-$k$ result set $R$. On the other hand,
$\mathsf{LazyInsert}$ compares $H(u).C_{B}$ with the ego-betweenness of the
$(k+1)$-th element in the sorted list $H$ (lines 4-8). Let $y$ denote the
$(k+1)$-th vertex in $H$. If $H(y).F_{G}$ is false, that means $y$ is the
vertex with the highest ego-betweenness that is not contained in $R$.
$\mathsf{LazyInsert}$ compares $H(u).C_{B}$ with $H(y).C_{B}$ and maintains
$R$ (lines 6-7). If $H(y).F_{G}=true$ holds, $\mathsf{LazyInsert}$ computes
$H(y).C_{B}$ and updates $H(y).F_{G}$, and then performs the next loop (line
8). While $u\notin R$, we derive the new upper bound
${\mathsf{\overline{ub}}}(u)$ of $H(u).C_{B}$ to determine whether
$H(u).C_{B}$ needs to be computed exactly (lines 10-16). If
${\mathsf{\overline{ub}}}(u)<=\min_{p\in R}C_{B}(p)$ holds, it means that
$H(u).C_{B}$ is not greater than $\min_{p\in R}C_{B}(p)$, thus $u$ is still
not an answer of the top-$k$ results and $\mathsf{LazyInsert}$ can avoid
calculating the correct $H(u).C_{B}$ and only updates $H(u).F_{G}$ to true
(line 16). Otherwise, $\mathsf{LazyInsert}$ calculates $H(u).C_{B}$ and
identifies whether $u$ should be inserted into $R$ (lines 12-15). Likewise, we
perform the same operation for the other endpoint $v$ (line 17). Then,
$\mathsf{LazyInsert}$ handles the common neighbors of $u$ and $v$ (lines
18-21). For vertex $x\in L$, the algorithm judges whether $x$ is included in
$R$. If yes, it updates $H$ and $R$ as the operations of $u$ (line 20). On the
other hand, because $C_{B}(x)$ is decreasing, $x$ is still not in the top-$k$
result set and thus $\mathsf{LazyInsert}$ avoids computing the exact
$H(x).C_{B}$ and only sets $H(x).F_{G}$ to true (line 21). Note that the ego-
betweennesses of the vertices in $R$ are always correct. Finally,
$\mathsf{LazyInsert}$ returns the top-$k$ vertices with the highest ego-
betweennesses correctly.

###### Example 7

Reconsider the graph $G$ in Fig. 1(a). Before inserting the edge $(i,k)$ into
$G$, we have $C_{B}(i)=8$ and $C_{B}(k)=1$. After the insertion, $C_{B}(i)$ is
equal to $10.5$ and $C_{B}(k)$ is $0.5$. For the common neighbor $f$,
$C_{B}(f)$ decreases from $11$ to $9.5$. Clearly, the change of the ego-
betweennesses for the ends of the insertion edge is uncertain while it is
decreasing for the common neighbors. Suppose that $k=1$ and the current result
set is $R=\\{f\\}$. For vertex $k$, it is not included in $R$ and its new
bound is $(3*2)/2=3<C_{B}(f)=11$, thus the calculation of $C_{B}(k)$ can be
skipped and we only set $H(k).FG$ to true. For vertex $i$, the new bound is
$(7*6)/2=21>C_{B}(f)=11$, thus we need to calculate the new $C_{B}(i)=10.5$
and update $R=\\{i\\}$. In this case, consider the common neighbor $f$, it is
not included in $R$. Since $C_{B}(f)$ is not incremental, it definitely not in
the top-1 result after inserting $(i,k)$, thus we can avoid calculating
$C_{B}(f)$ and updating the results $R$.

Lazy update for edge deletion. Consider the deletion edge $(u,v)$ and a common
neighbor $w\in N(u)\cap N(v)$. Like the edge insertion, the changes of
$C_{B}(u)$, $C_{B}(v)$ and $C_{B}(w)$ are as follows. $C_{B}(w)$ is definitely
non-decreasing while $C_{B}(u)$ and $C_{B}(v)$ are uncertain. Fortunately,
after deleting $(u,v)$, the degrees of $u$ and $v$ decrease and also the upper
bounds of $C_{B}(u)$ and $C_{B}(v)$ decrease. Based on this, we can implement
a lazy update algorithm which is very similar to edge insertion.

Our lazy update algorithm for handling edge deletion, called
$\mathsf{LazyDelete}$, can be easily devised by slightly modifying Algorithm
6. Like lines 14-15 of Algorithm 6, $\mathsf{LazyDelete}$ needs to find the
vertex $y$ with the lowest ego-betweenness in the top-$k$ results. Armed with
our lazy update technique, the ego-betweennesses of the vertices in $R$ are
not all correct, thus $\mathsf{LazyDelete}$ must find $y\in R$ with the lowest
ego-betweenness and $H(y).F_{G}=false$. The other steps of
$\mathsf{LazyDelete}$ are similar to those of $\mathsf{LazyInsert}$. Due to
the space limit, the pseudo-code of $\mathsf{LazyDelete}$ is omitted.

###### Example 8

Let us still consider the graph $G$ in Fig. 1(a). Before deleting the edge
$(c,g)$ from $G$, we have $C_{B}(c)=41/6$, $C_{B}(g)=2/3$ and $C_{B}(e)=9/2$.
After the deletion, the new ego-betweennesses for $c$, $g$, and $e$ are
$55/6,1/2,9/2$, respectively. Obviously, the change of the ego-betweennesses
for the ends of the deletion edge is uncertain while it is non-decreasing for
the common neighbors. Suppose that $k=1$ and we can check that the current
$R=\\{f\\}$. For vertex $g$, its new bound is equal to $(3*2)/2=3<C_{B}(f)=11$
and $g\notin R$, thus we do not need to calculate the new ego-betweenness for
$g$ and only set $H(g).FG$ to true. For vertex $c$, its new bound is
$(6*5)/2=15>C_{B}(f)=11$, thus we calculate the new $C_{B}(c)=55/6$ and the
top-1 answer is still $f$. When $k=12$, the top-$k$ results before deleting
the edge $(c,g)$ is the set $V-\\{u,v,y,z\\}$. In this case, the common
neighbor $e$ is included in $R$. Since $C_{B}(e)$ is non-decreasing after
deleting $(c,g)$ , it is definitely still contained in the top-$12$ results,
thus we can avoid updating the answer set $R$.

##  V The parallel algorithms

In this section, we propose parallel ego-betweenness algorithms to improve the
scalability of ego-betweenness computation. We first introduce a vertex-based
parallel algorithm and then propose an edge-based parallel algorithm to
further improve efficiency.

###  V-A A vertex-based parallel algorithm

The ego-betweenness of a vertex is defined on its ego network which can be
calculated independently, thus a straightforward parallel solution is to
process each vertex in parallel. However, such a simple solution may be
inefficient, especially for large graphs. When processing each vertex
independently, we need to construct its ego network and explore the _diamond_
structures (a diamond denotes two triangles that have a common edge), which
makes the same _diamond_ enumerated multiple times, resulting in repetitive
calculations. To solve this problem, we propose a vertex-based parallel
algorithm as follows.

As can be seen from Algorithm 1 and Algorithm 2, we explore the _diamond_
structures by searching triangles, thus we can employ a parallel triangle
enumeration to calculate the ego-betweennesses for all vertices. The main idea
is that every triangle in $G$ has a unique orientation based on the total
ordering, and only be enumerated when processing the highest-ranked vertex in
this triangle. When a triangle $\triangle_{(u,v,w)}$ is found, we utilize it
to explore _diamond_ s and maintain $S_{u}$, $S_{v}$, and $S_{w}$ which record
the number of shortest paths between their neighbors. Note that we should lock
the map $S$ when it is updated to ensure the correctness of the parallel
algorithm. To avoid frequent locking operations, we employ the idea of
Algorithm 2 to divide the neighbors of a vertex into the in-neighbors and out-
neighbors for delaying the updates of $S$, which can also search a triangle
once. As all triangles are enumerated, that is, the information of the number
of shortest paths is correctly maintained in the maps, we calculate the ego-
betweenness for each vertex in parallel according to Lemma 2. We refer to this
parallel implementation as $\mathsf{VertexPEBW}$ and omit the pseudo-code due
to the space limit.

###  V-B An edge-based parallel algorithm

In practice, $\mathsf{VertexPEBW}$ might still be inefficient, because the
out-degrees of the vertices typically exhibit a skew distribution, resulting
in the workloads of different threads are unbalanced. A better solution is to
enumerate triangles for each directed edge in parallel. This is because the
distribution of the number of common outgoing neighbors of the directed edges
is typically not very skew, thus improving the parallelism of the algorithm.
We refer to such an edge-parallel algorithm as $\mathsf{EdgePEBW}$. In the
experiments, we will compare the efficiency of $\mathsf{VertexPEBW}$ and
$\mathsf{EdgePEBW}$.

##  VI Experiments

TABLE I: Datasets Dataset | $n$ | $m$ | $d_{\max}$ | Desecription
---|---|---|---|---
$\mathsf{Youtube}$ | 1,134,890 | 2,987,624 | 28,754 | Social network
$\mathsf{WikiTalk}$ | 2,394,385 | 4,659,565 | 100,029 | Communication network
$\mathsf{DBLP}$ | 1,843,617 | 8,350,260 | 2,213 | Collaboration network
$\mathsf{Pokec}$ | 1,632,803 | 22,301,964 | 14,854 | Social network
$\mathsf{LiveJournal}$ | 3,997,962 | 34,681,189 | 14,815 | Social network

(a) $\mathsf{Youtube}$ (vary $k$)

(b) $\mathsf{WikiTalk}$ (vary $k$)

(c) $\mathsf{DBLP}$ (vary $k$)

(d) $\mathsf{Pokec}$ (vary $k$)

(e) $\mathsf{LiveJournal}$ (vary $k$)

Figure 6: Comparisons of $\mathsf{BaseBSearch}$ and $\mathsf{OptBSearch}$ on
various datasets

In this section, we conduct extensive experiments to evaluate the efficiency
and effectiveness of the proposed algorithms. We implement two top-$k$ ego-
betweenness search algorithms, namely, $\mathsf{BaseBSearch}$ and
$\mathsf{OptBSearch}$ (Algorithm 1 and Algorithm 2). To maintain the ego-
betweennesses for all vertices, we implement $\mathsf{LocalInsert}$ (Algorithm
4) and $\mathsf{LocalDelete}$ for handling edge insertion and edge deletion,
respectively. We also implement $\mathsf{LazyInsert}$ (Algorithm 6) and
$\mathsf{LazyDelete}$ to maintain the top-$k$ results for edge insertion and
edge deletion, respectively. In addition, we implement two parallel
algorithms, $\mathsf{VertexPEBW}$ and $\mathsf{EdgePEBW}$, to calculate ego-
betweennesses of all vertices using OpenMP. All algorithms are implemented in
C++. All experiments are conducted on a PC with 2.10GHz CPU and 256GB memory
running Red Hat 4.8.5.

Datasets. We use 5 different types of real-life networks in the experiments,
including social networks, communication networks and collaboration networks.
The detailed statistics of the datasets are summarized in Table I. In Table I,
$d_{\max}$ denotes the maximum degree of the graph. All these datasets are
downloaded from snap.stanford.edu.

Parameters. The parameter $k$ in our algorithms is chosen from the set
$\\{50,100,200,500,1000,2000\\}$ with a default value of $k=500$. The
parameter $\theta$ in $\mathsf{OptBSearch}$ is selected from the set
$\\{1.05,1.10,1.15,1.20,1.25,1.30\\}$ with a default value 1.05. We will study
the performance of our algorithms with varying $k$ and $\theta$. Unless
otherwise specified, the value of a parameter is set to its default value when
varying another parameter.

###  VI-A Efficiency testing

TABLE II: The number of vertices for exact computation

Dataset | $k=500$ | $k=1000$ | $k=2000$
---|---|---|---
| $\mathsf{BaseBS}$ | $\mathsf{OptBS}$ | $\mathsf{BaseBS}$ | $\mathsf{OptBS}$ | $\mathsf{BaseBS}$ | $\mathsf{OptBS}$
$\mathsf{Youtube}$ | 564 | 522 | 1143 | 1032 | 2324 | 2065
$\mathsf{WikiTalk}$ | 527 | 508 | 1052 | 1013 | 2098 | 2013
$\mathsf{DBLP}$ | 557 | 550 | 1499 | 1160 | 3060 | 2491
$\mathsf{Pokec}$ | 567 | 552 | 1230 | 1168 | 2498 | 2367
$\mathsf{LiveJournal}$ | 791 | 615 | 1723 | 1282 | 3406 | 2413

(a) $\mathsf{WikiTalk}$ (vary $\theta$)

(b) $\mathsf{LiveJournal}$ (vary $\theta$)

Figure 7: Evaluation of $\mathsf{OptBSearch}$ with varying $\theta$

Exp-1: Comparison between $\mathsf{BaseBSearch}$ and $\mathsf{OptBSearch}$.
Fig. 6 shows the runtime of $\mathsf{BaseBSearch}$ and $\mathsf{OptBSearch}$
with varying $k$ on all datasets. As expected, the runtime of both
$\mathsf{BaseBSearch}$ and $\mathsf{OptBSearch}$ increases as $k$ increases.
As can be seen, $\mathsf{OptBSearch}$ is around 6-23 times faster than
$\mathsf{BaseBSearch}$ with all parameter settings. For example, on
$\mathsf{DBLP}$, $\mathsf{OptBSearch}$ takes 10.198 seconds, while
$\mathsf{BaseBSearch}$ consumes 240.482 seconds to retrieve the top-50
results. In the case of $k=2000$ on $\mathsf{LiveJournal}$,
$\mathsf{OptBSearch}$ takes 2,558.002 seconds, while $\mathsf{BaseBSearch}$
consumes 52,599.764 seconds which is roughly 20 times slower than
$\mathsf{OptBSearch}$. This is because the dynamic upper bound is tighter than
the static upper bound, thus it is more effective to prune the unpromising
vertices that are not included in the top-$k$ results. We also record the
number of vertices whose ego-betweennesses are computed exactly in
$\mathsf{BaseBSearch}$ and $\mathsf{OptBSearch}$. For brevity, we refer to
$\mathsf{BaseBSearch}$ and $\mathsf{OptBSearch}$ as $\mathsf{BaseBS}$ and
$\mathsf{OptBS}$. Table II illustrates the results of $k=500,1000,2000$ on all
datasets. Similar results can be observed for other $k$ values. As can be
seen, the number of vertices computed by $\mathsf{OptBSearch}$ is
significantly less than that computed by $\mathsf{BaseBSearch}$ on all
datasets. For example, to obtain the top-2000 results on
$\mathsf{LiveJournal}$, $\mathsf{OptBSearch}$ only needs to compute the ego-
betweennesses for 2,413 vertices, while $\mathsf{BaseBSearch}$ has to compute
3,406 vertices. These results further confirm our theoretical analysis in
Section III.

(a) edge insertion

(b) edge deletion

Figure 8: Average runtime of the updating algorithms

(a) $\mathsf{LiveJournal}$ (vary $m$)

(b) $\mathsf{LiveJournal}$ (vary $n$)

Figure 9: Scalability of $\mathsf{BaseBSearch}$ and $\mathsf{OptBSearch}$

Exp-2: The effect of $\theta$. Fig. 7 reports the effect of parameter $\theta$
in $\mathsf{OptBSearch}$ on $\mathsf{WikiTalk}$ and $\mathsf{LiveJournal}$.
The results on the other datasets are consistent. As can be seen, the runtime
of $\mathsf{OptBSearch}$ varies slightly with different $\theta$ values. In
general, $\mathsf{OptBSearch}$ performs slightly better with a relatively
small $\theta$. For example, with $\theta=1.05$, $\mathsf{OptBSearch}$
consumes the lowest runtime on both $\mathsf{WikiTalk}$ and
$\mathsf{LiveJournal}$. Note that a large $\theta$ may increase the cost of
computing the exact ego-betweennesses, while a small $\theta$ may increase the
cost of updating the upper bounds in $H$. These results indicate that when
$\theta=1.05$, $\mathsf{OptBSearch}$ can achieve a good tradeoff between these
two costs.

Exp-3: Evaluation of the updating algorithms. To evaluate the performance of
our updating algorithms, we randomly select 1,000 edges for insertion and
deletion on each dataset. Fig. 8 shows the average runtime of
$\mathsf{LocalInsert}$, $\mathsf{LocalDelete}$, $\mathsf{LazyInsert}$ and
$\mathsf{LazyDelete}$ on all datasets. As expected, the update time of
$\mathsf{LazyInsert}$ is lower than that of $\mathsf{LocalInsert}$. For
example, on $\mathsf{LiveJournal}$, the $\mathsf{LocalInsert}$ consumes 0.578
seconds to maintain ego-betweennesses for all vertices, while
$\mathsf{LazyInsert}$ takes 0.304 seconds for updating the top-$k$ results.
Similar results can also be observed for $\mathsf{LocalDelete}$ and
$\mathsf{LazyDelete}$. In addition, the average runtime of
$\mathsf{LocalInsert}$ ($\mathsf{LazyInsert}$) and $\mathsf{LocalDelete}$
($\mathsf{LazyDelete}$) is almost the same. Note that the runtime of all our
updating algorithms is smaller than 0.7 seconds over all datasets. These
results indicate that the proposed updating algorithms are very efficient on
large real-life graphs.

Exp-4: Scalability testing. Here we evaluate the scalability of
$\mathsf{BaseBSearch}$ and $\mathsf{OptBSearch}$. To this end, we generate
four subgraphs for each dataset by randomly picking 20%-80% of the edges
(vertices), and evaluate the runtime of $\mathsf{BaseBSearch}$ and
$\mathsf{OptBSearch}$ on these subgraphs. Fig. 9 illustrates the results on
$\mathsf{LiveJournal}$. The results on the other datasets are similar. As can
be seen, the runtime of $\mathsf{OptBSearch}$ increases very smoothly with
increasing $m$ or $n$, while the runtime of $\mathsf{BaseBSearch}$ increases
more sharply. Again, we can see that $\mathsf{OptBSearch}$ is significantly
faster than $\mathsf{BaseBSearch}$ with all parameter settings, which is
consistent with our previous findings.

(a) $\mathsf{LiveJournal}$

(b) $\mathsf{LiveJournal}$

Figure 10: Evaluation of the parallel algorithms

(a) $\mathsf{WikiTalk}$

(b) $\mathsf{Pokec}$

(c) $\mathsf{WikiTalk}$

(d) $\mathsf{Pokec}$

Figure 11: Comparison between $\mathsf{TopBW}$ and $\mathsf{TopEBW}$

Exp-5: Evaluation of parallel algorithms. We vary the number of threads $t$
from 1 to 16, and evaluate two parallel algorithms, i.e.,
$\mathsf{VertexPEBW}$ and $\mathsf{EdgePEBW}$, with an increasing $t$. We run
$\mathsf{OptBSearch}$ with the parameter $k=n$ to compute ego-betweennesses as
baseline for $t=1$. Fig. 10 shows the results of runtime and speedup ratio on
$\mathsf{LiveJournal}$. From Fig. 10, we can see that both
$\mathsf{VertexPEBW}$ and $\mathsf{EdgePEBW}$ achieve very good speedup
ratios. The runtime of $\mathsf{EdgePEBW}$ is lower than $\mathsf{VertexPEBW}$
with all parameter settings. For example, the running time of
$\mathsf{OptBSearch}$ to calculate ego-betweennesses for all vertices is
14,487.840 seconds. When $t=16$, $\mathsf{VertexPEBW}$ takes 1,156.916 seconds
and $\mathsf{EdgePEBW}$ consumes 900.439 seconds to compute the results. The
speedup ratios of $\mathsf{VertexPEBW}$ and $\mathsf{EdgePEBW}$ are roughly
equal to 12 and 16, respectively. These results indicate that our parallel
algorithms are very efficient on real-life graphs.

###  VI-B Effectiveness testing

In this experiment, we evaluate the effectiveness of the proposed algorithms.
For comparison, we make use of the state-of-the-art Brandes’ algorithm [6] to
compute betweenness for each vertex and then identify the top-$k$ vertices
with the highest betweennesses. We refer to this baseline algorithm as
$\mathsf{TopBW}$ and our $\mathsf{OptBSearch}$ as $\mathsf{TopEBW}$ for
brevity. The top-$k$ results obtained by $\mathsf{TopBW}$ and
$\mathsf{TopEBW}$ are denoted as $\mathsf{BW}$ and $\mathsf{EBW}$
respectively.

(a) $\mathsf{DB}$

(b) $\mathsf{IR}$

(c) $\mathsf{DB}$

(d) $\mathsf{IR}$

Figure 12: Comparison between $\mathsf{TopBW}$ and $\mathsf{TopEBW}$ on
$\mathsf{DBLP}$

Exp-6: Comparison between $\mathsf{TopBW}$ and $\mathsf{TopEBW}$. We compare
$\mathsf{TopBW}$ and $\mathsf{TopEBW}$ on $\mathsf{WikiTalk}$ and
$\mathsf{Pokec}$ with $k\in\\{50,100,200,500,1000,2000\\}$. The results on the
other datasets are consistent. Note that to speed up the betweenness
computation, we also implement a parallel version of $\mathsf{TopBW}$ for
comparison. The running time of $\mathsf{TopBW}$ with 64 threads and
$\mathsf{TopEBW}$ is shown in Fig. 11(a-b). Clearly, $\mathsf{TopEBW}$ is at
least two orders of magnitude faster than the parallel $\mathsf{TopBW}$ within
all parameter settings. For example, on $\mathsf{Pokec}$, $\mathsf{TopEBW}$
takes 112.369 seconds, while $\mathsf{TopBW}$ consumes 559,322.062 seconds to
output the top-$50$ results.

Fig. 11(c-d) report the overlap of the top-$k$ results obtained by
$\mathsf{TopBW}$ and $\mathsf{TopEBW}$. As can be seen, the overlap is
generally higher than 60% on all datasets. Particularly, on
$\mathsf{WikiTalk}$, the overlap is even more than 80%. These results indicate
that the ego-betweenness centrality is a very good approximation of the
betweenness centrality. Moreover, compared to betweenness centrality, the ego-
betweenness centrality is much cheaper to compute using the proposed
algorithms.

TABLE III: Top-10 scholars in $\mathsf{DB}$

Top-10 EBW | $d$ | $C_{B}$ | Top-10 BW | $d$ | $B_{T}$
---|---|---|---|---|---
*Jiawei Han | 412 | 73,928.5 | *Philip S. Yu | 360 | 50,320,100
*Philip S. Yu | 360 | 58,834.1 | *Jiawei Han | 412 | 50,059,900
*Christos Faloutsos | 337 | 52,192.9 | *Christos Faloutsos | 337 | 46,340,200
*Jian Pei | 215 | 20,531.1 | *Gerhard Weikum | 213 | 26,232,700
*Gerhard Weikum | 213 | 19,238.3 | *Beng Chin Ooi | 205 | 22,376,200
*Michael J. Franklin | 220 | 17,867.5 | *Jian Pei | 215 | 21,470,900
Michael Stonebraker | 210 | 16,081.4 | *Michael J. Franklin | 220 | 20,809,000
*Raghu Ramakrishnan | 210 | 15,930.1 | *Raghu Ramakrishnan | 210 | 18,481,900
*Beng Chin Ooi | 205 | 14,848.2 | Haixun Wang | 183 | 17,062,500
Hector Garcia-Molina | 197 | 14,664.8 | H. V. Jagadish | 178 | 16,144,700

TABLE IV: Top-10 scholars in $\mathsf{IR}$

Top-10 EBW | $d$ | $C_{B}$ | Top-10 BW | $d$ | $B_{T}$
---|---|---|---|---|---
*Jeffrey P. Bigham | 2441 | 1.4846e+06 | *Taesup Moon | 2318 | 1.33948e+07
*Alex D. Wade | 2510 | 1.46767e+06 | *Jeffrey P. Bigham | 2441 | 1.1711e+07
*Adam Sadilek | 1993 | 1.30844e+06 | *Alex D. Wade | 2510 | 1.10161e+07
*Taesup Moon | 2318 | 1.25722e+06 | *Adam Sadilek | 1993 | 9.49158e+06
*Antonio Gulli | 1951 | 1.16136e+06 | *Antonio Gulli | 1951 | 9.44098e+06
*Henry A. Kautz | 1731 | 882,981 | *Bob Boynton | 1618 | 7.00364e+06
*Bob Boynton | 1618 | 844,761 | *Henry A. Kautz | 1731 | 6.82747e+06
*Padmini Srinivasan | 1541 | 822,131 | Linchuan Xu | 1834 | 6.79258e+06
*Yelena Mejova | 1210 | 580,116 | *Padmini Srinivasan | 1541 | 6.41121e+06
Raymie Stata | 796 | 224,422 | *Yelena Mejova | 1210 | 5.82391e+06

Exp-7: Case study on $\mathsf{DBLP}$. We extract two subgraphs, namely,
$\mathsf{DB}$ and $\mathsf{IR}$, from $\mathsf{DBLP}$ for case study.
$\mathsf{DB}$ contains the authors in $\mathsf{DBLP}$ who had published at
least one paper in the database and data mining related conferences. The
$\mathsf{DB}$ subgraph contains 37,177 vertices and 131,715 edges. The
$\mathsf{IR}$ subgraph contains the authors who had published at least one
paper in the information retrieval related conferences with 13,445 vertices
and 37,428 edges. We invoke $\mathsf{TopBW}$ ($\mathsf{TopEBW}$) to find the
top-$k$ highest (ego-)betweennesses scholars on $\mathsf{DB}$ and
$\mathsf{IR}$ with the parameter $k\in\\{10,50,100,150,200,250\\}$. The
results are shown in Fig. 12. Consistent with the previous findings, the
running time of $\mathsf{TopEBW}$ is significantly faster than
$\mathsf{TopBW}$. Moreover, the overlap of the top-$k$ results is
significantly high. For example, on $\mathsf{DB}$, $\mathsf{TopEBW}$ takes
22.777 seconds, while $\mathsf{TopBW}$ consumes 27641.190 seconds to output
the top-$100$ results. The overlap of the top-$100$ results on $\mathsf{DB}$
is 78%. Similar results can also be observed on $\mathsf{IR}$.

We also illustrate the top-$10$ scholars on $\mathsf{DB}$ and $\mathsf{IR}$ in
Table III and Table IV. In both Table III and Table IV, $d$ denotes the number
of co-authors of a scholar; $C_{B}$ and $B_{T}$ denote the ego-betweenness and
betweenness of a scholar respectively. Clearly, the overlaps of the top-$10$
results are 80% and 90% on $\mathsf{DB}$ and $\mathsf{IR}$ respectively.
Moreover, we can see that the top-10 scholars with the highest ego-
betweennesses are the most influential in the database, data mining, and
information retrieval communities. Such scholars may play a bridge role in
connecting different research groups. For example, in Table III, Professor
Jiawei Han has 412 co-authors and maintains connections with many different
research groups. Similarly, in Table IV, Taesup Moon is interested in diverse
areas such as information retrieval, statistical machine learning, information
theory, signal processing and so on, thus he plays an important role in
promoting the interactions between different research communities. These
results indicate that our algorithms can be used to find high influential
vertices in a network that act as network bridges.

##  VII Related work

Betweenness centrality. Our work is closely related to betweenness centrality
[6, 14]. Betweenness centrality is an important measure of centrality in a
graph based on the shortest path, which has been applied to a wide range of
applications in social networks [3], biological networks [4], computer
networks [5], road networks [2] and so on. The best-known algorithm for
betweenness computation, proposed by Brandes [6], runs ${\mathcal{O}}(nm)$
time complexity for unweighted networks. Measuring the betweenness centrality
scores of all vertices is notoriously expensive, thus many parallel and
approximate algorithms have been developed to reduce the computation cost [15,
16, 17, 18, 19]. Fan _et al._ proposed an efficient parallel GPU-based
algorithm for computing betweenness centrality in large weighted networks and
integrated the work-efficient strategy to address the load-imbalance problem
[15]. Furno _et al._ studied the performance of a parametric two-level
clustering algorithm for computing approximate value of betweenness with an
ideal speedup with respect to Brandes’ algorithm [18]. In this paper, we focus
on the ego-betweenness centrality which is first proposed by Everett _et al._
[7] as an approximation of betweenness centrality. Ego-betweenness centrality
has gained recognition in its own right as a natural measure of a node’s
importance as a network bridge [20]. To the best of our knowledge, our work is
the first to study the problem of finding top-$k$ ego-betweenness vertices in
graphs.

Top-$k$ retrieval. Our work is also related to the top-$k$ retrieval problem,
which aims to find $k$ results with the largest scores/relevances based on a
pre-defined ranking function [21]. The general framework for answering top-$k$
queries is to process the candidates according to a heuristic order and prune
the search space based on some carefully-designed upper bounds. An excellent
survey can be found in [21]. There are many studies on top-$k$ query
processing for heterogeneous applications, such as processing distributed
preference queries [22], keyword queries [23], set similarity join queries
[24]. An influential algorithm was proposed by Fagin _et al._ [25, 26], which
considers both random access and/or sequential access of the ranked lists.
Recently, some studies take diversity into consideration in the top-$k$
retrieval in order to return diversified ranking results [27, 28, 29, 30, 31].
For instance, Li _et al._ proposed a scalable algorithm to achieve near-
optimal top-$k$ diversified ranking with linear time and space complexity with
respect to the graph size. Some studies have also been done which focus mainly
on exploring influential communities, individuals, and relationships in
different networks [32, 33, 8, 9, 10]. For example, the study [33]
investigated an instance-optimal algorithm, which runs in linear time
complexity without indexes, for computing the top-$k$ influential communities.
In this paper, we develop two search frameworks to identify the top-$k$
vertices with the highest ego-betweennesses and propose efficient techniques
to maintain top-$k$ results when the graph is updated.

##  VIII Conclusion

In this paper, we study a problem of finding the top-$k$ vertices in a graph
with the highest ego-betweennesses. To solve this problem, we first develop
two top-$k$ search frameworks with a static upper bound and a novel dynamic
upper bound, respectively. Then, we propose efficient local maintenance
algorithms to maintain the ego-betweenness for each vertex when the graph is
updated. We also present lazy-update techniques to maintain the top-$k$
results in dynamic graphs. We conduct extensive experiments using five real-
life datasets to evaluate the proposed algorithms. The results demonstrate the
efficiency and scalability of our algorithms. Also, the results show that the
top-$k$ ego-betweenness results are highly similar to the top-$k$ betweenness
results, but they are much cheaper to compute by our algorithms.

## References

  * [1] Linton C Freeman.  A set of measures of centrality based on betweenness.  Sociometry, pages 35–41, 1977.
  * [2] Mark EJ Newman.  The mathematics of networks.  The new palgrave encyclopedia of economics, 2(2008):1–12, 2008\.
  * [3] David Alfred Ostrowski.  An approximation of betweenness centrality for social networks.  In ICSC, pages 489–492, 2015.
  * [4] Hawoong Jeong, Sean P Mason, A-L Barabási, and Zoltan N Oltvai.  Lethality and centrality in protein networks.  Nature, 411(6833):41–42, 2001.
  * [5] Luca Baldesi, Leonardo Maccari, and Renato Lo Cigno.  On the use of eigenvector centrality for cooperative streaming.  IEEE Communications Letters, 21(9):1953–1956, 2017.
  * [6] Ulrik Brandes.  A faster algorithm for betweenness centrality.  Journal of mathematical sociology, 25(2):163–177, 2001.
  * [7] Martin Everett and Stephen P Borgatti.  Ego network betweenness.  Social networks, 27(1):31–38, 2005.
  * [8] Xin Huang, Hong Cheng, Rong-Hua Li, Lu Qin, and Jeffrey Xu Yu.  Top-k structural diversity search in large networks.  VLDB Journal, 24(3):319–343, 2015.
  * [9] Lijun Chang, Chen Zhang, Xuemin Lin, and Lu Qin.  Scalable top-k structural diversity search.  In ICDE, pages 95–98, 2017.
  * [10] Qi Zhang, Rong-Hua Li, Qixuan Yang, Guoren Wang, and Lu Qin.  Efficient top-k edge structural diversity search.  In ICDE, pages 205–216, 2020.
  * [11] Norishige Chiba and Takao Nishizeki.  Arboricity and subgraph listing algorithms.  SIAM Journal on computing, 14(1):210–223, 1985.
  * [12] Min Chih Lin, Francisco J. Soulignac, and Jayme Luiz Szwarcfiter.  Arboricity, h-index, and dynamic algorithms.  Theor. Comput. Sci., 426:75–90, 2012.
  * [13] C. St. J. A. Nash-Williams.  Decomposition of finite graphs into forests.  Journal of the London Mathematical Society, 39(1):12–12, 1964.
  * [14] Linton C Freeman.  Centrality in social networks conceptual clarification.  Social networks, 1(3):215–239, 1978.
  * [15] Rui Fan, Ke Xu, and Jichang Zhao.  A gpu-based solution for fast calculation of the betweenness centrality in large weighted networks.  PeerJ Comput. Sci., 3:e140, 2017.
  * [16] Ranjan Kumar Behera, Debadatta Naik, Dharavath Ramesh, and Santanu Kumar Rath.  MR-IBC: mapreduce-based incremental betweenness centrality in large-scale complex networks.  Soc. Netw. Anal. Min., 10(1):25, 2020.
  * [17] Mostafa Haghir Chehreghani.  An efficient algorithm for approximate betweenness centrality computation.  Comput. J., 57(9):1371–1382, 2014.
  * [18] Angelo Furno, Nour-Eddin El Faouzi, Rajesh Sharma, and Eugenio Zimeo.  Reducing pivots of approximated betweenness computation by hierarchically clustering complex networks.  In COMPLEX NETWORKS, pages 65–77, 2017.
  * [19] Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz.  Simple and fast distributed computation of betweenness centrality.  In INFOCOM, pages 337–346, 2020.
  * [20] Peter V Marsden.  Egocentric and sociocentric measures of network centrality.  Social networks, 24(4):407–422, 2002.
  * [21] Ihab F Ilyas, George Beskales, and Mohamed A Soliman.  A survey of top-k query processing techniques in relational database systems.  ACM Computing Surveys, 40(4):11, 2008.
  * [22] Kevin Chen-Chuan Chang and Seung-won Hwang.  Minimal probing: supporting expensive predicates for top-k queries.  In SIGMOD, pages 346–357, 2002.
  * [23] Yi Luo, Xuemin Lin, Wei Wang, and Xiaofang Zhou.  Spark: top-k keyword query in relational databases.  In SIGMOD, pages 115–126, 2007.
  * [24] Chuan Xiao, Wei Wang, Xuemin Lin, and Haichuan Shang.  Top-k set similarity joins.  In ICDE, pages 916–927, 2009.
  * [25] Ronald Fagin.  Combining fuzzy information from multiple systems.  Journal of computer and system sciences, 58(1):83–99, 1999.
  * [26] Ronald Fagin, Amnon Lotem, and Moni Naor.  Optimal aggregation algorithms for middleware.  Journal of computer and system sciences, 66(4):614–656, 2003.
  * [27] Lu Qin, Jeffrey Xu Yu, and Lijun Chang.  Diversifying top-k results.  Proceedings of the VLDB Endowment, 5(11):1124–1135, 2012.
  * [28] Rong-Hua Li and Jeffery Xu Yu.  Scalable diversified ranking on large graphs.  IEEE TKDE, 25(9):2133–2146, 2013.
  * [29] Albert Angel and Nick Koudas.  Efficient diversity-aware search.  In Proceedings of SIGMOD, pages 781–792, 2011.
  * [30] Xiaofei Zhu, Jiafeng Guo, Xueqi Cheng, Pan Du, and Hua-Wei Shen.  A unified framework for recommending diverse and relevant queries.  In Proceedings of WWW, pages 37–46, 2011.
  * [31] Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong.  Diversifying search results.  In Proceedings of WSDM, pages 5–14, 2009.
  * [32] Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie.  Community-based greedy algorithm for mining top-k influential nodes in mobile social networks.  In KDD, pages 1039–1048, 2010.
  * [33] Fei Bi, Lijun Chang, Xuemin Lin, and Wenjie Zhang.  An optimal and progressive approach to online search of top-k influential communities.  VLDB, 11(9):1056–1068, 2018.