While fractional versions of problems tend to be easier to solve than integral versions, for influence maximization, we show that the two versions have essentially the same computational complexity. On the other hand, the two versions can have vastly different solutions: the added flexibility of fractional allocation can lead to vastly improved influence. Our main theoretical contribution is to show how to adapt the major positive results from the integral case to the fractional case. Specifically, Mossel and Roch (2006) used the submodularity of influence to obtain their integral results; we introduce a new notion of continuous submodularity, and use this to obtain matching fractional results. We conclude that similar algorithms and heuristics from the integral case apply to the fractional case. In practice, we find that the fractional model performs substantially better than the integral model, according to simulations on real-world social network data.
The full paper is available as arXiv.org:1401.7970 of the Computing Research Repository (CoRR).