Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: K-Core Minimization: A Game Theoretic Approach   K-cores are maximal induced subgraphs where all vertices have degree at least
k. These dense patterns have applications in community detection, network
visualization and protein function prediction. However, k-cores can be quite
unstable to network modifications, which motivates the question: How resilient
is the k-core structure of a network, such as the Web or Facebook, to edge
deletions? We investigate this question from an algorithmic perspective. More
specifically, we study the problem of computing a small set of edges for which
the removal minimizes the $k$-core structure of a network. This paper provides
a comprehensive characterization of the hardness of the k-core minimization
problem (KCM), including innaproximability and fixed-parameter intractability.
Motivated by such a challenge in terms of algorithm design, we propose a novel
algorithm inspired by Shapley value -- a cooperative game-theoretic concept --
that is able to leverage the strong interdependencies in the effects of edge
removals in the search space. As computing Shapley values is also NP-hard, we
efficiently approximate them using a randomized algorithm with probabilistic
guarantees. Our experiments, using several real datasets, show that the
proposed algorithm outperforms competing solutions in terms of k-core
minimization while being able to handle large graphs. Moreover, we illustrate
how KCM can be applied in the analysis of the k-core resilience of networks.

16
The categories of this paper are: stat
15
The categories of this paper are: nucl-ex
19
The categories of this paper are: eess
27
The categories of this paper are: comp-gas
12
The categories of this paper are: nucl-th
14
The categories of this paper are: math-ph
10
The categories of this paper are: q-bio
36
The categories of this paper are: cmp-lg
13
The categories of this paper are: quant-ph
32
The categories of this paper are: atom-ph
9
The categories of this paper are: nlin
11
The categories of this paper are: hep-lat
35
The categories of this paper are: mtrl-th
34
The categories of this paper are: chem-ph
4
The categories of this paper are: cond-mat
6
The categories of this paper are: astro-ph