VEK: a vertex-oriented approach for edge k-core problem

The stability of a network has been widely studied as an important indicator of network status, e.g., reliability and activity. A popular model for measuring the (structural) stability of a network is k-core , the maximal induced subgraph in which every vertex has at least k neighbors in the subgraph. As the size of k-core well estimates the stability of a network, the edge k-core problem is studied to enhance network stability: given a graph G, an integer k and a budget b, add b edges to non-adjacent vertex pairs in G such that the number of vertices in the k-core is maximized. The state-of-the-art solution is a greedy algorithm (named EKC) by finding a promising vertex pair at each iteration, while the algorithm is still not efficient enough on large graphs. In this paper, we propose a novel vertex-oriented heuristic algorithm (named VEK), with a well-designed scoring function to guide the search order. Effective optimization techniques are proposed to prune unpromising candidates and reuse the intermediate results. The experiments on 9 real-life datasets demonstrate the runtime of our proposed VEK is faster than the state-of-the-art algorithm EKC by 1-3 orders of magnitude.