Inferring networks of diffusion and influence
By Manuel Gomez-Rodriguez, Jure Leskovec, Andreas Krause. 2010
1,165 citations recorded by the source corpus.
Information diffusion and virus propagation are fundamental processes talking place in networks. While it is often possible to directly observe when nodes become infected, 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 in practice gives provably near-optimal performance. We demonstrate the effectiveness of our approach by tracing information cascades 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 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.
Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Causal Inference & Discovery, Network Science & Complex Systems
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Bernhard Schölkopf
- Yoshua Bengio
- Le Song
- Jure Leskovec
- Tat-seng Chua
- Xiangnan He
- Alex Smola
- Percy Liang
In Statistical and Nonlinear Physics
- Jure Leskovec
- Kristina Lerman
- Bernhard Schölkopf
- Manuel Gomez-Rodriguez
- Filippo Menczer
- Le Song
- Alessandro Flammini
- Edith Cohen
In Causal Inference & Discovery
- Bernhard Schölkopf
- Manuel Gomez-Rodriguez
- Eliav Buchnik
- Edith Cohen
- Jure Leskovec
- Le Song
- Manuel Gomez Rodriguez
- Nan Du
In Network Science & Complex Systems
- Eliav Buchnik
- Edith Cohen
- Bernhard Schölkopf
- Manuel Gomez-Rodriguez
- Le Song
- Jure Leskovec
- Bistra N. Dilkina
- Elias Boutros Khalil
Citations in the corpus
- Learning Combinatorial Optimization Algorithms over Graphs (2017, background): “The network is learned from real traces in [13], having 960 nodes and 5000 edges.”
- Scalable Influence Estimation in Continuous-Time Diffusion Networks (2013, background): “3]), which mimic the information diffusion traces in real world networks [21], (ii) random networks ([0.”
- Supervised random walks: predicting and recommending links in social networks (2010, background): “For example, the network inference problem [13, 24] can be cast as a link prediction problem where no knowledge of the network is given.”
- Process (2020, background): “Existing work in discrete event modeling using point processes, such as [23, 24, 25, 26], often make strong assumptions and specify a parametric form of the intensity functions.”
- Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity (2018, methodology): “reach diffusion) or the length (with distance diffusion) of edges [12, 13, 17, 19, 23] and then works with respective expectations.”
- Truthy: mapping the spread of astroturf in microblog streams (2010, background): “propose an algorithm that can efficiently approximate linkage information based on the times at which specific URLs appear in a network of news sites [19].”
- Uncovering the Temporal Dynamics of Diffusion Networks (2011, methodology): “…and propagation processes have received increasing attention in a broad range of domains: information propagation (Adar & Adamic, 2005; Gomez-Rodriguez et al., 2010; Meyers & Leskovec, 2010), social networks (Kempe et al., 2003; Lappas et al., 2010), viral marketing (Watts & Dodds, 2007)…”
- The role of social networks in information diffusion (2012, background): “[4, 9, 8, 15, 16, 19, 20, 25, 29, 36, 43]).”
- Learning Graphs From Data: A Signal Representation Perspective (2018, background): “W A similar model is considered in [7], in which the conditional transmission probabilities are taken to be the same on all edges, i.”
- Social big data: Recent achievements and new challenges (2015, methodology): “The NETINT method [78] has applied sub-modular, function-based iterative optimisation to discover the spreading cascade (path) that maximises the likelihood of the collected dataset.”
- Influence Maximization in Continuous Time Diffusion Networks (2012, methodology): “The exponential model is a well-known parametric model for modeling diffusion and influence in social and information networks (Gomez-Rodriguez et al., 2010).”
- Quantifying Information Overload in Social Media and Its Impact on Social Contagions (2014, background): “The temporal dynamics of information propagation, and in particular, the speed at which information propagates depends crucially on the time users take to process the information they receive and determine if they would like to forward it to other users (Gomez-Rodriguez, Balduzzi, and Schölkopf 201”
- Microscopic Social Influence (2012, background): “, homophily and confounding) and social influence on users’ activities [4], verifying the existence of correlation between personal behavior and social connection [5], finding the most influential nodes in social networks [6, 7], estimating the influence strength of social ties [8], and inferring in”
- Maximizing Social Influence in Nearly Optimal Time (2012, background): “This is the idea behind word-ofmouth advertising, in which information about a product travels via links between individuals; see, for example [35, 8, 17, 9, 3, 10, 19].”
- Who says what to whom on twitter (2011, background): “In this sense, it is related to recent work by Crane and Sornette [5], who posited a mathematical model of social influence to account for observed temporal patterns in the popularity of YouTube videos, and also to Gomez et al [7], who studied the diffusion of information among blogs and online news”
- Streaming submodular maximization: massive data summarization on the fly (2014, background): “Over the recent years, submodular optimization has been identified as a powerful tool for numerous data mining and machine learning applications including viral marketing [17], network monitoring [22], news article recommendation [10], nonparametric learning [14, 29], document and corpus summarizati”