Edge Manipulation Approaches for K-core Minimization: Metrics and Analytics
Chen Chen, Qiuyu Zhu, Renjie Sun, Xiaoyang Wang, Yanping Wu
Abstract
In social networks, dense relationships among users contribute to stable communities. Breakdowns of critical connections may cause users to leave the group. A popular model to measure the cohesiveness of a network is k-core or coreness. To identify important connections, in this paper, we propose and investigate the problem of k-core minimization problem under three different metrics. Specifically, given a graph G and a budget b, we aim to retrieve a set B of b edges for deletion purpose, which can minimize i) the number of nodes in the collapsed k-core (KNM), ii) the number of edges in the collapsed k-core (KEM), and iii) the overall coreness decreased in the target node set P (KCM). We first formally define the problems and prove that the three problems are all NP-hard. Then, a baseline greedy searching framework is developed. To scale for large graphs, optimized algorithms are developed by integrating novel pruning strategies and group-based structures. Finally, comprehensive experiments on 6 real social networks are conducted to demonstrate the efficiency and effectiveness of our proposed models and methods.