Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem

Abstract

We consider a model of user engagement in social networks, where each player incurs a cost to remain engaged but derives a benefit proportional to the number of engaged neighbors. The natural equilibrium of this model corresponds to the $k$-core of the social network---the maximal induced subgraph with minimum degree at least $k$. We introduce the problem of “anchoring” a small number of vertices to maximize the size of the corresponding anchored $k$-core---the maximal induced subgraph in which every nonanchored vertex has degree at least $k$. This problem corresponds to preventing “unraveling''---a cascade of iterated withdrawals---and it identifies the individuals whose participation is most crucial to the overall health of a social network. We classify the computational complexity of this problem as a function of $k$ and of the graph structure. We provide polynomial-time algorithms for general graphs with $k=2$ and for bounded-treewidth graphs with arbitrary $k$. We prove strong inapproximability results for general graphs and $k \ge 3$.