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

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 ≥ 3.