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

Short version appeared in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2010. Long version submitted to ACM Transactions on Knowledge Discovery from Data (TKDD)

Cited by in corpus (17)

• Learning Combinatorial Optimization Algorithms over Graphs
• Detecting and Tracking the Spread of Astroturf Memes in Microblog Streams
• Uncovering the Temporal Dynamics of Diffusion Networks
• Modeling Information Propagation with Survival Theory
• Influence Maximization in Continuous Time Diffusion Networks
• Affinity Paths and Information Diffusion in Social Networks
• Discovering Latent Network Structure in Point Process Data
• Submodular Inference of Diffusion Networks from Multiple Trees
• Inferring Graphs from Cascades: A Sparse Recovery Framework
• Universal Components of Real-world Diffusion Dynamics based on Point Processes
• Learning the Structure and Parameters of Large-Population Graphical Games from Behavioral Data
• Temporal scaling in information propagation
• Big data challenges for the social sciences: from society and opinion to replications
• Diffusion-Aware Sampling and Estimation in Information Diffusion Networks
• Sampling from Diffusion Networks
• Learning Network Structures from Contagion
• Learning Sentimental Influences from Users' Behaviors