Learnability of Influence in Networks

We show P AC learnability of influence functions for three common influence models, namely, the Linear Threshold (L T), Independent Cascade (IC) and V oter models, and present concrete sample complexity results in each case. Our results for the L T model are based on interesting connections with neural networks; those for the IC model are based an interpretation of the influence function as an expectation over random draw of a subgraph and use covering number arguments; and those for the V oter model are based on a reduction to linear regression. We show these results for the case in which the cascades are only partially observed and we do not see the time steps in which a node has been influenced. We also provide efficient polynomial time learning algorithms for a setting with full observation, i.e.