Phase Transition in the Maximal Influence Problem: When Do We Need Optimization?
arXiv:1708.02142
Abstract
Considerable efforts were made in recent years in devising optimization algorithms for influence maximization in networks. Here we ask: "When do we need optimization?" We use results from statistical mechanics and direct simulations on ER networks, small-world networks, power-law networks and a dataset of real-world networks to characterize the parameter-space region where optimization is required. We show that in both synthetic and real-world networks this optimization 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 then show that also from a utility-maximization perspective (when considering the costs of the optimization process), for large networks standard optimization is profitable only in a vanishing parameter region near the phase transition. Finally, we introduce a novel 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.
References in corpus (6)
- Statistical mechanics of complex networks
- Random graphs with arbitrary degree distributions and their applications
- Network robustness and fragility: Percolation on random graphs
- Social Percolation
- Containing epidemic outbreaks by message-passing techniques
- ERA: A Framework for Economic Resource Allocation for the Cloud