Edge Manipulation Approaches for K-Core Minimization: Metrics and Analytics

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.