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.