Influence Maximization Over Markovian Graphs: A Stochastic Optimization Approach
- 30 April 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal and Information Processing over Networks
- Vol. 5 (1) , 1-14
Abstract
Depending on the initial adopters of an innovation, it can either lead to a large number of people adopting that innovation or, it might die away quickly without spreading. Therefore, an idea central to many application domains, such as viral marketing, message spreading, etc., is influence maximization: selecting a set of initial adopters from a social network that can cause a massive spread of an innovation (or, more generally an idea, a product or a message). To this end, we consider the problem of randomized influence maximization over a Markovian graph process: given a fixed set of individuals whose connectivity graph is evolving as a Markov chain, estimate the probability distribution (over this fixed set of nodes) that samples an individual that can 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 is established theoretically, and numerical results are provided to illustrate how the algorithms work.Keywords
All Related Versions
Funding Information
- Army Research Office (12346080)
- National Science Foundation (1714180)
This publication has 32 references indexed in Scilit:
- Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are UnknownSIAM Journal on Matrix Analysis and Applications, 2013
- Consistency of community detection in networks under degree-corrected stochastic block modelsThe Annals of Statistics, 2012
- Spectral clustering and the high-dimensional stochastic blockmodelThe Annals of Statistics, 2011
- Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate2011
- Broadcasting in dynamic radio networksJournal of Computer and System Sciences, 2009
- Assortative Mixing in NetworksPhysical Review Letters, 2002
- Recursive algorithms for estimation of hidden Markov models and autoregressive models with Markov regimeIEEE Transactions on Information Theory, 2002
- Size-Estimation Framework with Applications to Transitive Closure and ReachabilityJournal of Computer and System Sciences, 1997
- Multivariate stochastic approximation using a simultaneous perturbation gradient approximationIEEE Transactions on Automatic Control, 1992
- Why Your Friends Have More Friends Than You DoAmerican Journal of Sociology, 1991