  This paper considers the problem of randomized influence maximization over a
Markovian graph process: given a fixed set of nodes whose connectivity graph is
evolving as a Markov chain, estimate the probability distribution (over this
fixed set of nodes) that samples a node which will initiate the largest
information cascade (in expectation). Further, it is assumed that the sampling
process affects the evolution of the graph i.e. the sampling distribution and
the transition probability matrix are functionally dependent. In this setup,
recursive stochastic optimization algorithms are presented to estimate the
optimal sampling distribution for two cases: 1) transition probabilities of the
graph are unknown but, the graph can be observed perfectly 2) transition
probabilities of the graph are known but, the graph is observed in noise. These
algorithms consist of a neighborhood size estimation algorithm combined with a
variance reduction method, a Bayesian filter and a stochastic gradient
algorithm. Convergence of the algorithms are established theoretically and,
numerical results are provided to illustrate how the algorithms work.
