Network Inference and Influence Maximization from Samples
  Influence maximization is the task of selecting a small number of seed nodes
in a social network to maximize the influence spread from these seeds. It has
been widely investigated in the past two decades. In the canonical setting, the
social network and its diffusion parameters are given as input. In this paper,
we consider the more realistic sampling setting where the network is unknown
and we only have a set of passively observed cascades that record the sets of
activated nodes at each diffusion step. We study the task of influence
maximization from these cascade samples (IMS) and present constant
approximation algorithms for it under mild conditions on the seed set
distribution. To achieve the optimization goal, we also provide a novel
solution to the network inference problem, that is, learning diffusion
parameters and the network structure from the cascade data. Compared with prior
solutions, our network inference algorithms require weaker assumptions and do
not rely on maximum-likelihood estimation and convex programming. Our IMS
algorithms enhance the learning-and-then-optimization approach by allowing a
constant approximation ratio even when the diffusion parameters are hard to
learn, and we do not need any assumption related to the network structure or
diffusion parameters.
