A Scalable Markov Chain Framework for Influence Maximization in Arbitrary Networks

We consider a Markov chain model of influence in a network where inactive nodes can be activated by their active in-neighbors or by external factors. The activation time is a random variable whose parameters, or influence rates, depend on control variables whose values can be changed by the decision-maker (DM) seeking to allocate her limited budget to minimize the time until all nodes are active. We show that the optimization of either the expectation or the tail probabilities of the network activation time (NAT) is an intractable (EXPTIME) problem. Thus, we focus on a stochastic upper bound on the NAT and show that both its expectation and tail probabilities are minimized when the Markov chain's minimum sojourn rate is maximized. We provide performance guarantees for the network activation time optimization problem (NATP) with respect to the optimization of the expectation problem and show that the NATP becomes an efficiently solvable convex optimization problem when we have concave influence rates and a convex cost function. We also provide an efficient cut generation algorithm, which can solve many synthetic and real-life instances with more than 104 nodes and 105 arcs in times ranging from a few seconds to a few minutes.