Diffusion in networks is often modeled as a local neighbor-based process: a node becomes active as a result of influence exerted by its active neighbors. However, in many technological and communication settings, adoption is driven not only by local influence, but by access to sufficiently large active connected regions. This paper studies such component-based diffusion dynamics, focusing on the Technology Diffusion (TD) problem and on a related Influence Maximization (IM) problem described by the same propagation process.
We first analyze how some connectivity restrictions affect component-based diffusion and show that their impact can be bounded more tightly than earlier results in the literature suggested. We then propose exact integer programming formulations that are not based on the connected-activation-sequence paradigm, showing the importance of considering disconnected active sets. On the algorithmic side, we develop a zeroth-order approach, namely a component-aware direct search that does not require the diffusion trajectory to be a connected activation sequence. Computational experiments on a standard benchmark show that the proposed method improves solution quality over state-of-the-art approaches, and it scales to significantly larger instances than exact/approximation methods.