2003 MaximizingSpreadOfInfluence

(Kempe et al., 2003) ⇒ David Kempe, Jon Kleinberg, and Éva Tardos. (2003). “Maximizing the Spread of Influence Through a Social Network.” In: Proceedings of SIGKDD Conference (KDD-2003). doi:10.1145/956750.956769

Subject Headings: Social Network Mining Algorithm.

Notes

It proposes an approximation algorithm for the ([NP-hard]) Influential Node Set Selection Task.

Cited By

2007

(Leskovec et al., 2007) ⇒ Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. (2007). “Cost-effective Outbreak Detection in Networks.” In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2007) doi:10.1145/1281192.1281239

Quotes

Author Keywords

approximation algorithms, social networks, viral marketing, diffusion of innovations.

Abstract

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 innovantion, 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 ﬁeld of social networks.,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2003 MaximizingSpreadOfInfluence	David Kempe Jon Kleinberg Éva Tardos			Maximizing the Spread of Influence Through a Social Network		Proceedings of SIGKDD Conference	http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf	10.1145/956750.956769		2003