Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2012 | public
Journal Article

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. 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.

Additional Information

© 2012 ACM. Received December 2010; revised October 2011; accepted November 2011. This research was supported in part by the Albert Yu and Mary Benchmann Foundation, IBM, Lightspeed, Microsoft, Yahoo, grants ONR N00014-09-1-1044, NSF CNS0932392, NSF CNS1010921, NSF IIS1016909, NSF IIS0953413, AFRL FA8650-10-C-7058, and Okawa Foundation Research Grant. M. Gomez-Rodriguez has been supported in part by a Fundacion Caja Madrid Graduate Fellowship, by a Fundacion Barrie de la Maza Graduate Fellowship, and by the Max Planck Society. We thank Spinn3r for resources that facilitated the research.

Additional details

Created:
August 22, 2023
Modified:
October 24, 2023