Phase Transition in the Maximal Influence Problem: When Do We Need Optimization?

Considerable efforts were made in recent years in devising optimization algorithms for influence maximization in networks. Here we ask: "When do we need optimization?" and apply insights from statistical mechanics, and direct simulations, to characterize the parameter-space region where optimization is required. We find that this region is due to a well known physical phase transition of the network, and that it vanishes as a power-law with the network size. We show that also from a utility-maximization perspective (when considering the optimization costs), for large networks standard optimization is profitable only in a vanishing parameter region near the phase transition. Finally, we introduce a constant-time optimization approach, and demonstrate it through a simple algorithm that manages to give similar results to standard optimization methods in terms of the influenced-set size, while improving the results in terms of the net utility.