# LUEM : Local User Engagement Maximization in Networks

Junghoon Kim  UNISTSouth Korea<EMAIL_ADDRESS>,  Jungeun Kim  Kongju
National UniversitySouth Korea<EMAIL_ADDRESS>,  Hyun Ji Jeong  Korea
Institute of Science and Technology InformationSouth Korea<EMAIL_ADDRESS>and  Sungsu Lim  Chungnam National UniversitySouth Korea<EMAIL_ADDRESS>
(2018)

###### Abstract.

Understanding a social network is a fundamental problem in social network
analysis because of its numerous applications. Recently, user engagement in
networks has received extensive attention from many research groups. However,
most user engagement models focus on global user engagement to maximize (or
minimize) the number of engaged users. In this study, we formulate the so-
called Local User Engagement Maximization (LUEM) problem. We prove that the
LUEM problem is NP-hard. To obtain high-quality results, we propose an
approximation algorithm that incorporates a traditional hill-climbing method.
To improve efficiency, we propose an efficient pruning strategy while
maintaining effectiveness. In addition, by observing the relationship between
the degree and user engagement, we propose an efficient heuristic algorithm
that preserves effectiveness. Finally, we conducted extensive experiments on
ten real-world networks to demonstrate the superiority of the proposed
algorithms. We observed that the proposed algorithm achieved up to 605% more
engaged users compared to the best baseline algorithms.

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

With the proliferation of mobile devices and the development of IT industry,
many people use social networking services via mobile devices every day,
anywhere, and anytime. One of the biggest social networking services,
Facebook, has reached over 2.8 billion monthly active users in 2021. Moreover,
approximately seven-in-ten U.S. adults use Facebook.

With the increasing popularity of social networking services, understanding
social networks is an important and fundamental problem (Jin et al., 2013;
Schneider et al., 2009). There have been several efforts to capture the
characteristics of social networks, such as the importance of user nodes
(Bonacich, 1987; Borgatti and Everett, 2006; Sabidussi, 1966) or social
relationships (Brandes, 2001; De Meo et al., 2012; Mavroforakis et al., 2015),
stability of a network (Zhu et al., 2018), degree distribution (Barabási and
Albert, 1999), small average distance (Backstrom et al., 2012), and community
size distribution (Stephen and Toubia, 2009).

In addition, encouraging user engagement (Malliaros and Vazirgiannis, 2013;
Zhou et al., 2019; Bhawalkar et al., 2015; Ghafouri et al., 2020; Zhang et
al., 2017a; Liu et al., 2021; Linghu et al., 2020) in social networks has
recently received extensive attention from many research groups. This study
focused on engaged (activated) users in a social network. In practice, many
services have many registered users but the amount of people who actively use
the service is another matter. We can observe that many of the previously used
services were shut down. Even if there are many registered users, if people do
not actively use it, the service becomes meaningless. The most widely accepted
model (Bhawalkar et al., 2012; Zhang et al., 2017b; Linghu et al., 2020; Kim
et al., 2022a; Cai et al., 2020) for measuring the user engagement in a social
network is based on the minimum degree (Seidman, 1983), which indicates that
every engaged user has at least $k$ friends on a social network. Formally,
given a graph $G=(V,E)$ and positive integer $k$, if a user has at least $k$
friends, the user is considered to be engaged. Otherwise, the user is
disengaged from the network. If any user is disengaged, a set of users can
iteratively be disengaged in a cascade manner because the number of friends of
the remaining users changes (Bhawalkar et al., 2015; Zhang et al., 2017a, c).
Note that the number of engaged users in a social network can be identified by
computing $k$-core (Seidman, 1983). There are two main research directions
regarding user engagement in social networks (Bhawalkar et al., 2012; Chitnis
et al., 2013; Zhang et al., 2017a; Luo et al., 2021, 2021). (1) The anchored
$k$-core problem was proposed by Bhawalkar et al. (Bhawalkar et al., 2012). It
aims to maximize the number of engaged users by anchoring $b$ disengaged
users. In other words, the problem is to find $b$ important disengaged users.
(2) The collapsed $k$-core problem was proposed by Zhang et al. (Zhang et al.,
2017a). It aims to minimize the number of engaged users by removing $b$ users,
that is, the problem is to find $b$ important engaged users.

Motivation. The above user engagement problems focus on graph-level user
engagement, that is, they aim to maximize (or minimize) the number of globally
engaged users in a network. This can be considered as a macro-level user
engagement. To get all the engaged users, most approaches utilize existing
cohesive subgraph models, such as $k$-core (Seidman, 1983) or $k$-truss
(Cohen, 2008). In the resultant cohesive subgraph, existing approaches try to
find a set of anchored nodes (Chitnis et al., 2013) in the non-engaged users
or collapsers (Zhang et al., 2017a) in the engaged users to maximize (or
minimize) the number of engaged users globally, i.e., the total number of
engaged or disengaged users is the major matter in the macro-level user
engagement. Note that these approaches assume that a given network is a
snapshot of a social network, i.e., each vertex is a real person and each edge
indicates a friend relation in a social networking service.

However, let assume that we want to perform targeted marketing for promotion,
which is known as an effective marketing tool. Targeted marketing involves
breaking the target users into segments and then selecting influential users
who widely spread our promotion. In targeted marketing, selecting influential
users for each segment is very important. Since the target user is found by
each segment, the user should have a local impact. In these days, according to
the proliferation of social networks, many companies use social networks to
find influential users. Hence, we propose the problem that finds a kind of
micro-level (or called local) user engagement from social networks.

This problem is distinguished from the anchored $k$-core problem (Chitnis et
al., 2013) and collapsed $k$-core problem (Zhang et al., 2017a). The following
example describes that our problem can be utilized to promote a social
networking service.

###### Example 0.

By utilizing the LUEM problem, we can find a set of people who effectively
promote the products to their friends. The selected people may have many
friends and there are sufficient social relationships among friends, i.e.,
they are important from the perspective of user engagement. This approach is
distinguished from the degree-based approach. If we consider only the degree
of the nodes, a set of fake accounts which has many fake friends will be
selected. These fake accounts have no effect on increasing the number of
engaged users since they may have only few relationships to each other.

As an alternative to the difficult-to-expect effects in global user
engagement, we focused on local user engagement, which unifies three key
concepts: (1) The existence of seed nodes, (2) minimum-degree-based user
engagement; and (3) seed-based distance cohesiveness. These key concepts are
described as follows:

Figure 1. Global user engagement and local user engagement

  * •

Existence of seed nodes : We focused on the local structure of seed nodes to
measure user engagement. This changes the perspective from a global network
structure to a local network structure. Intuitively, when a node is selected
as the seed node, a set of nodes closely related to the seed node can be
engaged. This can be considered as a micro-level of user engagement. This has
led to new applications. Figure 1 depicts the difference between the global
user engagement problem (macro-level, green-coloured) and proposed local user
engagement problem (micro-level, blue-coloured). Notice that local user
engagement has seed nodes, and the engaged users are affected by the seed
nodes and can overlap. There have been several similar attempts at social
network analysis. The influence maximization (IM) problem (Kempe et al., 2003)
aims to identify a set of seed nodes to maximize the spread of influence in a
social network under information diffusion models.

  * •

Minimum-degree-based structural cohesiveness : We incorporated the widely used
minimum-degree user engagement model (Bhawalkar et al., 2012; Zhang et al.,
2017c, a, 2018a) to measure user engagement. Formally, a user is engaged if
he/she has at least $k$ friends in the local structure. Otherwise, the user is
disengaged.

  * •

Distance-generalized cohesiveness : In the social sciences field, studying the
1-hop neighbor structure to capture structural characteristics is well
established (Luce, 1950). For the user engagement-related problem, the 1-hop
neighbor structure can be considered because many social networks are scale-
free (Barabási and Albert, 1999); thus, the degree of the nodes in social
networks follows a power-law distribution. Therefore, we generalize the
relationship between two nodes by incorporating the graph distance. i.e., if a
node is reachable from the seed node within a specific user-defined distance
threshold, the node can be engaged.

In this paper, we aim to find an answer to the question How many close
neighbor nodes will be engaged when a user is activated (becomes a seed node)?
This question is answered by proposing a new information diffusion model based
on user engagement in the IM problem. Compared to the traditional information
diffusion models, our model is characterized by a spreading limitation
(distance) and influenced limitation (minimum degree) without using any
simulation models. Hence, the results are deterministic. Figure 2 illustrates
a summary of our problem.

Figure 2. Illustration of our problem

We formulate a local user engagement maximization (LUEM) problem. First, we
propose a seed-based engaged group(SEG) for a specific node $v$. A set of
nodes $H$ is called the SEG of the node $v$ if the nodes in $H$ are engaged by
the seed node $v$. That is, the minimum degree of the induced subgraph of
nodes $H$ is larger than or equal to threshold $k$, and all nodes in $H$ are
reachable from $v$ at distance $r$. The LUEM problem is defined as follows.
Given a graph $G$, budget $b$, engagement threshold $k$, and distance
threshold $r$, LUEM aims to find $b$ seed nodes that can maximize the number
of engaged users who have at least $k$ friends in each SEG and are reachable
within a distance $r$ from the seed nodes. We show that this problem is NP-
hard, and the objective function is monotone submodular. Therefore, we present
an approximation algorithm that holds $1-1/e$-approximation ratio. We observe
that the main bottleneck of the proposed algorithm is to compute the SEGs of
the nodes because for each SEG, it is necessary to compute the $k$-core and
connected component containing a seed node ($O(|V|+|E|)$). Thus, to improve
efficiency, we propose a new heuristic algorithm that incorporates the
approximated neighborhood functions (Boldi et al., 2011) without computing all
SEGs at the initial stage.

Applications. The applications of our proposed problem are listed as follows:

  * •

Organizing a party. Let us assume that Joy wants to host a farewell party for
three consecutive holiday days by serving dinner. She would like to invite
three of her friend groups. Because her friends are from different groups,
such as a table tennis club, graduate association club, lab colleagues, etc.,
she would like to invite as many non-engaged people in the party as possible.
Here, finding a few friends to help her organize party.

  * •

Finding top-$b$ influential communities. Finding the engaged users of a
specific node can be considered as finding an influential community of the
specific node.

  * •

Finding key users in a social network. Important users are nodes that can
affect the network structure to a greater extent compared to other nodes
(Xiaolong and Linyuan, 2014). Our LUEM can be used to identify important users
in a social network using the user engagement model.

  * •

Virus propagation prediction/estimating influence spreading. LUEM can identify
a set of engaged users of a specific node, and thus, it can be utilized for
predicting the virus propagation and estimating the influence spreading. If a
user is infected, a set of close neighbor nodes has a high probability of
getting infected.

Challenges and Contributions Because the LUEM problem is NP-hard, computing an
exact solution within polynomial time is prohibited. Thus, the first challenge
is to compute an effective solution. The second challenge is the efficient
computation of the solution. To address these challenges, we propose two
algorithms: (1) An effective $r$-neighbor-based approximation algorithm (ERA)
and (2) Fast circle algorithm (FCA). First, the ERA algorithm incorporates a
traditional greedy algorithm to maximize the number of engaged users. Owing to
the submodularity of our objective function, we can design an efficient
strategy by not computing all engaged users for every iteration. ERA holds a
$1-1/e$ approximation ratio. In section 3, we present our main idea and
rigorous proof to demonstrate why the pruning strategy preserves the
approximation ratio. Next, we propose a heuristic algorithm called FCA to
improve the efficiency of the proposed algorithms. Even if our proposed ERA
significantly improves efficiency, in the worst case, it has the same time
complexity as a traditional greedy algorithm. Thus, in FCA, we propose a very
fast heuristic algorithm that incorporates the approximated neighborhood
function based on our observations.

The contributions of this research are summarized as follows:

  * •

Problem definition :  To the best of our knowledge, this is the first study to
identify a set of seed nodes to maximize the number of engaged users in a
social network.

  * •

Theoretical analysis :  We prove that the objective function of LUEM is
monotone submodular, and the LUEM problem is NP-hard.

  * •

Designing new algorithms :  Because our problem is NP-hard, we propose a
$1-1/e$ approximation algorithm, as well as a heuristic algorithm to improve
efficiency.

  * •

Extensive experimental study :  Using real-world datasets, we conduct
extensive experiments to demonstrate the superiority of the proposed
algorithms.

##  2\. Problem Statements

We present a Local User Engagement Maximization (LUEM) problem. In this study,
we consider an unweighted and undirected graph. Given a graph $G=(V,E)$ and
set of nodes $H\subseteq V$, we denote $G[H]=(H,E[H])$ as a subgraph of $G$
induced by nodes $H$. Table 1 lists the basic notations used in this study.
First, We introduce basic definitions of some terminology for presenting our
problem.

Table 1. Notation Description | Notation
---|---
minimum degree threshold | $k$
distance threshold | $r$
user engagement constraint | $\delta(.)$
distance constraint | $\tau(.)$
approximated neighbor value | $ANV$
$r$-neighbors of node $v$ in $G$ | $N_{r}(v,G)$
effective $r$-neighbors size of node $v$ | $\mathcal{E}_{r}(v)$
SEG of node $v$ | $\mathcal{K}_{k,r}(v)$
distinct engaged users in $\mathcal{K}$ |  $\rho$($S$)
engagement gain |  $\rho$($v$, $S$)

###### Definition 0.

(User engagement constraint $\delta(.)$)
Given a graph $G=(V,E)$ and positive integer $k$ called the minimum degree
threshold, a subgraph $H\subseteq V$ satisfies the user engagement constraint
if it is connected, and the minimum degree of induced subgraph $G[H]$ is
larger than or equal to $k$, i.e., $\delta(H)\geq k$.

Given a graph $G=(V,E)$, finding a maximal subgraph satisfying the minimum
degree constraint is the same as that in the classic $k$-core (Seidman, 1983)
problem. $k$-core can be computed in polynomial time.

###### Definition 0.

(Distance constraint $\tau(.)$)
Given a graph $G=(V,E)$, seed node $s\in V$, and positive integer $r$ called a
distance threshold, a subgraph $H\subseteq G$ satisfies the distance
constraint if it contains $s$, and the distance from $s$ to any node in the
induced subgraph $G[H]$ is less than or equal to $r$, that is, $\tau(s,H)\leq
r$.

We next define $r$-neighbors based on the distance threshold $r$.

###### Definition 0.

($r$-neighbors $N_{r}$)
Given a graph $G=(V,E)$, node $v\in V$, and positive integer $r$,
$r$-neighbors of $v$, denoted as $N_{r}(v,G)$, is a set of nodes that are
reachable from $v$ within a distance $r$ in graph $G$. We use
$N(v,G)=N_{1}(v,G)$, and $N(v)$ if it is obvious.

We are now ready to discuss user-level engagement by defining a set of users
engaged by the seed node as follows.

###### Definition 0.

(Seed-based engaged group(SEG))
Given a graph $G=(V,E)$, seed node $s$, and positive integers $k$ and $r$,
seed-based engaged group of the node $s$, denoted as $\mathcal{K}_{k,r}(s)$,
is a maximal set of nodes satisfying $\delta(\mathcal{K}_{k,r}(s))\geq k$ and
$\tau(s,\mathcal{K}_{k,r}(s))\leq r$. If it is obvious, we use
$\mathcal{K}(s)$ instead of $\mathcal{K}_{k,r}(s)$.

Note that a set of users in $\mathcal{K}(s)$ is considered as engaged by the
seed node $s$. As we have discussed in section 1, we aim at maximizing the
number of engaged users by selecting seed nodes. We next define the engagement
gain of SEG.

###### Definition 0.

(Engagement gain)
Given a graph $G=(V,E)$, and a set of seed nodes $\mathcal{S}$, and a new seed
node $v\not\in\mathcal{S}$, the engagement gain $\rho(v,\mathcal{S})$ is the
number of newly engaged users in $\mathcal{K}(v)$, i.e.,
$|\mathcal{K}(v)\setminus\bigcup_{s\in\mathcal{S}}\mathcal{K}(s)|$.

We formally define our objective function named local user engagement
function.

###### Definition 0.

(Local user engagement function $\rho(.)$).
Given a set of seed nodes $\mathcal{S}$, local user engagement function
$\rho(\mathcal{S})$ returns the number of distinct engaged users, namely,
$|\bigcup_{s\in\mathcal{S}}\mathcal{K}_{k,r}(s)|$ .

###### Example 0.

In Figure 3, suppose that $k=2$ and $r=2$. We can check two SEGs :
$\mathcal{K}_{2,2}(b)$ and $\mathcal{K}_{2,2}(f)$. Suppose that a set of seed
nodes $\mathcal{S}=\varnothing$. Notice that $\rho(b,\mathcal{S})=3$ and
$\rho(f,\mathcal{S})=5$. However, when $\mathcal{S}=\\{f\\}$,
$\rho(b,\mathcal{S})$ is changed from $3$ to $2$ because a node $c$ is already
engaged owing to the seed node $d$.

Figure 3. Two SEGs when $k=2$ and $r=2$

###### Property 1.

Given a graph $G=(V,E)$, $k$, and $r$, the SEG of any node $v\in V$ always
belongs to $k$-core and is unique.

###### Proof.

Because SEG is a maximal cohesive subgraph within a distance $r$ from the seed
node $s$, it is unique. When $r=\infty$, the result of any SEG belongs to the
$k$-core because the $k$-core does not require the connectivity constraint of
the resultant subgraphs. ∎

Note that $\mathcal{K}_{k,r}(v)\subseteq N_{r}(v)$. Observe that the union of
all the SEGs in a network is the same as $k$-core. This implies that the
maximum number of engaged users of given networks can be computed in an
efficient way. As discussed in the applications, we are interested in finding
$b$ seed nodes to maximize the number of engaged users. Now we can formulate
our problem. The definition of our LUEM problem is as follows.

###### Problem definition 1.

(Local User Engagement Maximization (LUEM)). Given a graph $G=(V,E)$, positive
integers $b$, $k$, and $r$, the LUEM problem aims to identify $b$ seed nodes,
denoted as $\mathcal{S}$, such that the number of distinct engaged users is
maximized; in other words, maximizing $\rho(\mathcal{S})$ such that
$|\mathcal{S}|\leq b$.

Note that any pair of SEGs can overlap. Next, we present some of the important
properties of the LUEM problem.

###### Property 2.

The local user engagement function $\rho(.)$ is submodular.

###### Proof.

It is known that a function $g$ is submodular if for all $S\subseteq
T\subseteq V$, all $v\in V\setminus T$, $g(S\cup\\{v\\})-g(S)\geq
g(T\cup\\{v\\})-g(T)$ (Schrijver, 2003) . Assume that $S\subseteq T\subseteq
V$ and there is a node $u\in V\setminus T$ which makes
$\rho(S\cup\\{u\\})-\rho(S)<\rho(T\cup\\{u\\})-\rho(T)$ . It implies that
$\rho(u,T)$ is larger than $\rho(u,S)$. However, we know that (1)
$\rho(T)\geq\rho(S)$; and (2) a user engaged by the set of seed nodes $S$ is
always the engaged user by the set of seed nodes $T$. Hence, the number of
engageable users by the node $u$ in $T$ is smaller than or equal to the number
of engageable users by the node $u$ in $S$. Hence, due to $S\subseteq T$,
$\rho(S\cup\\{u\\})-\rho(S)<\rho(T\cup\\{u\\})-\rho(T)$ does not hold. It
implies that our assumption is not true, and our function $\rho(.)$ is
submodular. ∎

###### Property 3.

$\rho(.)$ function is monotone.

###### Proof.

The proof is trivial. For any $S\subseteq T\subseteq V$, $\rho(S)\leq\rho(T)$
always holds. Therefore, $\rho(.)$ is monotone. ∎

###### Theorem 8.

LUEM problem is NP-hard.

###### Proof.

Proof can be checked in B ∎

Comparing with (Sozio and Gionis, 2010). Note that computing SEG is the same
with finding a solution to a community search problem (Sozio and Gionis,
2010). The problem is that : given a graph $G$ and a set of query nodes $Q$,
their model aims to find a connected subgraph while maximizing the minimum
degree such that 1) contains all the query nodes $Q$ and 2) all nodes in the
subgraph are at a distance to $Q$ less than a threshold. Hence, by restricting
$|Q|=1$ and applying a degree constraint, (Sozio and Gionis, 2010) can be
utilized to find the SEG. However, note that finding SEGs is different from
finding a solution for LUEM. When we use a greedy approach to find a solution
for LUEM by utilizing (Sozio and Gionis, 2010), the approach is the same as
our basic algorithm 3.3.

##  3\. Approximation Algorithms

In this section, we introduce approximation algorithms to solve the LUEM
problem. First, we present a framework of the approximation algorithm using
the characteristics of our objective function and present a basic
algorithm(BA). To improve efficiency, we present an effective $r$-neighbor-
based algorithm (ERA) with a pruning strategy.

###  3.1. Computing SEG

input : $G=(V,E)$, user parameters $k$, $r$, seed node $s$

output : SEG $\mathcal{K}_{k,r}(s)$

1 $\mathcal{K}_{k,r}(s)\leftarrow\varnothing$;

2 $D\leftarrow$ $k$-core(_$G[N_{r}(s)]$ , $k$_) ;

3 if  _$D$ contains $s$_ then

4 return connectedComp(_$D$ , $s$_);

5

6 end if

7return null;

Algorithm 1 Computing SEG

In this section, we present how to compute an SEG given a seed node $s$ using
Algorithm 1. Computing an SEG is simple and intuitive. First, we obtain an
induced network of $r$-neighbors from the seed node $s$, then compute the
$k$-core (line 2). Because the $k$-core returns multiple connected components,
we select a connected component that contains the seed node $s$ (line 4). If
there is no connected component that contains seed node $s$ in the $k$-core,
the algorithm returns null (line 5). Hence, computing an SEG requires
$O(|V|+|E|)$, and computing all SEGs in a graph requires $O(|V|(|V|+|E|))$.

Figure 4. Basic algorithm ($b=2,k=2,r=1$)

###  3.2. Framework

input : $G=(V,E)$, $k$, $r$, $b$

output : A set of seed nodes $\mathcal{S}$

1 $\mathcal{S}\leftarrow\varnothing$;

2 for (  _$|\mathcal{S}|\neq b$_ ) $\\{$

3 $s\leftarrow\operatornamewithlimits{argmax}_{v\in V}$ $\rho(v,\mathcal{S})$;

4 $\mathcal{S}\leftarrow$ $\\{s\\}\cup\mathcal{S}$;

5

6 $\\}$

7return $\mathcal{S}$;

Algorithm 2 Algorithmic framework of hill-climbing approach

Algorithm 2 depicts the framework of the $1-\frac{1}{e}$ approximation
algorithm. This framework incorporates a widely used greedy optimization
search named hill-climbing approach (Nemhauser et al., 1978) to find a
solution. It iteratively identifies a seed node that maximizes the number of
engaged users when it merges with the current solution $\mathcal{S}$. Note
that after adding a seed node, the number of engageable users of possible seed
nodes can be decreased or unchanged. Therefore, it is required to check which
seed node has the largest number of disengaged users at every iteration. After
finding $b$ seed nodes, the procedure is terminated.

input : $G=(V,E)$, $k$, $r$, $b$

output : A set of seed nodes $\mathcal{S}$

1 $\mathcal{S}\leftarrow\varnothing$;

2 $D\leftarrow$ $k$-core(_$G$ ,$k$_);

3
$C\leftarrow\\{v_{1}:\mathcal{K}_{k,r}(v_{1}),v_{2}:\mathcal{K}_{k,r}(v_{2}),\ldots,v_{|D|}:\mathcal{K}_{k,r}(v_{|D|})\\}$
;

4 for (  _$|\mathcal{S}|\neq b$_ ) $\\{$

$s\leftarrow\operatornamewithlimits{argmax}_{v\in
C.\text{keys}}\rho(v,\mathcal{S})$ ;

// To compute $\rho$, $\mathcal{K}$ is utilized

5 $\mathcal{S}\leftarrow\\{s\\}\cup\mathcal{S}$;

6

7 $\\}$

8return $\mathcal{S}$;

Algorithm 3 Basic Algorithm

###  3.3. Basic algorithm(BA)

The direct implementation of the Algorithm 2 is the basic algorithm (BA) with
a $1-\frac{1}{e}$ approximation ratio. The procedure of the BA is as follows.

###### Procedure 1.

At the initial stage, it computes all the SEGs (Lines 1-3). Then, until
finding $b$ seed nodes, it iteratively finds a node that can maximize the
number of engaged users. The selected node will be added to the solution
(Lines 4-6). Finally, it returns the selected seed nodes as a result (Line 7).

Figure 5. $er$-neighbors-based pruning ($b=2,k=2,r=1$)

###### Example 0.

In Figure 4, suppose that $k=2,r=1$, and $b=2$. To find a solution, we first
select a node '$f$' because the $\rho(f,S)$ is $4$. Therefore, the nodes
$\\{d,e,f,g\\}$ are engaged. Next, we select a node '$a$', which enables
engaging nodes $\\{a,b,c\\}$. When we find two seed nodes $\\{f,a\\}$, we
terminate the algorithm because $b=2$.

In the following, we briefly demonstrate the $1-1/e$ approximation ratio of
the framework. Please refer to (Nemhauser et al., 1978; Kempe et al., 2003)
for further details on this topic.

Theoretical analysis. We next check the approximability of our proposed
algorithm.

###### Lemma 0.

Let $OPT$ denote an optimal solution. We suppose that there is an identified
solutions $\mathcal{S}$ such that $|\mathcal{S}|<b$. Then the following
inequality always holds.

(1) $\displaystyle\max_{x\in
V}[\rho(\mathcal{S}\cup\\{x\\})-\rho(\mathcal{S})]\geq\frac{1}{b}[\rho(OPT)-\rho(\mathcal{S})]$

###### Proof.

Proof of Lemma 2 can be checked in C ∎

###### Theorem 3.

Algorithm 2 holds $1-\frac{1}{e}$ approximation ratio, i.e.,
$\rho(\mathcal{S})\geq(1-\frac{1}{e})\rho(OPT)$.

###### Proof.

Proof can be checked in D ∎

Time complexity. The basic algorithm takes $O(|V|(|V|+|E|)+b|V|^{2})$. The
time complexity of each component is as follows.

  * •

For initialization, it takes $O(|V|(|V|+|E|))$ to compute all SEGs.

  * •

For each iteration, it is required to compute the set difference $|V|$ times.
Since the set difference takes $O(|V|)$ time complexity, it takes
$O(b|V|^{2})$.

Limitation of BA. We point out three major limitations of BA: (1) Memory
consumption : it requires considerable memory to store all SEGs. It takes
$O(|V|^{2})$ memory space in the worst case. (2) Initialization bottleneck :
it requires computing all SEGs in the initial stage, which requires
$O(|V|(|V|+|E|))$ time complexity. (3) Update bottleneck : at every iteration,
we need to check all SEGs to find the best seed node.

In the following sections, we propose an efficient method to address the above
three issues. Specifically, ERA focuses on resolving the update bottleneck
issue of the BA while preserving its effectiveness. In section 4, we solve
these issues simultaneously without losing accuracy.

###  3.4. Effective $r$-neighbors-based approximation algorithm

In section 3.3, we discuss the characteristics of the $\rho$ function and
approximation ratio of BA. Even if BA is effective (a.k.a. $1-1/e$), it cannot
sufficiently handle large datasets. Therefore, in this section, we propose a
pruning technique called the $r$-neighbors-based pruning strategy to improve
efficiency (update bottleneck) while preserving effectiveness. First, we
define some terminology.

###### Definition 0.

(Effective $r$-neighbor size($er$-neighbors)).
Given a graph $G=(V,E)$, a set of seed nodes $\mathcal{S}^{i}$ at current
iteration $i$, node $v\in V$, minimum degree threshold $k$, and distance
threshold $r$, effective $r$ neighbor size ($er$-neighbors) of $v$, denoted as
$\mathcal{E}_{r}(v)$, is defined as follows.

(2) $\displaystyle\mathcal{E}_{r}(v)=\begin{cases}|N_{r}(v)|&\text{default
value}\\\ \rho(v,S^{j})&\text{if }\rho(v,S^{j})\text{ where $j<i$ is already
computed}\end{cases}$

We can consider that $er$-neighbors implies the number of possible engageable
nodes based on our observation. This $er$-neighbors is helpful to prune a set
of nodes as an upper bound.  For example, at the initial stage, all
$|N_{r}(v)|$ is the same with $er$-neighbors because all nodes in $N_{r}(v)$
can be engaged (without considering the degree constraint). When we compute
$\rho(v,S)$, we update the $er$-neighbors value of node $v$ to keep the recent
value.

Note that at the initial stage, we do not need to compute SEGs of all nodes
because it takes a long time. We only compute the SEG if it is required to be
computed; in other words, we adopt the lazy update manner. Note that
$|\mathcal{E}_{r}(v)|$ is always larger than or equal to $\rho(v,S)$, that is,
it can be an upper bound of $\rho(v,S)$. Thus, we can design the following
pruning strategy.

input : $G=(V,E)$, $k$, $r$, $b$

output : A set of seed nodes $\mathcal{S}$

1 $\mathcal{S}\leftarrow\varnothing$;

2
$H\leftarrow\\{\\{v_{1},|N_{r}(v_{1})|\\},\\{v_{2},|N_{r}(v_{2})|\\},\ldots,\\{v_{|V|},|N_{r}(v_{|V|}|)\\}\\}$;

$H\leftarrow$ sortByValue(_$H$_);

// Sort by $er$-neighbors

3 for (  _$|\mathcal{S}|\neq b$_ ) $\\{$

4 $Cur,\textnormal{{U}}\leftarrow\varnothing$;

5 for (  _$u\in H.keys()$_ ) $\\{$

6 $\mathcal{E}_{r}(u)\leftarrow H.get(u)$ ;

7 if  _$\rho(Cur,\mathcal{S})\geq\mathcal{E}_{r}(u)$_ then

8 break ;

9

10 end if

11 if  _$\rho(Cur,\mathcal{S})$ $<$ $\rho(u,\mathcal{S}$)_ then

12 $Cur\leftarrow u$;

13

14 end if

15 $\mathcal{E}_{r}(u)\leftarrow$ $\rho(u,\mathcal{S})$;

16 $U\leftarrow U\cup\\{u\\}$;

17

18 $\\}$

19 $\mathcal{K}\leftarrow\mathcal{K}\cup Cur$;

20 $H\leftarrow H\setminus Cur$;

Update order $U\setminus\\{Cur\\}$ of $H$ ;

// using binary search

21

22 $\\}$

23return $\mathcal{K}$;

Algorithm 4 Pseudo description of ERA

Instead of computing all SEGs at the beginning of the algorithm, an effective
$r$-neighbors-based pruning iteratively computes a few SEGs that are promising
candidates for selection. The high-level idea is to avoid computing SEGs using
$er$-neighbors because $er$-neighbors of a specific node $v$ is an upper bound
of $\rho(v,S)$. The detailed procedure is described as follows:

###### Procedure 2.

At the initial stage, the nodes are ordered based on $er$-neighbors in
descending order (Lines 1-3), then, we compute SEGs to iteratively obtain the
$\rho$ value (Lines 8-11). Note that we retain the current best node $Cur$,
which has the largest $\rho$ value (Line 11). As a result of checking the
nodes iteratively, if the $er$-neighbors of the current node is less than or
equal to $\rho$ of $Cur$, we return $Cur$ as the selected seed node of our
algorithm (Lines 8-9). After selecting the best node, we update the node order
based on the $er$-neighbors (Line 16). This process is repeated until we
identify $b$ seed nodes (Lines 4-16). Finally, it returns a set of selected
seed nodes as a result (Line 17).

###### Example 0.

Figure 5 depicts the procedure 2. The sample graph consists of seven nodes and
ten edges. We set $b=2$, $k=2$, and $r=1$. First, we initialize
$er$-neighbors. Next, we sort the nodes according to $er$-neighbors. Then, we
iteratively compute SEGs in a descending order of $er$-neighbors. In the case
of node $c$, SEG is $\\{a,b,c\\}$. When we compute SEG of node $f$, it
contains $\\{d,e,f,g\\}$. Because $er$-neighbors of the next node $g$ is $4$,
notice that all $\rho$ values of the nodes to be computed later are less than
$4$. This implies that we do not need to compute SEGs of the other nodes.
Hence, we select the SEG of node $f$ as a solution and delete node $f$ from
the candidate list. Then, we sort the list based on the size of
$er$-neighbors. We repeatedly compute SEGs. Next, we select the SEG of node
$c$. Because the solution size is exactly the same as the number of seed nodes
$b$, we terminate the algorithm.

Note that if the inverted index is maintained to retain the information
regarding which SEG contains a specific node $u$, we can improve the
efficiency. However, This is not preferred, because it requires considerable
memory space.

Before we compute an SEG, we must check whether the SEG has already been
computed or not. If computed, we do not need to recompute it because the SEG
of a node is unique.

Comparing with (Minoux, 1978). In (Minoux, 1978), authors propose an
accelerated greedy algorithm (AGA) to find a solution when the objective
function is submodular. It iteratively maintains the $\Delta(v)$ value by
computing $\rho(v)-\rho(\emptyset),\forall v\in V$ then updates the $\Delta$
value. Note that the high-level idea of AGA and ERA is similar. The two major
differences compared with AGA is as follows: (1) ERA does not directly compute
the value $\rho(v)$ since computing the SEG is time-consuming. Thus, we
utilize $|N_{r}(v)|$ to improve the efficiency since $|N_{r}(v)|$ can be
utilized as an upper bound; (2) For every iteration, SEG utilize binary search
to maintain the sorted values. Thus, it can improve the efficiency to find the
node which has the largest gain.

Time complexity. The time complexity of ERA is the same as that of BA since it
needs to compute all SEGs in the worst case. However, as discussed in section
5, we observe that ERA is much faster than BA in practice.

Figure 6. Degree and the size of SEG in Condmat dataset

##  4\. Fast Circle Algorithm

In section 3, we discuss two algorithms for finding an approximate solution to
the LUEM problem. Despite improving the update bottleneck of BA, ERA
intrinsically suffers from memory consumption and initialization bottlenecks.
Hence, in this section, we present an approach to improve the efficiency of
ERA by improving the abovementioned issues while preserving its effectiveness.
Our FCA algorithm is designed based on the assumption that a node with a large
degree may engage many users. In Figure 6, we present the degree and size of
engageable users when $r=1$ and $k=3$ in the Condmat dataset (Leskovec et al.,
2007). Observe that the degree of a node is correlated with the SEG size. In
FCA, we utilize this characteristic to find a solution for LUEM.

First, we introduce HyperANF (Boldi et al., 2011), which is a technique used
to approximate the neighborhood function. Next, we propose an efficient
algorithm that incorporates HyperANF, called the Fast Circle Algorithm (FCA).

Figure 7. Example of $ANV$ Figure 8. Example of FCA ($b=2$, $k=2$, $r=2$)

###  4.1. HyperANF

HyperANF (Boldi et al., 2011) is a state-of-the-art algorithm to compute an
approximation of the neighborhood function of a graph. It utilizes HyperLogLog
counters (Flajolet et al., 2007) which are statistical counters requiring
$O(\log\log{n})$ bits. Thus, HyperANF can approximate the number of reachable
nodes within a specific distance from a node. Unfortunately, the time
complexity of the HyperANF is unknown but its running time is expected to be
approximately $O((|V|+|E|)h)$, where $h$ denotes the maximum distance. This is
because HyperANF is an extension of ANF (Palmer et al., 2002) that requires
$O((|V|+|E|)h)$.

###  4.2. Algorithm description

By utilizing HyperANF, each node has a set of approximated neighborhood values
($ANV$s) for each distance, that is, given a radius $r$, each node has
$1$-$ANV$, $2$-$ANV$, $\cdots$, $r$-$ANV$. First, we formally define the
approximated neighborhood value ($ANV$) of a node.

###### Definition 0.

(Approximated neighborhood value ($ANV$)).
Given a graph $G$, node $v\in V$, and threshold $r$, the approximated
neighborhood value ($ANV$) is a key-value structure, in which a key is a set
of integers from $1$ to $r$ and a value is an approximated number of neighbors
from node $v$ within a specific distance.

###### Example 0.

We illustrate the ANF value by reusing Figure 3. We assume that $r=3$ and
compute the $ANV$ of node $a$. Figure 7 shows the $ANF$ result of the node
$a$. Note that $ANV$ does not return the exact degree because it is an
approximated value.

The intuition behind FCA is as follows. We focus only on $ANV_{v}^{r}$ to
select the best node. After finding node $u$ in the first iteration, we update
the $ANV^{r}$ values of all nodes. If node $x$ is the $d$-hop neighbor of the
selected node $u$, $ANV_{x}^{r}$ must be updated by negating $ANV_{x}^{r-d}$
because we assume that $ANV_{x}^{r-d}$ nodes are already engaged.

input : $G=(V,E)$, $k$, $r$, $b$

output : A set of seed nodes $\mathcal{S}$

1 $D\leftarrow G[$kcore(_$G$ , $k$_)$]$, $\mathcal{S}\leftarrow\varnothing$;

2 initialize HyperANF on $D$;

3 for (  _$r^{\prime}\leftarrow 1:r$_ ) $\\{$

4 Setup $ANV^{r^{\prime}}$ by computing HyperANF.next(_$r^{\prime}$_);

5

6 $\\}$

7$D\leftarrow$ sortByANV(_$D$_);

8 while  _$|\mathcal{S}|\neq b$_ do

9 $\textnormal{{U}}\leftarrow\varnothing$;

10 $u\leftarrow\operatornamewithlimits{argmax}_{u\in D}$ $ANV_{u}^{r}$;

11 compute $\mathcal{K}_{k,r}(u)$;

12 compute shortest path tree $T(u)$ using $G[\mathcal{K}_{k,r}(u)]$ with root
$u$;

13 $d_{T}\leftarrow$ maxDistance(_$T(u)$_);

14 for (  _$y\in\mathcal{K}_{k,r}(u)$_ ) $\\{$

15 Update the ANV values by Strategy;

16 U.add(_$y$_);

17

18 $\\}$

19 $D$.remove(_$u$_);

20 $\mathcal{S}\leftarrow$ $\mathcal{S}\cup\\{u\\}$;

21 update nodes U in $D$;

22

23 end while

24return $\mathcal{S}$;

Algorithm 5 Procedure of FCA

###### Procedure 3.

At the initial stage, given a distance threshold $r$, a set of $ANV$s
($ANV^{1}$ $\cdots$ $ANV^{r}$) for every node based on HyperANF is computed
(Lines 1-4). Then, node $u$ that has the largest $ANV_{u}^{r}$ value is
selected (Line 8). Intuitively, node $u$ have many $r$-neighbor nodes. Next,
we compute SEG $\mathcal{K}(u)$ and the shortest distances from node $u$;
then, construct a shortest-path tree based on the shortest path (Lines 8-10).
Next, if node $v$ is in the $i$-th level of the shortest-path tree of
$\mathcal{K}(u)$ owing to rooting node $u$, we obtain $ANV_{v}^{r-i}$. Then,
the $ANV$ values are updated as follows (Lines 11-14).

  * •

$ANV_{v}^{r^{\prime}}=ANV_{v}^{r^{\prime}}-ANV_{v}^{r-i},\forall r\geq
r^{\prime}>r-i$

  * •

$ANV_{v}^{r^{\prime\prime}}=0,\forall r^{\prime\prime}\leq r-i$

This process is repeated for all nodes in $\mathcal{K}_{k,r}(u)$. After
updating $ANV$ value of a node, we relocate the position of the node to
preserve the order in $D$ (Line 17). This procedure is repeated until the size
of the solution is $b$.

###### Example 0.

In Figure 8, we give an example of FCA. Suppose that $b=2$, $r=2$, and $k=2$.
At the initial stage, we compute $ANV$s of all nodes. In the Figure, the
numbers indicate the $ANV^{r}$ values of the nodes. Next, we choose the node
that has the largest $ANV^{r}$ value. We choose a blue-coloured node in the
first iteration. After choosing the node, we update the $ANV^{r}$ values of
its neighbor nodes based on the procedure 3. Among the updated $ANV^{r}$
values, we choose the green-coloured node that has the largest $ANV^{r}$
value. Then, we choose two blue and green nodes as the seed nodes.
Consequently, the algorithm is terminated. Note that thirteen users are
completely engaged.

Time complexity. FCA takes $O(H+br|V|+b(|V|+|E|\log{|V|}))$. Time complexity
of each component is as follows.

  * •

Computing $b$ SEG takes $O(b(|V|+|E|))$

  * •

Computing HyperANF111Note that the time complexity of HyperANF is unclear (See
section 4.1) takes $O(H)$

  * •

Updating $ANV^{r}$ takes $O(br|V|)$

  * •

Computing the shortest path $O(b(|V|+|E|\log{|V|}))$

##  5\. Experiments

We evaluated the proposed algorithms using several real-world networks. All
experiments were conducted on Ubuntu 14.04 with 64GB memory and 2.50GHz Xeon
CPU E5-4627 v4. For the implementation, we used the JgraphT library (Michail
et al., 2020) and WebGraph (Boldi and Vigna, 2004). Our code is publicly
available 222https://bit.ly/3GyC8wl .  Since the datasets are publicly
available, we do not have any preprocessing.

Dataset. Table 2 lists the basic statistics of real-world datasets. All
datasets are publicly available. $c^{max}$ and $d^{avg}$ denote the maximum
core index and average degree, respectively.

Table 2. Summary of the real-world datasets Name | # nodes | # edges | $c^{max}$ | $d^{avg}$
---|---|---|---|---
Amazon(Yang and Leskovec, 2015) | 334,863 | 925,872 | 6 | 5.52
Brightkite(Cho et al., 2011) | 58,228 | 214,078 | 52 | 7.35
CondMat(Leskovec et al., 2007) | 23,133 | 93,497 | 25 | 8.08
DBLP(Yang and Leskovec, 2015) | 317,080 | 1,049,866 | 113 | 6.62
Enron(Yang and Leskovec, 2015) | 36,692 | 183,831 | 43 | 10.02
Hepth(Leskovec et al., 2007) | 9,877 | 25,998 | 31 | 5.26
LA(Bao et al., 2012; Wei et al., 2012) | 500,597 | 1,462,501 | 120 | 5.84
NYC(Bao et al., 2012; Wei et al., 2012) | 715,605 | 2,552,603 | 157 | 7.13
Orkut(Yang and Leskovec, 2015) | 3,072,441 | 117,185,083 | 253 | 76.28
Youtube(Yang and Leskovec, 2015) | 1,134,890 | 2,987,624 | 51 | 5.27

Algorithms. As baseline algorithms, we used two graph centrality-based
approaches333In Table 4, we show several centrality measures and notice that
AC and CC are relatively scalable to handle large-sized datasets. Hence, we
choose both centrality measures as the baseline algorithms., named AC(alpha
centrality), and CC(clustering-coefficient). Both approaches compute the
centrality measures; then, iteratively pick the node that has the largest
centrality until $b$ seed nodes are identified. If SEG of a selected node is
null, the node is not selected. Owing to limited scalability, we only report
the results of BA in the scalability test.

  * •

Basic algorithm (BA)

  * •

Effective $r$-neighbors-based approximation algorithm (ERA)

  * •

Fast Circle Algorithm (FCA)

  * •

Alpha Centrality-based approach (AC)

  * •

Clustering Coefficient-based approach (CC)

Parameter setting. In our experiments, we vary the values of three parameters
$k$, $r$, and $b$. In all the experiments, we use values $r\in[2,3]$ since the
larger values are not interesting since when $r$ becomes large, all the nodes
are reachable from the seed nodes. We fix the value $b=10$ since the larger
values may cover all the possible nodes (See Figure 10). For the value $k$, it
controlled the cohesiveness level. To the best of our knowledge, many previous
works on minimum-degree based cohesive subgraph discovery (Kim et al., 2020;
Barbieri et al., 2015; Fang et al., 2017, 2016) take the minimum degree as an
input parameter and did not shed light on strategies for setting its value.
Intuitively, when a user selects a large value $k$, we expect the SEG might be
more cohesive and smaller. Thus, we consider the value $k$ an additional
degree of freedom available to users to specify the cohesiveness, and users
can compare results with different parameters.

(a) Effectiveness test

(b) Efficiency test (same legend with Figure 9(a))

Figure 9. Real-world networks

Effectiveness and efficiency evaluation in real-world networks. Figures 9(a)
and 9(b) show effectiveness and efficient of the proposed algorithms on tests
conducted using real-world datasets, respectively. Each column indicates
different datasets and each row indicates different $r$ values. Each Figure
reports the number of engaged users and running time with respect to varying
$k$ values. For all experiments, we set $b=10$. The effectiveness is verified
in Figure 9(a). Observe that for all cases, ERA algorithm returns the largest
number of engaged users, and FCA returns comparable effective results. The two
baseline algorithms return relatively low-quality results. In Figure 9(b), we
check the efficiency. Note that for large-sized datasets, such as LA, NYC,
Orkut, and Youtube datasets with $r\geq 2$, ERA algorithm does not finish
within 24 hours. Therefore, we did not report these results. We observed that
our FCA outperformed the two baseline algorithms for all datasets. Next, we
verified the efficiency of these algorithms. We observed that the proposed FCA
algorithm is much faster than the two baseline algorithms because it does not
need to compute many SEGs.

Measuring node influence. In this experiment, we use the Polbooks network
(Rossi and Ahmed, 2015) to verify the quality of our seed nodes using node
influence measures. The Polbooks network is a well-known network with $105$
nodes and $441$ edges. The nodes and edges represent blogs on U.S. politics
and web links, respectively. Because measuring the influence is time
consuming, we used a small graph to check the tendency. In the experiments, we
set $k=3$, $r=2$, and $b=3$. In addition, we used five measures to check the
influence (Salavaty et al., 2020): (1) ClusterRank (Chen et al., 2013) : It is
a local ranking measure that considers not only the number of neighbor nodes
and the neighbors’ influences but also the clustering coefficient. (2) Hubness
centrality (Salavaty et al., 2020) : It reflects the power of each node in its
surrounding environment. (3) IVI score (Salavaty et al., 2020) : IVI method is
an integrative measure for determining influence nodes. (4) SIRIR (Salavaty et
al., 2020) : It is an SIR-based influence ranking method that combines the
leave-one-out cross-validation with a conventional susceptible-infected-
recovered model. (5) Spreading score (Salavaty et al., 2020) : It is
indicative of the spreading potential.

Table 3. Node influence Measures | Mean of all nodes | ERA | FCA
---|---|---|---
clusterRank | 48.0829 | 63.7308 | 63.7195
hubness | 28.5478 | 58.3913 | 56.9565
IVI | 12.6734 | 40.4316 | 60.693
SIRIR | 1.4515 | 2.224 | 3.139
Spreading score | 19.2765 | 48.6802 | 76.9068

Table 3 reports the experimental results. Observe that our identified seed
nodes have larger influence scores than the average influence score of the
nodes for all metrics. This indicates that the seed nodes play an important
role in the graph structure. In addition, because FCA returns high influence
scores, large $r$-neighbors is preferred when identifying influential nodes in
networks.

Table 4. Centrality score Algorithm | Mean of all nodes | ERA | FCA
---|---|---|---
AC | 1.096 | 1.1739 | 1.171
BC | 104.2912 | 332.9455 | 488.5373
CC | 0.4902 | 0.3479 | 0.3283
Close | 0.3329 | 0.3716 | 0.407
CN | 4.9702 | 6 | 6
IM | 3.1193 | 5 | 5
HC | 0.4015 | 0.4671 | 0.4888

Graph centrality. In this experiment, we reused the Polbooks network to verify
the centrality score444Graph centrality is to measure the important nodes (or
edges) in a graph. of our seed nodes. Because our selected seed nodes might be
located at the center of the core structure in a graph, we assume that the
seed nodes might have a high centrality score. We checked the alpha centrality
(AC) (Bonacich and Lloyd, 2001), betweenness centrality(BC) (Brandes, 2001),
clustering coefficient (CC), closeness centrality (Close) (Bavelas, 1950),
coreness (CN) (Matula and Beck, 1983), influence maximization (IM) (Kempe et
al., 2003), and harmonic centrality (HC) (Newman, 2003; Rochat, 2009). Table 4
reports the results of the centrality scores of our ERA and FCA algorithms and
the average centrality scores of the nodes. Observe that ERA has a larger
value than the average centrality score. Moreover, CC only focuses on the
local graph structure, and our seed nodes have relatively small scores.

Table 5. The number of engaged users Algs | AC | BC | CC | Close | CN | HC | IM | ERA | FCA
---|---|---|---|---|---|---|---|---|---
$\rho(.)$ | 56 | 78 | 31 | 73 | 49 | 56 | 26 | 103 | 102

In Table 5, we verify the number of engaged users when a set of nodes are
selected based on centrality measures. Observe that our ERA and FCA algorithms
outperform the other algorithms because they aim to maximize the number of
engaged users. This indicates that maximizing the number of engaged users
cannot be achieved by identifying classic node importance measures.

Figure 10. Varying parameter $b$

Effect on $b$. To verify the effect on parameter $b$, we used the Brightkite
dataset by setting $k=3,b=2$ and $r=2$, and reported the number of distinctly
engaged users. In Figure 10, when $b$ value becomes relatively large, the
difference between ERA and FCA algorithms increases. However, when $b$ value
becomes very large (e.g., $5120$), the difference is negligible because most
nodes are already engaged. Furthermore, we also observe that $AC$ and $CC$
return relatively few engaged users because the larger centrality scores do
not indicate a larger number of engaged users.

Figure 11. Scalability test on synthetic networks

(a) First SEG

(b) Second SEG

(c) Third SEG

Figure 12. Result of LUEM in the word-association network ($k=3,r=2,b=3$)

Scalability test. Figure 11 demonstrate the efficiency of our algorithms with
respect to a varying number of nodes in the LFR synthetic networks
(Lancichinetti et al., 2008) to present scalability. Notice that the running
time of ERA increases significantly when the number of nodes increases.
Moreover, observe that the running time of FCA is much faster than that of ERA
and increases almost linearly with node size.

Case study : Word-association network Figure 12 depicts the three resultant
SEGs in the word-association network (Nelson et al., 2004). The word-
association network consists of $10,617$ nodes and $72,168$ edges. Each node
indicates an English word, and each edge indicates the association between two
nodes. Please refer. To avoid meaningless association, we retain the edges if
the edge weight (occurrence) is greater than or equal to $10$. By utilizing
LUEM with $b=3$, we identified three seed nodes: Water, Food, and Money. We
deduced that the three seed nodes are keywords that represent high-level
concepts (topic) to explain the words. For example, in the first SEG, many
keywords such as Coast, Leak, Sink, Wet, Port, Gas, Vapor, Pump, and Puddle
are related to the seed node Water. In the second SEG, we noticed that most of
the keywords, such as Rib, Bread, Pizza, Pastry, Chips, and Spaghetti are
related to the keyword Food. Notice that each SEG is a cluster of similar
keywords.

Figure 13. DBLP result when $k=3$

Case study : DBLP. We use DBLP dataset (Kim et al., 2014) for our case study.
We generate a co-authorship network where an edge of two authors is generated
if they publish at least $3$ papers together. We set $k=3$ and $r=2$. Figure
13 shows the result of the case study. We notice that the author $1621$ is the
center of SEG and all the nodes are reachable from $1621$ within $2$ hops. We
observe that there are two major sub-communities : (1) two research groups of
Academy; (2) a research group of an institute.

Figure 14. Community search experiment

Case study : Community Search. In this experiment, we demonstrate the results
when our LUEM approach is utilized on the community search problem (Sozio and
Gionis, 2010; Fang et al., 2020). We use three representative community search
models as baseline algorithms :  the $k$-core model (Sozio and Gionis, 2010),
$k$-truss model (Huang et al., 2014), and $k$-ecc model (Chang et al., 2015)
among many community search models (Barbieri et al., 2015; Huang et al., 2014;
Kim et al., 2022b; Wu et al., 2015b; Huang et al., 2015) since the
implementation of the algorithms is publicly available (Fang et al., 2020).
To verify the accuracy, we use two representative metrics for the community
detection problem: NMI(Normalized Mutual Information) (Danon et al., 2005) and
ARI(Adjusted Rand Index) (Hubert and Arabie, 1985). Because both measures are
designed to identify the best partitions (communities), we consider the
community search problem as a binary classification problem to utilize both
measures. We use three datasets (Amazon, DBLP, and Youtube (Yang and Leskovec,
2015)) that are reported in Table 2, which have ground-truth communities.
Because the ground-truth communities overlap, we compare the identified
community with all ground-truth communities containing the query node; then,
select the best accuracy value. For each experiment, we randomly picked $10$
query nodes, set $k=3$ and $r=1$, and reported the average and standard
deviation. Figure 14 reports the results of LUEM and two baseline algorithms.
Observe that in the Amazon dataset, our model returns a better result than
that of the $k$-core model and a result comparable to that of the $k$-truss
model. In DBLP and Youtube datasets, observe that our model achieves better
accuracy than those of the $k$-core, $k$-truss, and $k$-ecc models. This is
because the size of ground-truth communities is relatively small and they
normally have a small diameter.

Figure 15. Diameter distribution

Figure 15 depicts the diameter distribution of ground-truth communities in the
DBLP and Youtube datasets. Notice that approximately 80% of communities in
DBLP dataset and 95% of communities in Youtube had a diameter of less than or
equal to 5. Because our community model is a minimum-degree with a diameter-
bounded community model, we can obtain a better accuracy score if the size of
the ground-truth communities are very small.

##  6\. Related Work

###  6.1. Influence maximization

The influence maximization (IM) problem (Li et al., 2018), which is a key
problem in social network analysis, has recently gained much attention owing
to its potential value. Given a graph $G=(V,E)$, the influence maximization
problem aims to find a set of $k$ seed nodes while maximizing the expected
number of users influenced by the seed nodes. A representative application of
IM is viral marketing (Chen et al., 2010; Huang et al., 2019). Kempe et al.
(Kempe et al., 2003) first modeled the influence maximization problem for two
fundamental information diffusion models: (1) an independent cascade model and
(2) a linear threshold model. Most existing IM problems can be solved by
applying the greedy hill-climbing algorithm. Because the objective function of
the IM problem is non-negative monotone submodular, if the best node to
maximize the number of expected influenced users are chosen, a $1-\frac{1}{e}$
approximation ratio is achieved.

###  6.2. Anchored and collapsed $k$-core

The anchored $k$-core problem was first proposed by Bhawalkar et al.
(Bhawalkar et al., 2012). Given a graph $G$, integer $k$, and budget $b$, the
anchored $k$-core problem involves identifying $b$ anchor nodes to maximize
the number of engaged users. Note that $b$ anchor nodes are fixed to be
engaged, even if they do not have sufficient neighbor nodes to be engaged. In
(Bhawalkar et al., 2012), the authors showed that when $k=2$, polynomial-time
algorithms could be designed. When $k\geq 3$, the inapproximability results
were proved. Zhang et al. (Zhang et al., 2017c) proposed the OLAK algorithm
for the anchored $k$-core problem. They proposed an onion layer structure to
significantly reduce the search space for this problem. They also proposed
early termination and pruning techniques to improve efficiency. Linghu et
al.(Linghu et al., 2020) proposed an anchored coreness problem. Instead of
maximizing the number of engaged users, they focused on the coreness gain by
anchoring the $b$ nodes. They presented that the anchored coreness problem was
also NP-hard and proposed a pruning search space technique and method to reuse
the intermediate results to improve efficiency. Cai et al. (Cai et al., 2020)
proposed an attributed community engagement problem that considers the
attributes of users and community cohesiveness. They aimed to identify $l$
anchored users that can induce a maximal expanded community, namely, Anchored
Vertex set Exploration (AVE) problem. They demonstrated that, when $k\geq 3$,
the AVE problem was NP-hard. To solve this problem, they proposed the filter-
verify algorithm with early termination and pruning techniques. In (Laishram
et al., 2020), the authors proposed residual core maximization, an algorithm
for the anchored $k$-core problem. They selected anchored nodes based on two
strategies: residual degree and anchor score. Moreover, they showed that the
result is close to the optimal solution.

The collapsed $k$-core problem is firstly proposed by Zhang et al. (Zhang et
al., 2017a). They focused on the problem of finding $b$ collapsers to minimize
the number of engaged users in a social network when removing $b$ collapsers.
The identified $b$ anchor nodes can be considered as important users for
maintaining their engagement in a network. Luo et al. (Luo et al., 2021)
proved that when $k\geq 3$, the collapsed $k$-core problem was W[P] hard.
Zhang et al. (Zhang et al., 2018a) introduced a collapsed $k$-truss problem.

###  6.3. $k$-core Decomposition and Its Variation

The $k$-core is widely used for finding cohesive subgraphs in a graph. The
definition of the $k$-core (Seidman, 1983) is as follows. Given a graph
$G=(V,E)$ and integer $k$, the $k$-core, denoted by $D_{k}$, is a set of nodes
of which every node has at least $k$ neighbor nodes in $D_{k}$. This $k$-core
is unique and has containment relationship, i.e., $D_{k}\subseteq D_{k-1}$
when $k-1\geq 1$. The core index of a node is $k$ if it belongs to the
$k$-core but not to $(k+1)$-core. Note that $k$-core is a set of nodes of
which its core index is larger than or equal to $k$. Batagelj et al. (Batagelj
and Zaversnik, 2003) propose an exact and efficient algorithm to find the core
index. Sariyuce et al. (Sarıyüce et al., 2016) focuses on incremental $k$-core
problem in a dynamic graph. Bonchi et al. (Bonchi et al., 2019) formulate
distance-generalized $k$-core named $(k,h)$-core. Zhang et al. (Zhang et al.,
2020) formulate $(k,p)$-core by considering the degree ratio in $k$-core.
Zhang et al. (Zhang et al., 2018b) formulate $(k,s)$-core by unifying
$k$-truss and $k$-core. There are several variations of $k$-core in signed
networks (Giatsidis et al., 2014), directed networks (Giatsidis et al., 2013),
weighted graph (Eidsaa and Almaas, 2013; Galimberti et al., 2017), temporal
graph (Wu et al., 2015a), multi-layer graph (Galimberti et al., 2017),
bipartite graph (Ding et al., 2017), and uncertain graph (Bonchi et al.,
2014). To get more details, please refer to this nice survey paper (Malliaros
et al., 2020).

##  7\. Conclusion

In this study, we formulate a novel problem called Local User Engagement
Maximization (LUEM) by integrating the local user engagement with graph
distance. We prove that the LUEM problem is NP-hard and its objective function
is monotonic submodular. To solve this problem, we propose two approximation
algorithms and an efficient heuristic algorithm that preserves effectiveness.
To demonstrate the superiority of our algorithms, we conducted extensive
experiments using real-world and synthetic networks. As a future research
direction, we will consider a dynamic environment to find $b$ seed nodes. For
example, the graph can be changed dynamically, or the end user may change the
parameters online.

##  Appendix A Efficiency and effectiveness test when $r=1$

Figure 16. $r=1$

Figure 16 shows effectiveness and efficiency results for $r=1$. Observe that
the results have trends similar to those shown in Figures 9(a) and Figures
9(b). One remarkable difference is that our FCA is slightly slower than the
baseline algorithms because it requires some initialization steps for
approximation. When $r\geq 2$, the initialization time is not significantly
affected.

Figure 17. Reduction procedure

##  Appendix B Proof of Theorem 8

To show the NP-hard of a specific problem, it is required to show an example
of an NP-hard problem that can be reduced to the problem that we want to
verify the hardness. To show the hardness of LUEM problem, we utilize the set-
cover problem (Bernhard and Vygen, 2008). The set-cover problem is defined as
follows: given a set of elements $U=\\{u_{1},u_{2},\cdots,u_{y}\\}$, $z$
subsets $X=\\{X_{1},X_{2},\cdots X_{z}\\}$ of $U$, a set of assignments
$E_{1}$ from $X$ to $U$ where $X_{i}\in X$ contains the element $u_{j}\in U$,
and a parameter $b^{\prime}>0$, it returns YES if there exists a set of
$b^{\prime}$ subsets whose union is the same with $U$. Otherwise, it returns
NO. To present a reduction, we suppose that we have a solution of LUEM. Next,
we start with an arbitrary instance of the set-cover problem, and show that
our LUEM problem can be utilized to solve the set-cover problem. Let suppose
that we have an instance of the set-cover problem
$I_{SC}=(X,U,E_{1},b^{\prime})$. By utilizing the instance $I_{SC}$, we can
construct a new instance $I_{\textsf{LUEM}}$. $I_{\textsf{LUEM}}$ contains
three key elements: (1) $V_{1}^{\prime}$ is the same with $X$; (2)
$V_{2}^{\prime}$ is the same with $U$; and (3) $V_{3}^{\prime}$ is $z$ sets of
$(y+z)$ entities. A subset $X_{j}$ is connected to the element $i$ if $X_{j}$
contains the element $i$. We denote this relationship as $E_{1}$. A subset
$X_{j}$ is connected to the $j$-th $(y+z)$ entities in $V_{3}^{\prime}$. We
set $b=b^{\prime}$, $k=1$, and $r=1$. The newly generated instance and graph
$G^{\prime}$ can be checked in Figure 17.

For every entity in $V_{2}^{\prime}$, it can have at most $z$ degree since the
number of entities in $V_{1}^{\prime}$ is $z$. All the entities in
$V_{3}^{\prime}$ has exactly one neighbor entity in $V_{1}^{\prime}$.
Interestingly, a node in $V_{1}^{\prime}$ has at least $z+y$ degree since it
is connected to the nodes in $V_{3}^{\prime}$. Since $k=1$ and $r=1$, the size
of SEG of node $v$ is the size of the ego-network of node $v$ in $G^{\prime}$.

##  Appendix C Proof of Lemma 2

We denote $OPT\setminus\mathcal{S}=\\{v_{1},v_{2},\ldots,v_{l}\\}$ where
$l\leq b$. We then easily notice that

$\displaystyle\rho$ $\displaystyle(OPT)\leq\rho(OPT\cup\mathcal{S})$
$\displaystyle=\rho(\mathcal{S})+\sum_{j=1}^{l}[\rho(\mathcal{S}\cup\\{v_{1},\ldots,v_{j}\\})-\rho(\mathcal{S}\cup\\{v_{1},\ldots,v_{j-1}\\})]$
(3)
$\displaystyle\leq\rho(\mathcal{S})+\sum_{j=1}^{l}[\rho(\mathcal{S}\cup\\{v_{j}\\})-\rho(\mathcal{S})]$
$\displaystyle\leq\rho(\mathcal{S})+\sum_{j=1}^{l}\max_{x\in
V}[\rho(\mathcal{S}\cup\\{x\\})-\rho(\mathcal{S})]$
$\displaystyle\leq\rho(\mathcal{S})+b\max_{x\in
V}[\rho(\mathcal{S}\cup\\{x\\})-\rho(\mathcal{S})]$

It indicates that the following inequality holds.

(4) $\displaystyle\begin{aligned} &\rho(OPT)\leq\rho(\mathcal{S})+b\max_{x\in
V}[\rho(\mathcal{S}\cup\\{x\\})-\rho(\mathcal{S})]\\\
&\frac{1}{b}(\rho(OPT)-\rho(\mathcal{S}))\leq\max_{x\in
V}[\rho(\mathcal{S}\cup\\{x\\})-\rho(\mathcal{S})]\end{aligned}$

Hence, our Lemma 2 holds.

##  Appendix D Proof of Theorem 3

Let denote $\mathcal{K}^{i}$ as the solution of our algorithm at the end of
the iteration $i\leq b$. Then, we reuse the Lemma 2.

$\displaystyle\rho(\mathcal{K}^{i})$
$\displaystyle-\rho(\mathcal{K}^{i-1})\geq\frac{1}{b}(\rho(OPT)-\rho(\mathcal{K}^{i-1}))$
$\displaystyle\rho(\mathcal{K}^{i})$
$\displaystyle-\rho(\mathcal{K}^{i-1})\geq\frac{1}{b}\rho(OPT)-\frac{1}{b}\rho(\mathcal{K}^{i-1})$
(5) $\displaystyle\rho(\mathcal{K}^{i})$
$\displaystyle\geq\frac{1}{b}\rho(OPT)+(1-\frac{1}{b})\rho(\mathcal{K}^{i-1})$
$\displaystyle\geq\frac{1}{b}\rho(OPT)+(1-\frac{1}{b})[\frac{1}{b}\rho(OPT)+(1-\frac{1}{b})\rho(\mathcal{K}^{i-2})]$
(6)
$\displaystyle\geq\dfrac{1-(1-\frac{1}{b})^{b}}{b(1-(1-\frac{1}{b}))}\rho(OPT)=[1-(1-\frac{1}{b})^{b}]\rho(OPT)$
$\displaystyle\geq(1-\frac{1}{e})\rho(OPT)$

Therefore, we notice that $\rho(\mathcal{K}^{i})\geq(1-\frac{1}{e})\rho(OPT)$.

In $G^{\prime}$, we can find a solution of LUEM with $b=b^{\prime}$, $k=1$,
and $r=1$. To find a solution, we must choose the nodes in $V_{1}^{\prime}$
since it can make at least $1+y+z$ nodes to be engaged as we discussed. Thus,
if we find a solution of LUEM in $G^{\prime}$ and it covers all the nodes in
$V_{2}^{\prime}$, we can solve the set-cover problem with parameter
$b^{\prime}$. Hence, LUEM problem is NP-hard.

## References

  * (1)
  * Backstrom et al. (2012) Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. 2012.  Four degrees of separation. In _WebSci_. 33–42.
  * Bao et al. (2012) Jie Bao, Yu Zheng, and Mohamed F Mokbel. 2012.  Location-based and preference-aware recommendation using sparse geo-social networking data. In _SIGSPATIAL_. ACM, New York, NY, USA, 199–208.
  * Barabási and Albert (1999) Albert-László Barabási and Réka Albert. 1999.  Emergence of scaling in random networks.  _science_ 286, 5439 (1999), 509–512.
  * Barbieri et al. (2015) Nicola Barbieri, Francesco Bonchi, Edoardo Galimberti, and Francesco Gullo. 2015.  Efficient and effective community search.  _Data mining and knowledge discovery_ 29, 5 (2015), 1406–1433.
  * Batagelj and Zaversnik (2003) Vladimir Batagelj and Matjaz Zaversnik. 2003.  An O (m) algorithm for cores decomposition of networks.  _arXiv preprint cs/0310049_ (2003).
  * Bavelas (1950) Alex Bavelas. 1950\.  Communication patterns in task-oriented groups.  _The journal of the acoustical society of America_ 22, 6 (1950), 725–730.
  * Bernhard and Vygen (2008) KORTE Bernhard and JENS Vygen. 2008.  Combinatorial optimization: Theory and algorithms.  _Springer, Third Edition, 2005._ (2008).
  * Bhawalkar et al. (2012) Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. 2012.  Preventing unraveling in social networks: the anchored k-core problem. In _ICALP_. 440–451.
  * Bhawalkar et al. (2015) Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. 2015.  Preventing unraveling in social networks: the anchored k-core problem.  _SIDMA_ 29, 3 (2015), 1452–1475.
  * Boldi et al. (2011) Paolo Boldi, Marco Rosa, and Sebastiano Vigna. 2011.  HyperANF: Approximating the neighbourhood function of very large graphs on a budget. In _WWW_. 625–634.
  * Boldi and Vigna (2004) Paolo Boldi and Sebastiano Vigna. 2004.  The webgraph framework I: compression techniques. In _WWW_. 595–602.
  * Bonacich (1987) Phillip Bonacich. 1987\.  Power and centrality: A family of measures.  _American journal of sociology_ 92, 5 (1987), 1170–1182.
  * Bonacich and Lloyd (2001) Phillip Bonacich and Paulette Lloyd. 2001.  Eigenvector-like measures of centrality for asymmetric relations.  _Social networks_ 23, 3 (2001), 191–201.
  * Bonchi et al. (2014) Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. 2014.  Core decomposition of uncertain graphs. In _SIGKDD_. 1316–1325.
  * Bonchi et al. (2019) Francesco Bonchi, Arijit Khan, and Lorenzo Severini. 2019\.  Distance-generalized core decomposition. In _SIGMOD_. 1006–1023.
  * Borgatti and Everett (2006) Stephen P Borgatti and Martin G Everett. 2006.  A graph-theoretic perspective on centrality.  _Social networks_ 28, 4 (2006), 466–484.
  * Brandes (2001) Ulrik Brandes. 2001\.  A faster algorithm for betweenness centrality.  _Journal of mathematical sociology_ 25, 2 (2001), 163–177.
  * Cai et al. (2020) Taotao Cai, Jianxin Li, Nur Al Hasan Haldar, Ajmal Mian, John Yearwood, and Timos Sellis. 2020\.  Anchored Vertex Exploration for Community Engagement in Social Networks. In _ICDE_. IEEE, 409–420.
  * Chang et al. (2015) Lijun Chang, Xuemin Lin, Lu Qin, Jeffrey Xu Yu, and Wenjie Zhang. 2015.  Index-based optimal algorithms for computing steiner components with maximum connectivity. In _SIGMOD_. 459–474.
  * Chen et al. (2013) Duan-Bing Chen, Hui Gao, Linyuan Lü, and Tao Zhou. 2013\.  Identifying influential nodes in large-scale directed networks: the role of clustering.  _PloS one_ 8, 10 (2013), e77455.
  * Chen et al. (2010) Wei Chen, Chi Wang, and Yajun Wang. 2010.  Scalable influence maximization for prevalent viral marketing in large-scale social networks. In _SIGKDD_. 1029–1038.
  * Chitnis et al. (2013) Rajesh Chitnis, Fedor Fomin, and Petr Golovach. 2013\.  Preventing unraveling in social networks gets harder. In _AAAI_ (Bellevue, Washington) _(AAAI’13)_. AAAI Press, 1085–1091.
  * Cho et al. (2011) Eunjoon Cho, Seth A Myers, and Jure Leskovec. 2011\.  Friendship and mobility: user movement in location-based social networks. In _SIGKDD_. ACM, ACM, New York, NY, USA, 1082–1090.
  * Cohen (2008) Jonathan Cohen. 2008\.  Trusses: Cohesive subgraphs for social network analysis.  _National security agency technical report_ 16, 3.1 (2008).
  * Danon et al. (2005) Leon Danon, Albert Diaz-Guilera, Jordi Duch, and Alex Arenas. 2005.  Comparing community structure identification.  _Journal of statistical mechanics: Theory and experiment_ 2005, 09 (2005), P09008.
  * De Meo et al. (2012) Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, and Angela Ricciardello. 2012.  A novel measure of edge centrality in social networks.  _Knowledge-based systems_ 30 (2012), 136–150.
  * Ding et al. (2017) Danhao Ding, Hui Li, Zhipeng Huang, and Nikos Mamoulis. 2017\.  Efficient fault-tolerant group recommendation using alpha-beta-core. In _CIKM_. 2047–2050.
  * Eidsaa and Almaas (2013) Marius Eidsaa and Eivind Almaas. 2013.  S-core network decomposition: A generalization of k-core analysis to weighted networks.  _PRE_ 88, 6 (2013), 062819.
  * Fang et al. (2017) Yixiang Fang, Reynold Cheng, Xiaodong Li, Siqiang Luo, and Jiafeng Hu. 2017.  Effective community search over large spatial graphs.  _Proceedings of the VLDB Endowment_ 10, 6 (2017), 709–720.
  * Fang et al. (2016) Yixiang Fang, Reynold Cheng, Siqiang Luo, and Jiafeng Hu. 2016\.  Effective community search for large attributed graphs.  _Proceedings of the VLDB Endowment_ 9, 12 (2016), 1233–1244.
  * Fang et al. (2020) Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, and Xuemin Lin. 2020.  A survey of community search over big graphs.  _VLDBJ_ 29, 1 (2020), 353–392.
  * Flajolet et al. (2007) Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. 2007.  Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In _DMTCS_. Discrete Mathematics and Theoretical Computer Science, 137–156.
  * Galimberti et al. (2017) Edoardo Galimberti, Francesco Bonchi, and Francesco Gullo. 2017\.  Core decomposition and densest subgraph in multilayer networks. In _CIKM_. 1807–1816.
  * Ghafouri et al. (2020) Maryam Ghafouri, Kai Wang, Fan Zhang, Ying Zhang, and Xuemin Lin. 2020.  Efficient graph hierarchical decomposition with user engagement and tie strength. In _DASFAA_. Springer, 448–465.
  * Giatsidis et al. (2014) Christos Giatsidis, Bogdan Cautis, Silviu Maniu, Dimitrios M Thilikos, and Michalis Vazirgiannis. 2014\.  Quantifying trust dynamics in signed graphs, the S-Cores approach. In _SDM_. SIAM, 668–676.
  * Giatsidis et al. (2013) Christos Giatsidis, Dimitrios M Thilikos, and Michalis Vazirgiannis. 2013.  D-cores: measuring collaboration of directed graphs based on degeneracy.  _KAIS_ 35, 2 (2013), 311–343.
  * Huang et al. (2019) Huimin Huang, Hong Shen, Zaiqiao Meng, Huajian Chang, and Huaiwen He. 2019.  Community-based influence maximization for viral marketing.  _Applied Intelligence_ 49, 6 (2019), 2137–2150.
  * Huang et al. (2014) Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu. 2014.  Querying k-truss community in large and dynamic graphs. In _SIGMOD_. 1311–1322.
  * Huang et al. (2015) Xin Huang, Laks V. S. Lakshmanan, Jeffrey Xu Yu, and Hong Cheng. 2015.  Approximate Closest Community Search in Networks.  _PVLDB_ 9, 4 (dec 2015), 276–287.
  * Hubert and Arabie (1985) Lawrence Hubert and Phipps Arabie. 1985.  Comparing partitions.  _Journal of classification_ 2, 1 (1985), 193–218.
  * Jin et al. (2013) Long Jin, Yang Chen, Tianyi Wang, Pan Hui, and Athanasios V Vasilakos. 2013.  Understanding user behavior in online social networks: A survey.  _IEEE Communications Magazine_ 51, 9 (2013), 144–150.
  * Kempe et al. (2003) David Kempe, Jon Kleinberg, and Éva Tardos. 2003\.  Maximizing the spread of influence through a social network. In _SIGKDD_. 137–146.
  * Kim et al. (2014) Jungeun Kim, Minsoo Choy, Daehoon Kim, and U Kang. 2014\.  Link prediction based on generalized cluster information. In _WWW_. 317–318.
  * Kim et al. (2020) Junghoon Kim, Tao Guo, Kaiyu Feng, Gao Cong, Arijit Khan, and Farhana M Choudhury. 2020\.  Densely connected user community and location cluster search in location-based social networks. In _SIGMOD_. 2199–2209.
  * Kim et al. (2022a) Junghoon Kim, Sungsu Lim, and Jungeun Kim. 2022a.  OCSM : Finding Overlapping Cohesive Subgraphs with Minimum Degree.  arXiv:2202.03255 [cs.SI]
  * Kim et al. (2022b) Junghoon Kim, Siqiang Luo, Gao Cong, and Wenyuan Yu. 2022b.  DMCS : Density Modularity Based Community Search. In _SIGMOD_ _(SIGMOD ’22)_. ACM, New York, NY, USA, 889–903.
  * Laishram et al. (2020) Ricky Laishram, Ahmet Erdem Sar, Tina Eliassi-Rad, Ali Pinar, and Sucheta Soundarajan. 2020\.  Residual Core Maximization: An Efficient Algorithm for Maximizing the Size of the k-Core. In _SDM_. SIAM, 325–333.
  * Lancichinetti et al. (2008) Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. 2008\.  Benchmark graphs for testing community detection algorithms.  _PRE_ 78, 4 (2008), 046110.
  * Leskovec et al. (2007) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007\.  Graph evolution: Densification and shrinking diameters.  _TKDD_ 1, 1 (2007), 2.
  * Li et al. (2018) Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. 2018\.  Influence maximization on social graphs: A survey.  _TKDE_ 30, 10 (2018), 1852–1872.
  * Linghu et al. (2020) Qingyuan Linghu, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2020.  Global reinforcement of social networks: The anchored coreness problem. In _SIGMOD_. 2211–2226.
  * Liu et al. (2021) Kaixin Liu, Sibo Wang, Yong Zhang, and Chunxiao Xing. 2021\.  An Efficient Algorithm for the Anchored k-Core Budget Minimization Problem. In _ICDE_. IEEE, 1356–1367.
  * Luce (1950) R Duncan Luce. 1950\.  Connectivity and generalized cliques in sociometric group structure.  _Psychometrika_ 15, 2 (1950), 169–190.
  * Luo et al. (2021) Junjie Luo, Hendrik Molter, and Ondřej Suchỳ. 2021\.  A parameterized complexity view on collapsing k-cores.  _TOCS_ (2021), 1–40.
  * Malliaros et al. (2020) Fragkiskos D Malliaros, Christos Giatsidis, Apostolos N Papadopoulos, and Michalis Vazirgiannis. 2020\.  The core decomposition of networks: Theory, algorithms and applications.  _The VLDB Journal_ 29, 1 (2020), 61–92.
  * Malliaros and Vazirgiannis (2013) Fragkiskos D Malliaros and Michalis Vazirgiannis. 2013.  To stay or not to stay: modeling engagement dynamics in social graphs. In _CIKM_. 469–478.
  * Matula and Beck (1983) David W Matula and Leland L Beck. 1983.  Smallest-last ordering and clustering and graph coloring algorithms.  _Journal of the ACM (JACM)_ 30, 3 (1983), 417–427.
  * Mavroforakis et al. (2015) Charalampos Mavroforakis, Richard Garcia-Lebron, Ioannis Koutis, and Evimaria Terzi. 2015.  Spanning edge centrality: Large-scale computation and applications. In _WWW_. 732–742.
  * Michail et al. (2020) Dimitrios Michail, Joris Kinable, Barak Naveh, and John V. Sichi. 2020.  JGraphT—A Java Library for Graph Data Structures and Algorithms.  _ACM Trans. Math. Softw._ 46, 2, Article 16 (May 2020), 29 pages.  https://doi.org/10.1145/3381449
  * Minoux (1978) Michel Minoux. 1978\.  Accelerated greedy algorithms for maximizing submodular set functions.  In _Optimization techniques_. Springer, 234–243.
  * Nelson et al. (2004) Douglas L Nelson, Cathy L McEvoy, and Thomas A Schreiber. 2004\.  The University of South Florida free association, rhyme, and word fragment norms.  _Behavior Research Methods, Instruments, & Computers_ 36, 3 (2004), 402–407.
  * Nemhauser et al. (1978) George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978.  An analysis of approximations for maximizing submodular set functions—I.  _Mathematical programming_ 14, 1 (1978), 265–294.
  * Newman (2003) Mark EJ Newman. 2003\.  The structure and function of complex networks.  _SIAM review_ 45, 2 (2003), 167–256.
  * Palmer et al. (2002) Christopher R Palmer, Phillip B Gibbons, and Christos Faloutsos. 2002.  ANF: A fast and scalable tool for data mining in massive graphs. In _SIGKDD_. 81–90.
  * Rochat (2009) Yannick Rochat. 2009\.  _Closeness centrality extended to unconnected graphs: The harmonic centrality index_.  Technical Report.
  * Rossi and Ahmed (2015) Ryan A. Rossi and Nesreen K. Ahmed. 2015.  The Network Data Repository with Interactive Graph Analytics and Visualization. In _AAAI_. 4292–4293.  http://networkrepository.com
  * Sabidussi (1966) Gert Sabidussi. 1966\.  The centrality index of a graph.  _Psychometrika_ 31, 4 (1966), 581–603.
  * Salavaty et al. (2020) Abbas Salavaty, Mirana Ramialison, and Peter D Currie. 2020\.  Integrated value of influence: an integrative method for the identification of the most influential nodes within networks.  _Patterns_ 1, 5 (2020), 100052.
  * Sarıyüce et al. (2016) Ahmet Erdem Sarıyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and Ümit V Çatalyürek. 2016\.  Incremental k-core decomposition: algorithms and evaluation.  _VLDBJ_ 25, 3 (2016), 425–447.
  * Schneider et al. (2009) Fabian Schneider, Anja Feldmann, Balachander Krishnamurthy, and Walter Willinger. 2009.  Understanding online social network usage from a network perspective. In _Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement_. 35–48.
  * Schrijver (2003) Alexander Schrijver. 2003\.  _Combinatorial optimization: polyhedra and efficiency_. Vol. 24.  Springer Science & Business Media.
  * Seidman (1983) Stephen B Seidman. 1983\.  Network structure and minimum degree.  _Social networks_ 5, 3 (1983), 269–287.
  * Sozio and Gionis (2010) Mauro Sozio and Aristides Gionis. 2010.  The community-search problem and how to plan a successful cocktail party. In _SIGKDD_. 939–948.
  * Stephen and Toubia (2009) Andrew T Stephen and Olivier Toubia. 2009.  Explaining the power-law degree distribution in a social commerce network.  _Social Networks_ 31, 4 (2009), 262–270.
  * Wei et al. (2012) Ling-Yin Wei, Yu Zheng, and Wen-Chih Peng. 2012.  Constructing popular routes from uncertain trajectories. In _SIGKDD_. ACM, New York, NY, USA, 195–203.
  * Wu et al. (2015a) Huanhuan Wu, James Cheng, Yi Lu, Yiping Ke, Yuzhen Huang, Da Yan, and Hejun Wu. 2015a.  Core decomposition in large temporal graphs. In _2015 IEEE International Conference on Big Data (Big Data)_. IEEE, 649–658.
  * Wu et al. (2015b) Yubao Wu, Ruoming Jin, Jing Li, and Xiang Zhang. 2015b.  Robust local community detection: on free rider effect and its elimination.  _PVLDB_ 8, 7 (2015), 798–809.
  * Xiaolong and Linyuan (2014) Ren Xiaolong and Lv Linyuan. 2014.  Review of ranking nodes in complex networks.  _Chinese Science Bulletin_ 59, 13 (2014), 1175–1197.
  * Yang and Leskovec (2015) Jaewon Yang and Jure Leskovec. 2015.  Defining and evaluating network communities based on ground-truth.  _KAIS_ 42, 1 (2015), 181–213.
  * Zhang et al. (2020) Chen Zhang, Fan Zhang, Wenjie Zhang, Boge Liu, Ying Zhang, Lu Qin, and Xuemin Lin. 2020.  Exploring finer granularity within the cores: Efficient (k, p)-core computation. In _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. IEEE, 181–192.
  * Zhang et al. (2018a) Fan Zhang, Conggai Li, Ying Zhang, Lu Qin, and Wenjie Zhang. 2018a.  Finding critical users in social communities: The collapsed core and truss problems.  _TKDE_ 32, 1 (2018), 78–91.
  * Zhang et al. (2018b) Fan Zhang, Long Yuan, Ying Zhang, Lu Qin, Xuemin Lin, and Alexander Zhou. 2018b.  Discovering strong communities with user engagement and tie strength. In _DASFAA_. Springer, 425–441.
  * Zhang et al. (2017c) Fan Zhang, Wenjie Zhang, Ying Zhang, Lu Qin, and Xuemin Lin. 2017c.  OLAK: an efficient algorithm to prevent unraveling in social networks.  _VLDB_ (2017), 649–660.
  * Zhang et al. (2017a) Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017a.  Finding critical users for social network engagement: The collapsed k-core problem. In _AAAI_. 245–251.
  * Zhang et al. (2017b) Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017b.  Finding critical users for social network engagement: The collapsed k-core problem. In _AAAI_ (San Francisco, California, USA), Vol. 31. 245–251.
  * Zhou et al. (2019) Zhongxin Zhou, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Chen Chen. 2019.  K-Core Maximization: An Edge Addition Approach.. In _IJCAI_. 4867–4873.
  * Zhu et al. (2018) Weijie Zhu, Chen Chen, Xiaoyang Wang, and Xuemin Lin. 2018\.  K-core minimization: An edge manipulation approach. In _CIKM_. 1667–1670.