  Influence maximization is among the most fundamental algorithmic problems in
social influence analysis. Over the last decade, a great effort has been
devoted to developing efficient algorithms for influence maximization, so that
identifying the ``best'' algorithm has become a demanding task. In SIGMOD'17,
Arora, Galhotra, and Ranu reported benchmark results on eleven existing
algorithms and demonstrated that there is no single state-of-the-art offering
the best trade-off between computational efficiency and solution quality.
  In this paper, we report a high-level experimental study on three
well-established algorithmic approaches for influence maximization, referred to
as Oneshot, Snapshot, and Reverse Influence Sampling (RIS). Different from
Arora et al., our experimental methodology is so designed that we examine the
distribution of random solutions, characterize the relation between the sample
number and the actual solution quality, and avoid implementation dependencies.
Our main findings are as follows: 1. For a sufficiently large sample number, we
obtain a unique solution regardless of algorithms. 2. The average solution
quality of Oneshot, Snapshot, and RIS improves at the same rate up to scaling
of sample number. 3. Oneshot requires more samples than Snapshot, and Snapshot
requires fewer but larger samples than RIS. We discuss the time efficiency when
conditioning Oneshot, Snapshot, and RIS to be of identical accuracy. Our
conclusion is that Oneshot is suitable only if the size of available memory is
limited, and RIS is more efficient than Snapshot for large networks; Snapshot
is preferable for small, low-probability networks.
