Inferring Networks of Diffusion and Influence
Abstract
Information diffusion and virus propagation are fundamental processes taking place in networks. While it is often possible to directly observe when nodes become infected with a virus or publish the information, observing individual transmissions (who infects whom, or who influences whom) is typically very difficult. Furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved. We tackle these challenges by developing a method for tracing paths of diffusion and influence through networks and inferring the networks over which contagions propagate. Given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. Since the optimization problem is NP-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and finds provably near-optimal networks.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Feb 01, 2012
- Source ID
- 10.1145/2086737.2086741
Entities
People
- Andreas Krause
- Jure Leskovec
- Manuel Gomez-rodriguez
Organizations
- Air Force Research Laboratory
- Division of Computer and Network Systems
- Division of Information and Intelligent Systems
- ETH Zurich
- Office of Naval Research
- Stanford University