Maximizing resilience in large-scale social networks

Motivated by the importance of social resilience as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph G=(V,E) and integers k and b, the maximum anchored k-core problem seeks to find a largest subset of vertices S that induces a subgraph with at least |S|-b vertices of degree at least k. We introduce a new integer programming (IP) formulation for the maximum anchored k-core problem, and conduct a polyhedral study on the polytope of the problem. We show the linear programming relaxation of the proposed IP model is at least as strong as that of a naive formulation. We also identify facet-defining inequalities of the IP formulation. Furthermore, we develop inequalities and fixing procedures to improve the computational performance of our IP model. We use benchmark instances to compare the computational performance of the IP model with (i) the naive IP formulation and (ii) two existing heuristic algorithms. Our proposed IP model can optimally solve half of the benchmark instances that cannot be solved to optimality either by the naive model or the existing heuristic approaches.



View Maximizing resilience in large-scale social networks