A Scalable Markov Chain Framework for Influence Maximization in Arbitrary Networks

Juan S. Borrero, Majid Akhgar, Pavlo A. Krokhmal

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)2372-2387
Number of pages16
JournalIEEE Transactions on Network Science and Engineering
Issue number3
StatePublished - Jul 1 2021


  • Influence maximization
  • Markov Chains
  • convex optimization
  • cutting planes
  • minimum cut

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'A Scalable Markov Chain Framework for Influence Maximization in Arbitrary Networks'. Together they form a unique fingerprint.

Cite this