  In social networks, information and influence diffuse among users as
cascades. While the importance of studying cascades has been recognized in
various applications, it is difficult to observe the complete structure of
cascades in practice. Moreover, much less is known on how to infer cascades
based on partial observations. In this paper we study the cascade inference
problem following the independent cascade model, and provide a full treatment
from complexity to algorithms: (a) We propose the idea of consistent trees as
the inferred structures for cascades; these trees connect source nodes and
observed nodes with paths satisfying the constraints from the observed temporal
information. (b) We introduce metrics to measure the likelihood of consistent
trees as inferred cascades, as well as several optimization problems for
finding them. (c) We show that the decision problems for consistent trees are
in general NP-complete, and that the optimization problems are hard to
approximate. (d) We provide approximation algorithms with performance
guarantees on the quality of the inferred cascades, as well as heuristics. We
experimentally verify the efficiency and effectiveness of our inference
algorithms, using real and synthetic data.
