K-Core Minimization: A Game Theoretic Approach

Understand

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.