An Efficient Algorithm for the Anchored k-Core Budget Minimization Problem

Online social networking companies devote much effort to maximize the engagement of users. Most existing methods assume that the budget is already known and focus on heuristic solutions to maximize the number of users that keep engaged. However, many real-life applications aim to keep the engagement of the majority of users in the social network. In such scenarios, the budget is flexible, and the goal is to minimize the budget used to keep these users active. In this paper, we define and study the anchored k-core budget minimization problem. Given an undirected graph G, a degree constraint k and a quota q for engaged users, this problem aims to minimize the budget that assures at least q users not in k-core keeping engaged.We propose CLOCK, an efficient greedy algorithm to solve the anchored k-core budget minimization problem. The main idea is to delete the anchored vertex with the lowest score in every iteration while maintaining the required number of engaged users. By considering the influence among the anchored vertices, a scoring function is well designed to identify the anchored vertices with high quality. Then we propose two merging strategies to get better anchored vertices. In addition, we dynamically maintain all anchored vertices by a local update strategy which avoids many redundant calculations. Finally, we conduct extensive experiments on real world datasets, demonstrating the effectiveness and efficiency of CLOCK.