  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 adopt the information, observing individual
transmissions (i.e., 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.
  We demonstrate the effectiveness of our approach by tracing information
diffusion in a set of 170 million blogs and news articles over a one year
period to infer how information flows through the online media space. We find
that the diffusion network of news for the top 1,000 media sites and blogs
tends to have a core-periphery structure with a small set of core media sites
that diffuse information to the rest of the Web. These sites tend to have
stable circles of influence with more general news media sites acting as
connectors between them.
