Stochastic Dynamic Programming Heuristics for Influence
  Maximization-Revenue Optimization
  The well-known Influence Maximization (IM) problem has been actively studied
by researchers over the past decade, with emphasis on marketing and social
networks. Existing research have obtained solutions to the IM problem by
obtaining the influence spread and utilizing the property of submodularity.
This paper is based on a novel approach to the IM problem geared towards
optimizing clicks and consequently revenue within anOnline Social Network
(OSN). Our approach diverts from existing approaches by adopting a novel,
decision-making perspective through implementing Stochastic Dynamic Programming
(SDP). Thus, we define a new problem Influence Maximization-Revenue
Optimization (IM-RO) and propose SDP as a method in which this problem can be
solved. The SDP method has lucrative gains for an advertiser in terms of
optimizing clicks and generating revenue however, one drawback to the method is
its associated "curse of dimensionality" particularly for problems involving a
large state space. Thus, we introduce the Lawrence Degree Heuristic (LDH),
Adaptive Hill-Climbing (AHC) and Multistage Particle Swarm Optimization (MPSO)
heuristics as methods which are orders of magnitude faster than the SDP method
whilst achieving near-optimal results. Through a comparative analysis on
various synthetic and real-world networks we present the AHC and LDH as
heuristics well suited to to the IM-RO problem in terms of their accuracy,
running times and scalability under ideal model parameters. In this paper we
present a compelling survey on the SDP method as a practical and lucrative
method for spreading information and optimizing revenue within the context of
OSNs.
