Gomez Rodriguez, M., J. Leskovec, and A. Krause. 2010. Inferring networks of diffusion and influence. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 1019–1028.

Online Version

An electronic version of this paper can be downloaded here: [1]

Summary

This paper addresses the problem of inferring structures of the underlying diffusion/propagation networks from the observed data, i.e. times when the contagion infect particular nodes in the graph . The main premise behind their proposed approach is that the joint observations of many different contagion-spreading processes could determine the underlying diffusion network, assuming that it does not change over time. The proposed algorithm is called NETINF, which formulates the contagion spread as directed trees through the network, and can reduce the complexity of searching an exponential set of candidate trees to polynomial time.

Results

For evaluation they apply the proposed approach to both synthetic data (including Forest Fire model and the Kronecker Graphs model) and real data (Blog hyperlink cascades dataset and MemeTracker dataset created from 172 million news articles and blog posts from 1 million online sources over a year).