Maximizing the spread of influence through a social network
By David Kempe, Jon M. Kleinberg, É. Tardos. 2003
9,178 citations recorded by the source corpus.
Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies in game-theoretic settings, and the effects of "word of mouth" in the promotion of new products. Recently, motivated by the design of viral marketing strategies, Domingos and Richardson posed a fundamental algorithmic problem for such social network processes: if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target?We consider this problem in several of the most widely studied models in social network analysis. The optimization problem of selecting the most influential nodes is NP-hard here, and we provide the first provable approximation guarantees for efficient algorithms. Using an analysis framework based on submodular functions, we show that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models; our framework suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks.We also provide computational experiments on large collaboration networks, showing that in addition to their provable guarantees, our approximation algorithms significantly out-perform node-selection heuristics based on the well-studied notions of degree centrality and distance centrality from the field of social networks.
Subfields: Management Science and Operations Research, Statistical and Nonlinear Physics, 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 Management Science and Operations Research
- Jure Leskovec
- Yaochu Jin
- Jon M. Kleinberg
- Andreas Krause
- Ye Tian
- Xing-yi Zhang
- Francis R. Bach
- Ran Cheng
In Statistical and Nonlinear Physics
- Jure Leskovec
- Charu C. Aggarwal
- Jon M. Kleinberg
- Kristina Lerman
- Manuel Gomez-Rodriguez
- Bernhard Schölkopf
- Huan Liu
- Le Song
In Network Science & Complex Systems
- Jure Leskovec
- Eliav Buchnik
- Edith Cohen
- Bernhard Schölkopf
- Manuel Gomez-Rodriguez
- Kristina Lerman
- Charu C. Aggarwal
- Le Song
Citations in the corpus
- Learning Combinatorial Optimization Algorithms over Graphs (2017, background): “The SCP is also related to the diffusion optimization problem on graphs; for instance, the proof of hardness in the classical [20] paper uses SCP for the reduction.”
- Scalable Influence Estimation in Continuous-Time Diffusion Networks (2013, methodology): “Similarly, for LT, we follow the methodology by [1].”
- Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “We are by no means exhaustive and other applications may be found in facility location [50, 51, 1], game theory [66], document summarization [132], social networks [118], or clustering [159].”
- Neighbors Do Help: Deeply Exploiting Local Structures of Point Clouds (2017, background): “Naturally, graph representation is flexible to irregular or even nonEuclidean data such as point clouds, user data on social network, text documents, and gene data [1,10,11,16,17,17,26].”
- Everyone's an influencer: quantifying influence on twitter (2011, background): “…combination of desirable attributes—whether personal attributes like credibility, expertise, or enthusiasm, or network attributes such as connectivity or centrality—that allows them to influence a disproportionately large number of others [10], possibly indirectly via a cascade of influence [31, 16].”
- Influence maximization: near-optimal time complexity meets practical efficiency (2014, methodology): “Besides Greedy [18] and RIS [4], the work most related to ours is by Leskovec et al.”
- The Structural Virality of Online Diffusion (2015, background): “We emphasize that our structural approach to virality is a complement to, not a substitute for, the many existing generative models of viral propagation and their associated parameters (Bass 1969, Granovetter 1978, Watts 2002, Kempe et al. 2003, Dodds and Watts 2004).”
- Quantum machine learning: a classical perspective (2017, background): “Examples of such applications are very diverse, such as document summarization [175], social networks [176] or clustering [177] to name but a few.”
- Tractable Models for Information Diffusion in Social Networks (2006, methodology): “[5], we recall the definition of the ICM, and an approximation theory for the influence maximization problem in the ICM.”
- Submodular Function Maximization (2014, background): “This insight is extremely useful, as it allows to build complex submodular objectives from simpler constituents ( c.f. , Kempe et al. 2003; Leskovec et al. 2007; Stobbe and Krause 2010).”
- Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate (2011, methodology): “…with a standard greedy approximation algorithm while being orders of magnitude faster. keywords: influence maximization; social networks; negative opinions; independent cascade model; ∗Author affiliations and emails: W. Chen (contact author), Microsoft Research Asia, China, weic@microsoft.com.”
- Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity (2017, methodology): “Moreover, since the self-training wrapper retains the scalability of the base method, we obtain both higher quality and be er scalability.”
- Learning Mixtures of Submodular Shells with Application to Document Summarization (2012, background): “While they have a long history in operations research, game theory, econometrics, and electrical engineering, they are still beginning to be studied in machine learning for a variety of tasks including sensor placement [19, 20], structure learning of graphical models [34], document summarization [27”
- Using a model of social dynamics to predict popularity of news (2010, background): “Researchers are using this data to study a variety of topics, including detecting [1, 20] and influencing [6, 12] trends in public opinion, and dynamics of information flow in groups [25, 19].”
- Analysis of Physical Activity Propagation in a Health Social Network (2014, methodology): “We first give a definition of a single trace of physical activity propagations and review the fundamental independent cascade propagation (IC) model [7] in Sec.”