# Personalized Influential Community Search in Large Networks: A K-ECC-Based Model

Authors: Shi Meng; Hao Yang; Xijuan Liu; Zhenyue Chen; Jingwen Xuan; Yanping Wu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

Graphs have been widely used to model the complex relationships among entities. Community search is a fundamental problem in graph analysis. It aims to identify cohesive subgraphs or communities that contain the given query vertices. In social networks, a user is usually associated with a weight denoting its influence. Recently, some research is conducted to detect influential communities. However, there is a lack of research that can support personalized requirement. In this study, we propose a novel problem, named personalized influentialk-ECC (PIKE) search, which leverages the k-ECC model to measure the cohesiveness of subgraphs and tries to find the influential community for a set of query vertices. To solve the problem, a baseline method is first proposed. To scale for large networks, a dichotomy-based algorithm is developed. To further speed up the computation and meet the online requirement, we develop an index-based algorithm. Finally, extensive experiments are conducted on 6 real-world social networks to evaluate the performance of proposed techniques. Compared with the baseline method, the index-based approach can achieve up to 7 orders of magnitude speedup.


---

## Body

## 1. Introduction

With the proliferation of applications, graphs are widely used to represent entities and their relationships in real-life network data, e.g., social networks, collaboration networks, and communication networks [1–5]. Connected subgraph (community), existing as a functional module in different graphs, has been extensively explored to analyze graphs recently [6]. Community search and community detection are two fundamental problems in graph analysis. Community search aims to identify important communities (i.e., cohesive subgraphs) that contain the query vertices [7], while community detection aims to find all or top-k communities that satisfy the cohesiveness constraint [8, 9]. In this study, we focus on the problem of community search, which is an important tool for personalized applications, such as friend recommendation and product promotion [7, 10, 11].In social networks, a user is usually associated with a weight, denoting its influence in the network. Recently, the influential community detection problem has attracted great attention (e.g., Ref. [12–15]). Influential community detection aims to find the communities that are not only cohesive but also have large influence value. The influence value of a community is the minimum weight of all the vertices in the community [12, 14]. However, the personalized requirement is ignored by existing research. To meet the requirement, in this study, we propose a new problem, named personalized influential k-edge-connected component (PIKE) search, to find personalized influential communities in social networks. We use the k-edge-connected component (k-ECC) model to measure the cohesiveness of a subgraph, which remains connected after removing any k-1 edges in the graph [16–18]. Given a graph G and a set of query vertices Q, PIKE is the subgraph with the largest influence value that i contains all the vertices in Q (i.e., personalized), ii satisfies the k-ECC constraint (i.e., highly connected), and iii is maximal (i.e., there is no supergraph of it that can meet the constraints in (i) and (ii)). Note that, in our previous work [19], a k-ECC-based community search model is also proposed. However, it only focuses on the community with maximum k instead of any given k as in this study, while in this study, we can support both scenarios.Example 1.
As shown in Figure1, it is a small network with 14 vertices. For the simplicity, the number in each vertex denotes both its vertex id and weight. Given a query vertex set Q=v7,v8,v9 and k=3, the vertices in the dotted line are the corresponding result.Figure 1
Running example (the number in each vertex denotes its vertex id and weight).


### 1.1. Applications

In the literature, the study of PIKE search problem can find many applications. We list some examples as follows:(i)
Personalized product recommendation: in many social network platforms, such as Facebook, the weight of each user can represent its ability for information promotion in social networks, i.e., viral marketing. The platforms often provide product recommendations for users based on their relationships with others. Given a set of users who are already interested in certain products, other users who are highly connected with them may buy the same products. This is because the highly connected friends may belong to the same social cluster and share similar interests [20]. Besides, the influential users can make the product sales greatly increase. Hence, finding such groups of users in the platforms is helpful for recommendation system, which can be solved by investigating the PIKE of Q (i.e., the most highly connected component containing Q).(ii)
Collaboration team assembling: assembling a collaboration team for a specific project is essential in different scenarios. In a collaboration network, such as DBLP, the weight of vertices can be the influence or impact of the users. The researchers who are highly connected in a collaboration group are good candidates to be invited into the team [21]. Besides, the researchers who have high influence are also easy to get invitations to join groups because they can increase the impact of the research group. Such a team can be obtained by computing PIKE with the set of key researchers or initiators as the query Q. Also, the k-edge-connected component model indicates how strong they are connected.(iii)
Fraud group detection: in e-commerce platforms, such as Amazon, each customer is associated with a weight representing the number of times for its purchases or certain actions. There exist fraudulent users who give fake “like”s to products on platforms in order to promote the product [22]. These fraudulent users often form a closely connected group. Given a set of suspicious customers as the query set, our personalized influential k-ECC model can help us to find the most suspicious fraudster group, which can be further investigated by platforms.


### 1.2. Challenges

The challenges of the problem are twofold. Firstly, social networks are usually large. Therefore, it requires an algorithm that should have good scalability. Secondly, in real applications, there may be plenty of queries issued. It is necessary that the developed techniques can meet the online requirement.


### 1.3. Our Solution

To address these challenges, we first propose a baseline algorithm. Due to the definition of PIKE that is the subgraph with the largest influence value, we iteratively remove the vertex with the smallest influence value and maintain thek-ECC model containing the query vertex set. Considering that removing one vertex in each step leads to enormous iterations, especially for the large graph, a dichotomy-based algorithm is proposed. It removes half of the candidate vertices at each iteration and then checks the existence of k-ECC containing the query set, which can efficiently escape the redundant computations and obtain the result. Based on the deletion procedure of baseline, an index-based algorithm is further developed to meet the online requirement. Generally, we keep the order of deleting vertices and construct a tree index for each k. Given the set of query vertices and k, we can first retrieve the tree index by k and then locate the corresponding result efficiently.


### 1.4. Contributions

To the best of our knowledge, we are the first to investigate the personalized influentialk-ECC search problem. The contributions of this study are summarized as follows:(i)
We formally define the personalized influentialk-ECC search problem(ii)
Two algorithms, i.e., a baseline algorithm and a dichotomy-based algorithm, are first proposed to address the problem(iii)
To further accelerate the computation and meet the online requirement, an index-based algorithm is proposed(iv)
Experiments over 6 real-world social networks are conducted to show the superiority of proposed techniques


#### 1.4.1. Roadmap

We organize the rest of this study as follows. We first introduce the problem investigated in Section2. In Section 3, we present the baseline algorithm and dichotomy-based algorithm. In Section 4, we introduce the index-based algorithm. We report the evaluation of effectiveness and efficiency of our strategies in Section 5. Finally, we show the related work in Section 6 and conclude the study in Section 7.


## 1.1. Applications

In the literature, the study of PIKE search problem can find many applications. We list some examples as follows:(i)
Personalized product recommendation: in many social network platforms, such as Facebook, the weight of each user can represent its ability for information promotion in social networks, i.e., viral marketing. The platforms often provide product recommendations for users based on their relationships with others. Given a set of users who are already interested in certain products, other users who are highly connected with them may buy the same products. This is because the highly connected friends may belong to the same social cluster and share similar interests [20]. Besides, the influential users can make the product sales greatly increase. Hence, finding such groups of users in the platforms is helpful for recommendation system, which can be solved by investigating the PIKE of Q (i.e., the most highly connected component containing Q).(ii)
Collaboration team assembling: assembling a collaboration team for a specific project is essential in different scenarios. In a collaboration network, such as DBLP, the weight of vertices can be the influence or impact of the users. The researchers who are highly connected in a collaboration group are good candidates to be invited into the team [21]. Besides, the researchers who have high influence are also easy to get invitations to join groups because they can increase the impact of the research group. Such a team can be obtained by computing PIKE with the set of key researchers or initiators as the query Q. Also, the k-edge-connected component model indicates how strong they are connected.(iii)
Fraud group detection: in e-commerce platforms, such as Amazon, each customer is associated with a weight representing the number of times for its purchases or certain actions. There exist fraudulent users who give fake “like”s to products on platforms in order to promote the product [22]. These fraudulent users often form a closely connected group. Given a set of suspicious customers as the query set, our personalized influential k-ECC model can help us to find the most suspicious fraudster group, which can be further investigated by platforms.


## 1.2. Challenges

The challenges of the problem are twofold. Firstly, social networks are usually large. Therefore, it requires an algorithm that should have good scalability. Secondly, in real applications, there may be plenty of queries issued. It is necessary that the developed techniques can meet the online requirement.


## 1.3. Our Solution

To address these challenges, we first propose a baseline algorithm. Due to the definition of PIKE that is the subgraph with the largest influence value, we iteratively remove the vertex with the smallest influence value and maintain thek-ECC model containing the query vertex set. Considering that removing one vertex in each step leads to enormous iterations, especially for the large graph, a dichotomy-based algorithm is proposed. It removes half of the candidate vertices at each iteration and then checks the existence of k-ECC containing the query set, which can efficiently escape the redundant computations and obtain the result. Based on the deletion procedure of baseline, an index-based algorithm is further developed to meet the online requirement. Generally, we keep the order of deleting vertices and construct a tree index for each k. Given the set of query vertices and k, we can first retrieve the tree index by k and then locate the corresponding result efficiently.


## 1.4. Contributions

To the best of our knowledge, we are the first to investigate the personalized influentialk-ECC search problem. The contributions of this study are summarized as follows:(i)
We formally define the personalized influentialk-ECC search problem(ii)
Two algorithms, i.e., a baseline algorithm and a dichotomy-based algorithm, are first proposed to address the problem(iii)
To further accelerate the computation and meet the online requirement, an index-based algorithm is proposed(iv)
Experiments over 6 real-world social networks are conducted to show the superiority of proposed techniques


### 1.4.1. Roadmap

We organize the rest of this study as follows. We first introduce the problem investigated in Section2. In Section 3, we present the baseline algorithm and dichotomy-based algorithm. In Section 4, we introduce the index-based algorithm. We report the evaluation of effectiveness and efficiency of our strategies in Section 5. Finally, we show the related work in Section 6 and conclude the study in Section 7.


## 1.4.1. Roadmap

We organize the rest of this study as follows. We first introduce the problem investigated in Section2. In Section 3, we present the baseline algorithm and dichotomy-based algorithm. In Section 4, we introduce the index-based algorithm. We report the evaluation of effectiveness and efficiency of our strategies in Section 5. Finally, we show the related work in Section 6 and conclude the study in Section 7.


## 2. Preliminaries

In this section, we first introduce some necessary concepts and present the formal definition of the personalized influentialk-ECC search problem. Table 1 summarizes the notations that are frequently used in this study.Table 1
Summary of notations.
NotationDefinitionG=V,EA graph with vertex/edge setV/Eg=Vg,EgAn induced subgraph ofGnNumber of vertices inGmNumber of edges inGu,vVertex inGwuThe influence value ofu in GfgThe influence value of subgraphgλu,vThe connectivity betweenu and vλgThe connectivity of subgraphgkThe connectivity constraintQThe query vertex setWe consider a networkG=V,E as an undirected graph, where V and E represent the set of vertices and edges in G, respectively. n=V and m=E are the number of vertices and edges. Each vertex u∈V is associated with a weight ωu, representing its influence value. Without loss of generality, we use the same setting as the previous works for vertex weight, where different vertices have different weights [12, 14]. For vertices with the same weight, we break the tie randomly. A subgraph g=Vg,Eg is an induced graph of G, if Vg⊆V and Eg=u,v|u,v∈Vg∧u,v∈E. To measure the cohesiveness of subgraph, we utilize the k-edge-connected component (k-ECC) model, which is widely adopted [16].Definition 1 (connectivity).
Given a subgraphg and two vertices u,v∈Vg, the connectivity λu,v between u and v is the minimum number of edges, whose removal will disconnect u and v in g. The connectivity of g is the minimum connectivity between any two distinct vertices in g, i.e., λg=minu,v∈Vλu,v.Definition 2 (k-ECC).
Given a graphG, a subgraph g is a k-edge-connected component (k-ECC) of G if iλg≥k and iig is maximal, i.e., the connectivity of any supergraph of g is less than k.
To compute thek-ECCs, we apply the state-of-the-art method, which iteratively decomposes the graph by removing the unpromising edges [16]. As we discussed, we want to identify the community, which is not only cohesive but also has large influence value.Definition 3 (influence value).
Given a subgraphg, the influence value of g is denoted by the minimum weight of the vertex in Vg, i.e., fg=minu∈Vgωu.
In the previous studies, people usually focus on finding all or top-r influential communities, while the property of personalization is ignored, which is an important factor for network analysis. Inspired by this, we formally define the personalized influential k-ECC (PIKE) as follows.Definition 4 (personalized influentialk-ECC).
Given a graphG, a positive integer k, and a query vertex set Q, a personalized influential k-ECC (PIKE) is an induced subgraph g of G, which meets all the following constraints:(i)
Personalized:Q is contained in g, i.e., Q⊆Vg(ii)
Cohesiveness:λg≥k(iii)
Maximal: there is no other subgraphg′ that i satisfies the first two constraints, ii is a supergraph of g, i.e., g′⊃g, and iii has the same influence value as g, i.e., fg=fg′(iv)
Largest:g is the one with the largest influence value and satisfies the previous constraints


### 2.1. Problem Statement

Given a graphG=V,E, a set Q of query vertices, and a positive integer k, we aim to develop an efficient algorithm to find the PIKE for query vertices Q.


## 2.1. Problem Statement

Given a graphG=V,E, a set Q of query vertices, and a positive integer k, we aim to develop an efficient algorithm to find the PIKE for query vertices Q.


## 3. Solution

In this section, a baseline algorithm is firstly developed. Novel algorithms are further proposed to accelerate the computation.


### 3.1. Baseline Algorithm

Before introducing the baseline algorithm, we first present an important property about community influence value.Lemma 1.
Given a graphG and two induced subgraphs g1 and g2, we have Vg1=Vg2∪u. If the weight of u is smaller than the influence value of g2, i.e., ωu<fg2, then the influence value of g1 is smaller than that of g2, i.e., fg1<fg2.Proof.
Based on the definition of influence value, we havefg1=minv∈Vg1ωv≤ωu<fg2. Thus, the lemma is correct.
According to Lemma1, for a given subgraph g, we can increase its influence value by iteratively deleting the vertex with the smallest weight. Algorithm 1 presents the details of baseline method. We first compute the k-ECC g that contains the query vertices Q in Lines 1-2. Compute KECCs is the algorithm developed in [16], which is the state-of-the-art method for k-ECC computation. If the query vertices are not contained in any k-ECC, an error code is returned in Line 3, which means there is no satisfied community for the query. Otherwise, we sort the vertices of g in ascending order based on vertex weights and store the vertices, whose weight is smaller than that of Q, into S. If S is empty, then g is returned. Otherwise, we try to delete the vertex with the current smallest weight one by one in Line 7. For each processed vertex w, deleting it may break the connectivity of other vertices. Hence, we need to make sure the remained subgraph satisfies the connectivity constraint. When there is no k-ECC containing Q, we return the k-ECC g found in the previous iteration as the result (Lines 10-11). Note that, the vertices in S remain sorted as Line 4 does. Based on Lemma 1, the correctness of the algorithm is straightforward.Algorithm 1: Baseline algorithm
Input:G: a graph, Q: query vertices, k: a positive integerOutput: PIKE for the query(1)
H← Compute KECCs G,k;(2)
g← the k-ECC in H containing Q;(3)
ifg=∅then return error;(4)
S← vertices of g with weight smaller than fQ and sort vertices in the ascending order according to the weights(5)
whileS≠∅do(6)
w←S.front(7)
g′←g∖w(8)
H←Compute KECCs g′,k(9)
g′← the k-ECC in H containing Q(10)
ifg′=∅then(11)
break(12)
S←Vg′; g←g′(13)
returngExample 2.
Considering the graph in Figure1. Assume k = 2 and query vertex set Q is v5,v6. By the definition of baseline algorithm, we first compute the k-ECC of G. Then, we iteratively remove the vertex with the current smallest weight, i.e., v1, v2, and v3, and compute the result. After deleting the vertex v3, vertices v4, v13, and v14 violate the degree constraint and are removed. The remained graph is separated into two connected components. As we can see, there is no 2-ECC containing query set Q. Then, we stop and output 2-ECC containing Q by v3,v4,…,v14.


### 3.2. Dichotomy-Based Algorithm

The core part of the baseline algorithm is to locate the critical vertex, whose removal will lead to nonek-ECC (i.e., Lines 10-11 of Algorithm 1). To find the vertex, we need to delete the vertex orderly and check the result accordingly. For each deletion of a vertex, the computation of k-ECC is required, which is time-consuming, especially for large graphs. If we can remove a bulk of candidate vertices at once, it will avoid a lot of computation. Motivated by this, we introduce a dichotomy-based algorithm to accelerate the processing. The details are shown in Algorithm 2.Algorithm 2: Dichotomy-based algorithm
Input:G: a graph, Q: query vertices, k: a positive integerOutput: PIKE for the query(1)
H← Compute KECCs G,k(2)
g← the k-ECC in H containing Q(3)
Ifg=∅then return error(4)
S←vertices of g with weight smaller than fQ and sort vertices in the ascending order according to the weights(5)
whileS≠∅do(6)
D1← the first half of vertices in S(7)
D2← the second half of vertices in S(8)
g′← remove D1from g(9)
H← Compute KECCs g′,k(10)
g′← the k-ECC in H containing Q(11)
ifg′=∅then(12)
ifD1=1then break;(13)
S←D1(14)
else(15)
S←Vg′∩D2; g←g′(16)
returngIn Algorithm2, the first three steps (i.e., Lines 1–4) are the same as the baseline algorithm, which is to find the k-ECC containing Q and initialize the candidate vertex set S. Then, we process the candidates in a dichotomy manner. That is, we iteratively partition the vertices in S into two sets D1 and D2. D1 contains the vertices in the first half of S, and D2 consists of the others (Lines 6-7). If S=1, we put the vertex in D1. Next, we try to remove the vertices in D1 from the current k-ECC g and compute the k-ECC on the remained subgraph g′ (Lines 8-9). If the returned k-ECC still contains Q, we repeat the procedure on the remained graph (Line 15). Otherwise, it means we can only remove part of vertices in D1 to obtain the PIKE. The procedure terminates if S is empty or no more vertex can be removed from the candidate set (Lines 5 and 12). By conducting the search in a dichotomy manner, we can reduce the computation time of k-ECC from OS to Olog2S, whose advantages could also be observed from our experiment evaluation.Example 3.
Reconsidering the graph in Figure1. Assume k  = 2 and query vertex set Q is v5,v6. By the definition of dichotomy-based algorithm, we first compute 2-ECC containing Q and then initialize the candidate vertex set S with v1,v2,v3,v4. We partition the vertices in S into D1 (i.e., v1,v2) and D2 (i.e., v3,v4). Next, we remove the vertices in D1 and obtain 2-ECC containing Q in the remained subgraph. The candidate set S is updated by v3,v4. We repeat the same procedure, and we can find that there is no 2-ECC containing Q after removing D1 (i.e., v3). So, we return the result obtained in last iteration, i.e., v3,v4,…,v14.


## 3.1. Baseline Algorithm

Before introducing the baseline algorithm, we first present an important property about community influence value.Lemma 1.
Given a graphG and two induced subgraphs g1 and g2, we have Vg1=Vg2∪u. If the weight of u is smaller than the influence value of g2, i.e., ωu<fg2, then the influence value of g1 is smaller than that of g2, i.e., fg1<fg2.Proof.
Based on the definition of influence value, we havefg1=minv∈Vg1ωv≤ωu<fg2. Thus, the lemma is correct.
According to Lemma1, for a given subgraph g, we can increase its influence value by iteratively deleting the vertex with the smallest weight. Algorithm 1 presents the details of baseline method. We first compute the k-ECC g that contains the query vertices Q in Lines 1-2. Compute KECCs is the algorithm developed in [16], which is the state-of-the-art method for k-ECC computation. If the query vertices are not contained in any k-ECC, an error code is returned in Line 3, which means there is no satisfied community for the query. Otherwise, we sort the vertices of g in ascending order based on vertex weights and store the vertices, whose weight is smaller than that of Q, into S. If S is empty, then g is returned. Otherwise, we try to delete the vertex with the current smallest weight one by one in Line 7. For each processed vertex w, deleting it may break the connectivity of other vertices. Hence, we need to make sure the remained subgraph satisfies the connectivity constraint. When there is no k-ECC containing Q, we return the k-ECC g found in the previous iteration as the result (Lines 10-11). Note that, the vertices in S remain sorted as Line 4 does. Based on Lemma 1, the correctness of the algorithm is straightforward.Algorithm 1: Baseline algorithm
Input:G: a graph, Q: query vertices, k: a positive integerOutput: PIKE for the query(1)
H← Compute KECCs G,k;(2)
g← the k-ECC in H containing Q;(3)
ifg=∅then return error;(4)
S← vertices of g with weight smaller than fQ and sort vertices in the ascending order according to the weights(5)
whileS≠∅do(6)
w←S.front(7)
g′←g∖w(8)
H←Compute KECCs g′,k(9)
g′← the k-ECC in H containing Q(10)
ifg′=∅then(11)
break(12)
S←Vg′; g←g′(13)
returngExample 2.
Considering the graph in Figure1. Assume k = 2 and query vertex set Q is v5,v6. By the definition of baseline algorithm, we first compute the k-ECC of G. Then, we iteratively remove the vertex with the current smallest weight, i.e., v1, v2, and v3, and compute the result. After deleting the vertex v3, vertices v4, v13, and v14 violate the degree constraint and are removed. The remained graph is separated into two connected components. As we can see, there is no 2-ECC containing query set Q. Then, we stop and output 2-ECC containing Q by v3,v4,…,v14.


## 3.2. Dichotomy-Based Algorithm

The core part of the baseline algorithm is to locate the critical vertex, whose removal will lead to nonek-ECC (i.e., Lines 10-11 of Algorithm 1). To find the vertex, we need to delete the vertex orderly and check the result accordingly. For each deletion of a vertex, the computation of k-ECC is required, which is time-consuming, especially for large graphs. If we can remove a bulk of candidate vertices at once, it will avoid a lot of computation. Motivated by this, we introduce a dichotomy-based algorithm to accelerate the processing. The details are shown in Algorithm 2.Algorithm 2: Dichotomy-based algorithm
Input:G: a graph, Q: query vertices, k: a positive integerOutput: PIKE for the query(1)
H← Compute KECCs G,k(2)
g← the k-ECC in H containing Q(3)
Ifg=∅then return error(4)
S←vertices of g with weight smaller than fQ and sort vertices in the ascending order according to the weights(5)
whileS≠∅do(6)
D1← the first half of vertices in S(7)
D2← the second half of vertices in S(8)
g′← remove D1from g(9)
H← Compute KECCs g′,k(10)
g′← the k-ECC in H containing Q(11)
ifg′=∅then(12)
ifD1=1then break;(13)
S←D1(14)
else(15)
S←Vg′∩D2; g←g′(16)
returngIn Algorithm2, the first three steps (i.e., Lines 1–4) are the same as the baseline algorithm, which is to find the k-ECC containing Q and initialize the candidate vertex set S. Then, we process the candidates in a dichotomy manner. That is, we iteratively partition the vertices in S into two sets D1 and D2. D1 contains the vertices in the first half of S, and D2 consists of the others (Lines 6-7). If S=1, we put the vertex in D1. Next, we try to remove the vertices in D1 from the current k-ECC g and compute the k-ECC on the remained subgraph g′ (Lines 8-9). If the returned k-ECC still contains Q, we repeat the procedure on the remained graph (Line 15). Otherwise, it means we can only remove part of vertices in D1 to obtain the PIKE. The procedure terminates if S is empty or no more vertex can be removed from the candidate set (Lines 5 and 12). By conducting the search in a dichotomy manner, we can reduce the computation time of k-ECC from OS to Olog2S, whose advantages could also be observed from our experiment evaluation.Example 3.
Reconsidering the graph in Figure1. Assume k  = 2 and query vertex set Q is v5,v6. By the definition of dichotomy-based algorithm, we first compute 2-ECC containing Q and then initialize the candidate vertex set S with v1,v2,v3,v4. We partition the vertices in S into D1 (i.e., v1,v2) and D2 (i.e., v3,v4). Next, we remove the vertices in D1 and obtain 2-ECC containing Q in the remained subgraph. The candidate set S is updated by v3,v4. We repeat the same procedure, and we can find that there is no 2-ECC containing Q after removing D1 (i.e., v3). So, we return the result obtained in last iteration, i.e., v3,v4,…,v14.


## 4. Index-Based Algorithm

Algorithm 3: Index construction
Input:G: a graphOutput: constructed Index(1)
fork from 1 to kmax do(2)
Tk← initialize a tree root node for k(3)
H← Compute KECCs G,k(4)
for eachg∈Hdo(5)
Build NodeTk,g,k(6)
returnT1,T2,…,Tmax(7)
Procedure Build Node T,g,k(8)
construct a tree nodeN(9)
u← the vertex with the smallest weight in g(10)
H← Compute KECCs g,u,k(11)
N←Vg, vertices in H(12)
addN as a child node of T(13)
for eachg′∈H do(14)
Build NodeN,g′,kCompared with the baseline method, the dichotomy-based algorithm can significantly reduce the cost of computingk-ECCs. However, this approach still has some limitations: i deleting vertices and recomputing k-ECC still cost a lot for processing large graphs and ii in real-world applications, different users may have different requirements and there may exist a lot of queries. Therefore, it will be difficult for the method to meet the online requirements. Motivated by this, we develop an index-based algorithm. The idea is that, for each k, we follow the vertex deletion procedure by iteratively removing the vertex with the smallest weight in current k-ECC. The deletion of certain vertex will cause some other vertices to violate the connectivity constraint and be removed from the k-ECC. We keep the order of these vertices and construct a tree index.


### 4.1. Index Construction

The index construction details are shown in Algorithm3. For each k from 1 to kmax, we construct a tree index (Line 2). Then, we process each k-ECC of G with Build Node procedure, whose details are in Lines 7-14. In Build Node, we construct an intermediate node for the input k-ECC g. Then, we delete the vertex with the smallest weight in g and compute the k-ECC H on the remained graph (Lines 9-10). We store the vertices violating the connectivity constraint in N and add N as the child node of T (Lines 11-12). The procedure terminates when all the vertices are processed.Example 4.
Figure2 shows the constructed index for the graph in Figure 1 when k=2,3. For k=3, the constructed index is shown in Figure 2(b). We first process v1, which leads to the removal of v13 and v14. Then, we remove v2 and cause v4 to violate the connectivity constraint. Deleting v4 results in 2 connected components. When deleting v3, the connectivity of v5, v11, and v12 becomes less than 3. Therefore, we construct a tree node for the four vertices. For the other connected component, we conduct similar procedure and the constructed index is shown in the right branch.Figure 2
Index construction and query processing example: (a)k=2 and (b) k=3.
(a)(b)


### 4.2. Query Processing

For a given query, we first retrieve the tree index byk. Then, we locate the intermediate tree nodes that contain the query vertices. Finally, we only need to find their closest common ancestor Na and return all the vertices in Na and its child nodes as the results. Following is an example of index construction and query processing.Example 5.
Fork=2, we perform the similar procedure, where the corresponding index is shown in Figure 2(a). Given a query with k=2 and Q=v5,v7, then we retrieve the closest common ancestor node of v5,v7. Therefore, the vertices in the dotted circle of Figure 2(a) are the results. Similarly, when k=3 and Q=v7,v8,v9, the vertices in the dotted circle of Figure 2(b) are the results.


## 4.1. Index Construction

The index construction details are shown in Algorithm3. For each k from 1 to kmax, we construct a tree index (Line 2). Then, we process each k-ECC of G with Build Node procedure, whose details are in Lines 7-14. In Build Node, we construct an intermediate node for the input k-ECC g. Then, we delete the vertex with the smallest weight in g and compute the k-ECC H on the remained graph (Lines 9-10). We store the vertices violating the connectivity constraint in N and add N as the child node of T (Lines 11-12). The procedure terminates when all the vertices are processed.Example 4.
Figure2 shows the constructed index for the graph in Figure 1 when k=2,3. For k=3, the constructed index is shown in Figure 2(b). We first process v1, which leads to the removal of v13 and v14. Then, we remove v2 and cause v4 to violate the connectivity constraint. Deleting v4 results in 2 connected components. When deleting v3, the connectivity of v5, v11, and v12 becomes less than 3. Therefore, we construct a tree node for the four vertices. For the other connected component, we conduct similar procedure and the constructed index is shown in the right branch.Figure 2
Index construction and query processing example: (a)k=2 and (b) k=3.
(a)(b)


## 4.2. Query Processing

For a given query, we first retrieve the tree index byk. Then, we locate the intermediate tree nodes that contain the query vertices. Finally, we only need to find their closest common ancestor Na and return all the vertices in Na and its child nodes as the results. Following is an example of index construction and query processing.Example 5.
Fork=2, we perform the similar procedure, where the corresponding index is shown in Figure 2(a). Given a query with k=2 and Q=v5,v7, then we retrieve the closest common ancestor node of v5,v7. Therefore, the vertices in the dotted circle of Figure 2(a) are the results. Similarly, when k=3 and Q=v7,v8,v9, the vertices in the dotted circle of Figure 2(b) are the results.


## 5. Experiment

### 5.1. Algorithms

To the best of our knowledge, there is no existing work for the proposed problem. In the experiments, we implement and evaluate the following algorithms:(i)
BL: the baseline algorithm proposed in Algorithm1.(ii)
DBA: the dichotomy-based algorithm proposed in Algorithm2.(iii)
IBA: the index-based algorithm proposed in this study.


### 5.2. Datasets and Workloads

We employ 6 real-world networks, which are publicly available on SNAP (http://snap.stanford.edu). Their number of vertices and edges is reported in Table 2. We use the PageRank score of vertex to denote its weight, which is widely used in existing studies [12, 14]. To evaluate the performance of proposed techniques, we vary the parameter k, the number of query vertices Q, and the weight distribution ω of query vertices. For each setting, we randomly generate 20 queries with nonempty results and run the algorithms 10 times to report average response time. All algorithms are implemented in C++, and all the experiments are performed on a PC with an Intel i5-9600KF CPU and 32 GB RAM.Table 2
Statistics of datasets.
Datasetn=Vm=EEmail-Eu-core1,00516,064Facebook4,03988,234Email-Enron36,692367,662Brightkite58,228214,078Gowalla196,591950,327YouTube1,134,8902,987,624


### 5.3. Results of Varyingk

We first conduct the experiments on all datasets by varyingk from 5 to 25. For each query Q, we randomly selected 10 vertices from the graph. The corresponding results are shown in Figures 3(a)–3(f). We can see that IBA and DBA significantly outperform BL by a wide margin. In Gowalla, IBA can achieve up to 7 orders of magnitude speedup compared with the baseline method. This is because, with the proposed index, we only need to access the data that are related to queries. As observed, when k increases, the running time decreases for all methods, since the community size decreases and more space could be directly pruned based on the cohesive subgraph model.Figure 3
Experiment results by varying parametersk: (a) Email-Eu-core, (b) Facebook, (c) Email-Enron, (d) Brightkite, (e) Gowalla, and (f) YouTube.
(a)(b)(c)(d)(e)(f)


### 5.4. Results of VaryingQ

To further evaluate the performance, we vary the numberQ of queried vertices from 2 to 30 with k=15 as default. The results are shown in Figures 4(a)–4(f), where similar trends can be observed. IBA is significantly faster than BL because of the index structure developed. The running time of BL and DBA decreases when Q increases. This is because larger Q will lead to smaller size of candidate vertices in S. The running time of IBA slightly increases when Q increases because it will need more time to locate the corresponding tree nodes and their common ancestor.Figure 4
Experiment results by varying number of query verticesQ: (a) Email-Eu-core, (b) Facebook, (c) Email-Enron, (d) Brightkite, (e) Gowalla, and (f) YouTube.
(a)(b)(c)(d)(e)(f)


### 5.5. Results of Varyingω

We sort the vertices in an increasing order according to the weights and divide them into 5 buckets. We vary the weight distributionω of queried vertices from 20% to 100%. The results are shown in Figures 5(a)–5(f), where x% means the query vertices are selected from the range x% to x+20%. Larger x% means higher weight. Note that, to make it fair, for each query, we set Q=2 and k=5. This is because, for larger Q and k, it may lead to lots of empty results. As shown, DBA and IBA are not sensitive to ω. When ω increases, the response time of BL increases greatly. This is because, larger ω means larger candidate size, i.e., S. Since BL processes the candidates in linear manner, it will invoke the k-ECC computation procedure a lot of times. In Gowalla, when ω=80%, BL requires 64567.46 s to find the result, while IBA only takes 0.00139 s because of the advanced index developed in this study.Figure 5
Experiment results by varying weight distributionω of query vertices: (a) Email-Eu-core, (b) Facebook, (c) Email-Enron, (d) Brightkite, (e) Gowalla, and (f) YouTube.
(a)(b)(c)(d)(e)(f)


## 5.1. Algorithms

To the best of our knowledge, there is no existing work for the proposed problem. In the experiments, we implement and evaluate the following algorithms:(i)
BL: the baseline algorithm proposed in Algorithm1.(ii)
DBA: the dichotomy-based algorithm proposed in Algorithm2.(iii)
IBA: the index-based algorithm proposed in this study.


## 5.2. Datasets and Workloads

We employ 6 real-world networks, which are publicly available on SNAP (http://snap.stanford.edu). Their number of vertices and edges is reported in Table 2. We use the PageRank score of vertex to denote its weight, which is widely used in existing studies [12, 14]. To evaluate the performance of proposed techniques, we vary the parameter k, the number of query vertices Q, and the weight distribution ω of query vertices. For each setting, we randomly generate 20 queries with nonempty results and run the algorithms 10 times to report average response time. All algorithms are implemented in C++, and all the experiments are performed on a PC with an Intel i5-9600KF CPU and 32 GB RAM.Table 2
Statistics of datasets.
Datasetn=Vm=EEmail-Eu-core1,00516,064Facebook4,03988,234Email-Enron36,692367,662Brightkite58,228214,078Gowalla196,591950,327YouTube1,134,8902,987,624


## 5.3. Results of Varyingk

We first conduct the experiments on all datasets by varyingk from 5 to 25. For each query Q, we randomly selected 10 vertices from the graph. The corresponding results are shown in Figures 3(a)–3(f). We can see that IBA and DBA significantly outperform BL by a wide margin. In Gowalla, IBA can achieve up to 7 orders of magnitude speedup compared with the baseline method. This is because, with the proposed index, we only need to access the data that are related to queries. As observed, when k increases, the running time decreases for all methods, since the community size decreases and more space could be directly pruned based on the cohesive subgraph model.Figure 3
Experiment results by varying parametersk: (a) Email-Eu-core, (b) Facebook, (c) Email-Enron, (d) Brightkite, (e) Gowalla, and (f) YouTube.
(a)(b)(c)(d)(e)(f)


## 5.4. Results of VaryingQ

To further evaluate the performance, we vary the numberQ of queried vertices from 2 to 30 with k=15 as default. The results are shown in Figures 4(a)–4(f), where similar trends can be observed. IBA is significantly faster than BL because of the index structure developed. The running time of BL and DBA decreases when Q increases. This is because larger Q will lead to smaller size of candidate vertices in S. The running time of IBA slightly increases when Q increases because it will need more time to locate the corresponding tree nodes and their common ancestor.Figure 4
Experiment results by varying number of query verticesQ: (a) Email-Eu-core, (b) Facebook, (c) Email-Enron, (d) Brightkite, (e) Gowalla, and (f) YouTube.
(a)(b)(c)(d)(e)(f)


## 5.5. Results of Varyingω

We sort the vertices in an increasing order according to the weights and divide them into 5 buckets. We vary the weight distributionω of queried vertices from 20% to 100%. The results are shown in Figures 5(a)–5(f), where x% means the query vertices are selected from the range x% to x+20%. Larger x% means higher weight. Note that, to make it fair, for each query, we set Q=2 and k=5. This is because, for larger Q and k, it may lead to lots of empty results. As shown, DBA and IBA are not sensitive to ω. When ω increases, the response time of BL increases greatly. This is because, larger ω means larger candidate size, i.e., S. Since BL processes the candidates in linear manner, it will invoke the k-ECC computation procedure a lot of times. In Gowalla, when ω=80%, BL requires 64567.46 s to find the result, while IBA only takes 0.00139 s because of the advanced index developed in this study.Figure 5
Experiment results by varying weight distributionω of query vertices: (a) Email-Eu-core, (b) Facebook, (c) Email-Enron, (d) Brightkite, (e) Gowalla, and (f) YouTube.
(a)(b)(c)(d)(e)(f)


## 6. Related Work

### 6.1. Cohesive Subgraph Mining

In the literature, computing cohesive subgraphs has been widely studied, where different models are proposed to measure the cohesiveness of community, such ask-core [23, 24], k-ECC [16], k-truss [25, 26], and clique [27, 28]. These works aim to compute all maximal subgraphs whose cohesiveness is no smaller than a given threshold. In [16–18], novel techniques are developed to identify cohesive subgraphs based on the k-ECC model. Compared with the k-core model, the k-ECC model enjoys much more cohesiveness. In general, there are three methods to compute k-ECCs of a graph, i.e., cut-based method [29], decomposition-based method [16], and random contraction [17]. However, these techniques cannot be applied to the problem studied in this study due to different problem definitions.


### 6.2. Influential Community Detection

As discussed, users in the social networks are usually associated with weights denoting their influence. Reference [12] presents a novel model, named k-influential community, based on the k-core concept, and tries to find the top-rk-influential communities from the networks. Considering the importance of the problem, in [13], a backward search algorithm is presented to enable early termination. Moreover, in [14], a local search algorithm is developed to overcome the deficiency of accessing the whole graph. In [15], a personalized influential community search has been proposed, which aims to retrieve the most influential community for query vertex by leveraging the k-core concept. In our previous work [19], a k-ECC-based community search model is proposed. However, it only focuses on the community with maximum k instead of any given k as in this study.


### 6.3. Community Search

Community search, which aims to find cohesive subgraphs containing the query vertices, has been widely studied (e.g., [10, 30]). Refs. [31, 32] use the minimum degree to server as the metric to measure the cohesiveness of a community and aim to find the maximal connected k-core with maximal k value. Reference [32] proposes a global search algorithm, and Reference [31] proposes a local search method for the problem. In [33], the authors study the online community search based on the k-truss concepts and develop a novel tree shape index, i.e., TCP index, to efficiently search k-truss community. There are many studies on other types of graphs, e.g., attribute graphs and signed graphs [34, 35]. A comprehensive survey about recent studies on community search problem can be found in [7]. As observed, there is a lack of research for personalized influential community search problem, which is of great importance for many social network-based applications.


## 6.1. Cohesive Subgraph Mining

In the literature, computing cohesive subgraphs has been widely studied, where different models are proposed to measure the cohesiveness of community, such ask-core [23, 24], k-ECC [16], k-truss [25, 26], and clique [27, 28]. These works aim to compute all maximal subgraphs whose cohesiveness is no smaller than a given threshold. In [16–18], novel techniques are developed to identify cohesive subgraphs based on the k-ECC model. Compared with the k-core model, the k-ECC model enjoys much more cohesiveness. In general, there are three methods to compute k-ECCs of a graph, i.e., cut-based method [29], decomposition-based method [16], and random contraction [17]. However, these techniques cannot be applied to the problem studied in this study due to different problem definitions.


## 6.2. Influential Community Detection

As discussed, users in the social networks are usually associated with weights denoting their influence. Reference [12] presents a novel model, named k-influential community, based on the k-core concept, and tries to find the top-rk-influential communities from the networks. Considering the importance of the problem, in [13], a backward search algorithm is presented to enable early termination. Moreover, in [14], a local search algorithm is developed to overcome the deficiency of accessing the whole graph. In [15], a personalized influential community search has been proposed, which aims to retrieve the most influential community for query vertex by leveraging the k-core concept. In our previous work [19], a k-ECC-based community search model is proposed. However, it only focuses on the community with maximum k instead of any given k as in this study.


## 6.3. Community Search

Community search, which aims to find cohesive subgraphs containing the query vertices, has been widely studied (e.g., [10, 30]). Refs. [31, 32] use the minimum degree to server as the metric to measure the cohesiveness of a community and aim to find the maximal connected k-core with maximal k value. Reference [32] proposes a global search algorithm, and Reference [31] proposes a local search method for the problem. In [33], the authors study the online community search based on the k-truss concepts and develop a novel tree shape index, i.e., TCP index, to efficiently search k-truss community. There are many studies on other types of graphs, e.g., attribute graphs and signed graphs [34, 35]. A comprehensive survey about recent studies on community search problem can be found in [7]. As observed, there is a lack of research for personalized influential community search problem, which is of great importance for many social network-based applications.


## 7. Conclusion

Graphs are widely used to model the complex relationships among different entities. In graph analysis, community search is a fundamental problem and receives great attention recently. In a network, users are usually associated with weights denoting its influence in the network, which is neglected by most previous studies. In this study, we conduct the first research to investigate the personalized influentialk-ECC (PIKE) search problem in large networks. We formally define the problem and propose a baseline algorithm. To reduce the cost of k-ECC computation, a dichotomy-based algorithm is developed to reduce the searching space. In real scenarios, there may be a lot of queries issued. To meet the online requirement in real applications, an index-based algorithm is further developed to accelerate the computation. Experiments are conducted on 6 real-world social networks to verify the advantages of proposed techniques.



---

*Source: 5363946-2021-11-29.xml*