Optimal Interventions on the Linear Threshold Model in Large-Scale Networks
For social planners or network influence practitioners, this provides a computationally feasible method for large-scale networks where only statistical knowledge is available, though the solution is approximate.
The paper tackles the NP-hard problem of designing minimal-cost interventions on the linear threshold model to ensure a predefined fraction of agents reaches a given state. It proposes an approximate solution using a local mean-field approximation, reformulating the problem as a linear program with infinite constraints, and then approximating it with finite constraints. Numerical experiments on real-world networks validate the approach.
We study an optimal intervention problem on the linear threshold model (LTM) in which a social planner aims to design minimal-cost interventions that modify the agents' thresholds, under the constraint that at least a predefined fraction of agents reaches a given state after a finite number of iterations. While this problem is known to be NP-hard and its exact solution requires full knowledge of the network structure, we focus on approximate solutions for large-scale networks and assume that the planner has only statistical knowledge of the network. In particular, we build on a local mean-field approximation of the LTM that is known to hold true on large-scale random networks, and reformulate the optimal intervention problem as a linear program with an infinite set of constraints. We then show how to approximate the solutions of the latter problem by standard linear programs with finitely many constraints. Finally, our approach is validated through numerical experiments on real-world networks and compared both with optimal seeding and state-of-the-art algorithms for the least-cost influence.