Candidate Intermediary Node Deployment Under the Linear Threshold Model: A Branch-and-Benders-Cut Approach

Abstract

This paper studies candidate intermediary node deployment for influence diffusion under the linear threshold model (LTM). Given fixed diffusion sources, target nodes, and a budget, the decision maker selects candidate intermediary nodes to maximize the expected total weight of activated targets. Once deployed, a candidate node enables its associated potential arcs whose other endpoints belong to the effective network. Using the LTM live-arc representation, we establish distributional equivalence between sampling on the potential graph and then restricting each scenario to the deployed induced network, and sampling directly on the deployed network. This leads to a finite-scenario sample-average approximation (SAA) mixed-integer formulation based on canonical live paths; the resulting deployment objective is monotone and supermodular but is generally not submodular, so the classical greedy-approximation guarantee for monotone submodular maximization does not apply in general. Since the compact SAA formulation contains many scenario–target variables and covering constraints, solving the formulation directly can be computationally demanding. We therefore propose a scenario-decomposed branch-and-Benders-cut algorithm that solves the finite-scenario SAA model to optimality. Each scenario subproblem is separable by target and has a closed-form dual optimum, so Benders cuts are separated by scanning required-node sets rather than solving linear programs inside callbacks. On five real networks and 225 SAA instances, the algorithm solves all instances within one hour, averaging 27.46 s; the compact SAA formulation solves 172 instances, with an average capped time of 1444.11 s.