K-Core Maximization: An Edge Addition Approach

1 Introduction

Graphs are widely used to model networks, where each vertex represents a user and each edge represents a connection between two users. The cohesive subgraph model of k-core, introduced by [Seidman, 1983], is defined as the maximal induced subgraph in which every vertex has at least k neighbors (adjacent vertices) in the subgraph. The k-core of a network corresponds to the natural equilibrium of a user engagement model: each user incurs a cost (e.g., k) to remain engaged but receives a benefit proportional to (e.g., equal to) the number of engaged neighbors. Since the number of vertices (the size) of k-core reflects the stability of a network, it is widely adopted in the study of network engagement (stability), e.g., [Bhawalkar et al., 2015; Malliaros and Vazirgiannis, 2013; Wu et al., 2013].

To prevent network unraveling, Bhawalkar and Kleinberg et al. propose the anchored k-core problem which maximizes the k-core by anchoring b vertices [Bhawalkar et al., 2015], where the degree of an anchor is considered as infinitely large. There are a series of following work to maximize the k-core, e.g., [Zhang et al., 2018b; Zhang et al., 2017a; Chitnis et al., 2013]. In order to improve network stability, another basic graph operation is edge addition, which can also be applied to k-core maximization. Thus, the edge k-core problem is proposed [Chitnis and Talmon, 2018]: Given a graph G, an integer k and a budget b, add b edges to non-adjacent vertex pairs in G such that the k-core is the largest.

Zhongxin Zhou and Fan Zhang are the joint first authors. Fan Zhang is the corresponding author.

Example 1. Figure 1 depicts a social group G with 9 users and their connections. The willingness of a user to keep engaged is influenced by the number of her friends (neighbors) in this group. According to the k-core model, suppose k = 3, v4, v6, and v7 firstly drop out. Their departure leads to the leave of v5 and v8, as their degrees decrease to 1 which is less than k. To improve network stability, we can anchor v6 and v7 based on anchored k-core model, or add an edge between v6 and v7 based on edge k-core model. Both solutions lead to a larger k-core induced by the vertices in G except v4.

The edge k-core problem can find many applications on real-life networks: friend recommendation in social networks, connection construction in telecom networks, etc. For instance, in a P2P network, any user benefiting from the network should be connected to at least k other users, to exchange resources. The holder of a P2P network can use the edge k-core model to find which connections should be added between users so that a large number of users can successfully use the P2P network [Chitnis and Talmon, 2018].

Challenges and Contributions. In this paper, we propose a concise reduction to prove that the problem is NP-hard and APX-hard. The only existing solution is proposed for graphs with bounded tree-width [Chitnis and Talmon, 2018]. However, this assumption usually does not hold in real-life graphs, and their techniques cannot be extended to handle general graphs. Due to the hardness of the problem, we propose a heuristic algorithm with effective pruning techniques. The experiments are conducted on 9 real networks to demonstrate the effectiveness and the efficiency of the proposed methods.

2 RelatedWork

Graph processing on large data may require higher computation efficiency than traditional queries [Luo et al., 2008; Cheema et al., 2010; Luo et al., 2011]. Cohesive subgraph mining is a fundamental graph problem, with various models such as clique [Luce and Perry, 1949], k-core [Seidman, 1983], k-fami [Zhang et al., 2018a], etc. Among the models, k-core is the only one known to have a linear time algorithm [Batagelj and Zaversnik, 2003]. The k-core has a wide range of applications such as social contagion [Ugander et al., 2012], influential spreader identification [Kitsak et al., 2010], collapse prediction [Morone et al., 2019], user engagement study [Malliaros and Vazirgiannis, 2013], etc.

There is an efficient heuristic algorithm for the anchored kcore problem [Zhang et al., 2017a], while it cannot be simply applied to solve the edge k-core problem. One major reason is that the anchored k-core model does not change the topology of the graph while the edge k-core model needs to add new edges. Besides the k-core maximization work introduced in Section 1, there are some studies on k-core minimization under the view of against attack [Zhang et al., 2017b; Zhu et al., 2018; Medya et al., 2019].

The edge addition has been studied in different topics. [Natanzon et al., 2001] studies the hardness of edge modification problems on some classes of graphs. [Suady and Najim, 2014] aims to reduce the diameter of a graph by adding edges. [Lai et al., 2005] aims to add a small number of edges in a graph to enlarge the bandwidth. [Kapron et al., 2011] aims to anonymize a given vertex set by adding fewest edges.

3 Preliminaries

We consider a simple, undirected and unweighted graph G = (V,E), where V is a set of vertices and and E is a set of edges. We denote n = |V |, m = |E| and assume m > n. Let S = (V ′ ,E′ ) be an induced subgraph of G, where V ′ ⊆ V and E′ ⊆ E. The notations are summarized in Table 1.

Definition 1. k-core. Given a graph G, a subgraph S is the k-core of G, denoted by Ck(G), if (i) deg(u, S) ≥ k for every vertice u ∈ S; (ii) S is maximal, i.e., any subgraph S′ ⊃ S is not a k-core.

The k-core of a graph G can be obtained by recursively removing every vertex u and its incident edges in G if deg(u,G) < k, with a time complexity of O(m). The kcores of G with different inputs of k constitute a hierarchical structure of G, i.e., Ck+1(G) ⊆ Ck(G) for every value of k. The definition of k-shell is then derived.

Definition 2. k-shell. Given a graph G, the k-shell of G, denoted by Hk(G), is the set of vertices in k-core but not in (k+1)-core, i.e., Hk(G) = V (Ck(G) - Ck+1(G)).

If we add some new edges among the vertices which are not adjacent, the k-core of the graph may contain more vertices, which is named the edge k-core. The added new edges are called anchors or anchor edges. In this paper, we say anchor, add, or insert an edge interchangeably, e.g., an inserted edge is also called an anchored edge. The edges, which may be inserted to the graph, are called candidate anchors or candidate edges.

Definition 3. edge k-core. Given a graph G and a set of anchor edges A ⊆ ((V2 ) \ E), the edge k-core, denoted by Ck(G+A), is the k-core of the graph G′ = (V,E ∪A).

Due to the addition of anchor edges (A), more vertices might be retained in Ck(G+ A), in addition to the vertices in Ck(G). Note that the vertices not incident to the anchor edges may also be retained, according to the contagious nature of k-core computation. The vertices following the anchor edges A to engage in k-core are named the followers of A, denoted by F(A,G). Formally, F(A,G) is the set of vertices in Ck(G+A) \Ck(G). The number of the followers reflects the importance of the corresponding anchor edges.

Problem Statement. Given a graph G, a degree constraint k and a budget b, the edge k-core problem aims to find a set A of b edges in (V2 ) \ E such that the number of followers of A is maximized, i.e., F(A, G) is maximized.

4 Complexity

Theorem 1. Edge k-core problem is NP-hard when k ≥ 3.

Proof. We reduce the edge k-core problem from the maximum coverage (MC) problem [Karp, 1972] which is NP-hard. The MC problem is to find at most b sets to cover the largest number of elements, where b is a given budget. We consider an arbitrary instance of MC with c sets T1, .., Tc and d elements {e1, .., ed} = ∪1≤i≤cTi. We suppose c > k, c > b, and each of the resulting b sets contains at least 2 elements, without loss of generality. Then we construct a corresponding instance of the edge k-core problem on a graph G. Figure 2 shows a construction example from 3 sets and 4 elements when k = 3.

The set of vertices in G consists of three parts: M, N and Q. The part M contains c set of vertices where each set has d + 3 vertices, i.e., M = ∪1≤i≤cMi where Mi = ∪1≤j≤d+3uij . The part N contains d vertices. The part Q is a (k+1)-clique where every two vertices of the k + 1 vertices are adjacent. For every i and j, if ei ∈ Tj in the MC instance, we add an edge between vi and uji . In Figure 2, these edges are marked in bold. For every Mi in M, we connect uij and uij+1 by an edge for every j ∈ [1, d + 2], and we also connect ui1 and uid+3 . For every Mi, we add edges between every vertex in Mi and the vertices in Q so that every vertex in Mi \ {uid+1 , uid+3 } has a degree of k and every vertex in {uid+1 , uid+3 } has a degree of k - 1. We add k - 1 edges between vi and the vertices in Q for every i ∈ [1, d]. The construction of G is completed.

The k-core computation will delete all the vertices in M and N. Thus, the k-core of G is Q. To enlarge the k-core, the solution (A) is to add edges between uid+1 and uid+3 , which is most cost-effective. Another solution is to add edges between Mi and Mj where i ̸= j may also enlarge the k-core, while this solution can always be replaced by solution (A) with at most the same number of followers. Adding an edge to a vertex in N is not worthwhile, since we suppose each of the resulting b sets contains at least 2 elements. Thus, the edge k-core problem always chooses b of the Mi in G which corresponds to b sets in the MC problem. If there is a polynomial time solution for the edge k-core problem, the MC problem will be solved in polynomial time.

Theorem 2. For k ≥ 3 and any ϵ > 0, the edge k-core problem cannot be approximated in polynomial time within a ratio of (1 - 1/e + ϵ), unless P = NP .

Proof. We reduce from the MC problem using a reduction similar to that in the proof of Theorem 1. For any ϵ > 0, the MC problem cannot be approximated in polynomial time within a ratio of (1 - 1/e + ϵ), unless P = NP [Feige, 1998]. Let p be an arbitrarily large constant. There are two differences in the construction of G: (i) Q is a p-clique; and (ii) every vi is attached by a loop of p vertices where each vertex is connected to Q by k - 2 edges except vi. Let γ > 1-1/e, if there is a solution with γ-approximation on optimal follower number for the edge k-core problem, there will be a λ-approximate solution on optimal element number for MC, where λ = γ+ (γ-1)×b(d+3) p×f and f is the number of followers of edge k-core problem. Thus, the theorem is proved. The edge k-core problem is APX-hard.

Theorem 3. Let f(A) = |F(A)|. We have that f is not submodular for k ≥ 2.

Algorithm 1 NaiveEKC

Input: G: a graph, k: degree constraint, b: budget Output: a set A of anchor edges

• 1: A← ∅; Ck ←Ck(G)
• 2: for i from 1 to b do
• 3: for each e ∈ (V2 ) \ {E ∪ A ∪ (V (Ck) 2 )} do
• 4: compute F (e, G + A);
• 5: end for
• 6: e∗ ← the edge with most followers;
• 7: A←A∪ e∗ ; Ck ←Ck(G+A);
• 8: end for
• 9: return A

Proof. For two arbitrary collapsers sets A and B, if f is submodular, it must hold that f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B). Let Q1 be a (k+1)-clique where vertices u and v are contained. Let Q2 be another (k+1)-clique. We create a vertex w and connect it to the vertices in Q2 by k - 2 edges. If A = (u,w) and B = (v,w), f(A) + f(B) = 0 < f (A ∪ B) + f (A ∩ B) = 1.

5 Solution

Due to the NP-hardness and inapproximability of the problem, we resort to a greedy heuristic which iteratively finds the best anchor, i.e., the edge with the largest number of followers. The framework of the greedy algorithm is shown in Algorithm 1. At Line 4, we compute the followers for each candidate anchor edge in the complement graph of G, except the anchored edges in A and the edges between the k-core vertices. Note that adding an edge between two (nonadjacent) k-core vertices cannot enlarge the k-core, because all the non-k-core vertices will still be deleted in k-core computation. After the computation for every candidate anchor edge, the best anchor is chosen at Line 6, and the k-core is updated by inserting the anchor edge. The time complexity of Algorithm 1 is O(b × n2 × m). As we do not explicitly record the candidate edges, the space complexity of Algorithm 1 is O(m).

5.1 Optimizations on Each Iteration

In this section, we introduce optimization techniques for the first iteration of the greedy algorithm, i.e., the edge k-core problem with b = 1. They can be immediately applied to other iterations by replace the k-core of G by the edge k-core of G + A.

Basic Candidate Pruning

The following theorem locates the scope of valid candidate anchors where each edge has at least one follower.

Theorem 4. Given a graph G, if a candidate edge e = (u, v) has at least one follower, we have that u ∈ Ck-1(G) and v ∈ Ck-1(G), where at least one of u and v is in Hk-1(G).

Proof. Suppose u /∈ Ck-1(G). We have e ∈ Ck(Ge); otherwise, we have Ck(Ge) = Ck(G), i.e., there is no follower of e. If we remove e from Ck(Ge), then deg(u,Ck(Ge) \ {e}) and deg(v, Ck(Ge) \ {e}) are at least k -1, because (u, v) ∈

Ck(Ge) and their degrees decrease by 1. Thus, Ck(Ge) \ {e} ⊆ Ck-1(G) which contradicts with u /∈ Ck-1(G). Now we have proved that u ∈ Ck-1(G) and v ∈ Ck-1(G). Suppose that {u, v} ∈ Ck(G) and Ck(Ge)\Ck(G) = F ̸= ∅, we have that Ck(Ge) \ {e} belongs to Ck(G), which contradicts with F /∈ Ck(G).

Example 2. In Figure 3, when k = 3, the 3-core C3(G) is induced by {v0, v1, v5, v6}, and the 2-shell H2(G) = {v2, v3, v7, v8}. According to Theorem 4, we only need to consider every new edge (u, v) or (v, u) with u ∈ H2(G) and v ∈ V (C2(G)) = V (C3(G)) ∪ H2(G), as candidates.

Onion Layer based Candidate Pruning

Given the (k-1)-core of G, the computation of k-core on G recursively deletes some vertices in the (k-1)-core. The vertices are deleted in batch as their degrees are less than k at a same time, like peeling an onion [Zhang et al., 2017c; Zhang et al., 2017a]. The first layer of the onion, denoted by L1, consists of the vertices in (k-1)-core with degree less than k, i.e., L1 = {u | deg(u,Ck-1(G)) < k}. The deletion of the first layer vertices may decrease the degrees of other vertices, and produces the second layer. Recursively, we have that Li = {u | deg(u,Gi) < k} where Gi = Ck-1(G) - G[∪1≤j<iLj ].

Let l(u) denote the layer index of u, i.e., u ∈ Ll(u). If l(u) < l(v), we say u is at a lower layer of v, or v is at a higher layer of u. We use L to denote the union of layers, i.e., L = ∪1≤i≤sLi where s = max({l(u) | u ∈ Hk-1(G)}). Let d∗ (u) denote the number of adjacent neighbors of u in higher layers and k-core, i.e., d∗ (u) = deg(u,G′ ) where G′ = Ck-1(G) - G[{∪1≤i≤l(u)Li} \ u].

Benefit from L, we propose an effective pruning technique.

Theorem 5. Given a graph G, if a candidate edge e = (u, v) has at least one follower, we have that (i) d∗ (u) = k-1 when l(u) < l(v), (ii) d∗ (v) = k - 1 when l(v) < l(u), and (iii) d∗ (u) = d∗ (v) = k - 1 when l(u) = l(v);

Proof. Let O be the vertex deletion order of computing the k-core on the (k-1)-core. We have d∗ (u) ≤ k - 1 and d∗ (v) ≤ k - 1, since u and v are deleted at their layers in O, respectively. When l(u) < l(v), we suppose d∗ (u) < k - 1. The anchoring of (u, v) increases the degrees of u and v by 1, if we use the same order O to compute the k-core again, then d∗ (u) ≤ k - 1 < k, i.e., every vertex will be deleted at the same position of the order O, including u and v. It contradicts with e = (u, v) has at least one follower. Thus, case (i) and (ii) are proved. When l(u) = l(v), we suppose d∗ (u) < k-1 without loss of generality. If we use the same order O to compute the k-core again with the anchored edge e, u will be deleted at the same position since d∗ (u) < k. So v can't survive after the next batch of deletions since d∗ (v) < k. Finally, every vertex will be deleted.

Example 3. In Figure 3, when k = 3, layer 1 contains v3 and v8, and layer 2 contains v2 and v7. By theorem 5, (v2, v7) is not a promising candidate edge because d∗ (v7) = 1, but (v3, v8) is a proper candidate edge.

Note that if l(u) ≤ l(v), in the k-core computation with anchor e, the survive of u may preserve some vertices before visiting v. Thus, in Theorem 5, there is no degree requirement for v to ensure that e = (u, v) has at least one follower.

Onion Layer based Follower Computation

A naive follower computation is to directly apply the k-core computation on the graph with the existence of an anchor. An improved idea is to use the core maintenance algorithms, which update the k-core for every k with the addition of an edge [Zhang et al., 2017c]. For the edge k-core algorithm, we only need to update the k-core of a given k with an anchor edge. Thus, we adopt and refine the follower computation in the vertex-anchored k-core algorithm (OLAK) which is shown to be more efficient than core maintenance for kcore update with a fixed k [Zhang et al., 2017a].

In OLAK, anchoring a vertex means the degree of the vertex is infinitely large. There is an observation that a vertex u is the follower of the anchor vertex x if there is a path x ⇝ u based on neighboring relations, and l(y) < l(z) for every two consecutive vertices y and z along the path. This indicates that we do not need to consider the vertices without such paths in the follower computation. Different from anchored k-core problem, edge k-core problem requires us to add a new edge, where the vertex degree is increased by exactly 1, and we have to consider two vertices rather than one.

In our algorithm, given an anchor edge (u, v) with l(u) < l(v), we generate candidate followers layer-by-layer through activating the neighbors at higher layers, starting from the layer of u. Here u is the first activated vertex and only the activated vertices can activate their neighbors at higher layers. In this activation procedure, each activated vertex is assigned an upper bound of its degree in the edge k-core. The degree upper bound of a vertex u is generated by counting its neighbors in higher layers and the activated neighbors of u at other layers. Once the degree upper bound of a vertex is less than k, it will be deleted immediately and the upper bounds of its neighbours will be decreased by 1. The follower computation is complete when the layer-by-layer activation is finished. Note that the two vertices incident to the anchor edge may also be deleted in this procedure. Once one of them is deleted, there is no follower and the computation is returned.

Follower based Candidate Pruning

We can further prune some candidate edges by known results, when we retrieve the followers of some candidate edges.

Theorem 6. Given a candidate anchor edge e1 = (u1, v1) and its follower set F(e1), we have F(e) ⊆ F(e1) for every candidate edge e ∈ {(u, v) | u ∈ F(e1) and v ∈ F(e1) ∪ Ck(G) and u ̸= v}.

Algorithm 2 EKC

Input: G: a graph, k: degree constraint, b: budget Output: A set A of anchor edges

• 1: A← ∅;
• 2: for i from 1 to b do
• 3: N ← {(u, v) | u ∈ Hk-1(G + A), v ∈ Ck-1(G + A)} \ E(Ck-1(G + A)) (Theorem 4);
• 4: compute L and filter N based on Theorem 5;
• 5: for each e ∈ N do
• 6: F(e) ←FindFollower(e,L) (Section 5.1);
• 7: update N based on Theorem 6;
• 8: end for
• 9: e∗ ← the edge with most followers; A←A∪ e∗ ;
• 10: update N (Section 5.2);
• 11: end for
• 12: return A

Proof. Let e = (u, v). If F(e) is not empty, then Ck(Ge) contains Ck(G), u, v and F(e). Because Ck(Ge1 ) contains u and v, i.e., more vertices may be added to Ck(Ge) after anchoring e1. So, V (Ck(Ge)) ⊆ V (Ck(Ge1 )) and thus F(e) ⊆ F(e1).

Example 4. In Figure 3, when k = 3, if we get that v2 and v7 are the followers of edge (v3, v8). According to Theorem 6, the followers of (v2, v7) are also the followers of (v3, v8), thus (v2, v7) is not a promising candidate in current iteration.

5.2 Reusing Intermediate Results across Iterations

When one iteration of the greedy algorithm is completed, we get the best anchor edge A and the number of followers for every candidate edge in this iteration. These results can be reused since some connected components in the induced subgraph of (k-1)-shell may keep the same topology after anchoring an edge. For each connected component S where none of the vertices are incident to the anchor A, we can record the largest number of followers of one candidate anchor in S, for the later iterations. For the connected component(s) S where there is a vertex incident to the anchor A, it is hard to reuse the results because the addition of edges may largely change the vertex deletion order and the layer structure in k-core computation.

5.3 EKCAlgorithm

We present the EKC algorithm in Algorithm 2, which optimizes the greedy algorithm by adopting all the proposed techniques. At Line 3, the candidate edge set is restricted to N according to Theorem 4. In Line 4, we compute the onion layers of G and then exclude the candidates based on Theorem 5. The follower computation of a candidate edge is conducted by exploring L layer-by-layer, as introduced in Section 5.1. The set N is further filtered by Theorem 6 once a follower computation is completed. After each iteration, we get the anchor edge with the most followers. The algorithm terminates after b iterations.

The resulting set of b anchors is same to that in Algorithm 2. The correctness is guaranteed by the correctness of optimization techniques. The worst-case time complexity and space complexity are same to Algorithm 1.

6 Evaluation

Algorithms. As far as we know, there is no existing algorithm for the edge k-core problem on general graphs. In the experiment, we implement and evaluate 11 algorithms as shown in Table 2, where the bottom 6 algorithms produce the same result, because they use the same greedy heuristic and candidate visiting order.

Datasets. Flickr is from http://networkrepository.com/, and the others are from https://snap.stanford.edu/data/. Table 3 shows the statistics of the datasets.

Settings. All programs are implemented in C++. All experiments are performed on Intel Xeon 2.20GHz CPU and Linux System. We vary the parameters k and b.

6.1 Effectiveness

Figure 4 reports the number of followers w.r.t. b anchors. For random approaches, we report the average number of followers for 100 independent tests. In Figure 4, Degree and Layer failed to get any followers in more than half of the datasets, because a large degree vertex or a vertex in higher onion layer does not necessarily have a follower. A totally random algorithm cannot get any followers in most settings. Thus, in Rand, we only choose the edges from the set where each edge has at least one follower. We observe that the majority of the candidate edges does not have any followers, while our greedy heuristic always finds effective anchors in the experiments. In Figure 4, we notice that EKC preserves more than 100 followers in Flickr with only 5 anchors.

We also compare the performance of EKC with the optimal solution from Exact. Due to extremely high cost, we run Exact on an induced subgraph by 50 random vertices. The results are from 100 independent settings. The values of k and b are small due to the small-scale of data. Figure 5 shows that the margins between EKC and Exact are not unacceptable, considering the non-submodular property and the significantly better efficiency of EKC.

Figure 6 shows that EKC produces similar and almost larger numbers of followers than AKC where the meaning of b is different: the former for edges and the latter for vertices. Although the anchoring of one vertex means the preserving of many edges, EKC can produce similar followers with one anchor edge. It shows that the edge k-core can enlarge the k-core with less graph manipulations.

6.2 Efficiency

Figure 7 reports the performance of three algorithms on all the datasets with k = 20 and b = 5. The datasets are ordered by the number of edges. We find the runtime among different datasets is largely influenced by the characteristics of datasets and the onion layer structures in k-core computation. Baseline cannot finish computation on 4 datasets within one week. BL+OF significantly improve the performance by applying a series of techniques. EKC performs even better given all the optimizations.

In Figure 8, we report the number of candidate edges of different algorithms by incrementally adding techniques, where the details of each algorithms is given in Table 3. We can see the improvement brought by each proposed technique.

Figure 9 studies the impact of k and r. Figure 9(a) shows that the runtime decreases with a larger input of k. This is because the number of candidate edges become fewer with a larger k. Figure 9(b) reports the runtime with an increasing b, which is proportional to the value of b. The margin between BL+OF and EKC becomes smaller with a larger k, because the number of connected components becomes less when k increases. It is reported that EKC largely outperforms the other algorithms under all the settings.

7 Conclusion

In this paper, we investigate the problem of edge k-core, which aims to add a set b of edges in a network such that the size of the resulting k-core is maximized. We prove the problem is NP-hard and APX-hard. An efficient algorithm, named EKC, is proposed with novel optimizations. Extensive experiments on 9 real-life datasets are conducted to demonstrate our model is effective and our algorithm is efficient.

Acknowledgments

Xuemin Lin is supported by 2019DH0ZX01, 2018YFB10035 04, NSFC61232006, ARC DP180103096 and DP170101628. Wenjie Zhang is supported by ARC DP180103096.