Adaptivity Gaps for Influence Maximization: Percolation and DepletionResearch Paper
In influence maximization one selects at most vertices of a network, the seeds, so as to maximize the expected number of vertices reached by a random cascade started from them. Kempe, Kleinberg and Tardos (KKT03) introduced the independent cascade model, in which every arc of the network is live independently with a known probability, and showed that the…