2015 OnlineInfluenceMaximization

• (Lei et al., 2015) ⇒ Siyu Lei, Silviu Maniu, Luyi Mo, Reynold Cheng, and Pierre Senellart. (2015). “Online Influence Maximization.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783271

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Online+Influence+Maximization
• http://dl.acm.org/citation.cfm?id=2783258.2783271&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; influence maximization; multi-armed bandits; reinforcement learning; uncertain databases

Abstract

Social networks are commonly used for marketing purposes. For example, free samples of a product can be given to a few influential social network users (or seed nodes), with the hope that they will convince their friends to buy it. One way to formalize this objective is through the problem of influence maximization (or IM), whose goal is to find the best seed nodes to activate under a fixed budget, so that the number of people who get influenced in the end is maximized. Solutions to IM rely on the influence probability that a user influences another one. However, this probability information may be unavailable or incomplete. In this paper, we study IM in the absence of complete information on influence probability. We call this problem Online Influence Maximization (OIM), since we learn influence probabilities at the same time we run influence campaigns. To solve OIM, we propose a multiple-trial approach, where (1) some seed nodes are selected based on existing influence information; (2) an influence campaign is started with these seed nodes; and (3) user feedback is used to update influence information. We adopt Explore-Exploit strategies, which can select seed nodes using either the current influence probability estimation (exploit), or the confidence bound on the estimation (explore). Any existing IM algorithm can be used in this framework. We also develop an incremental algorithm that can significantly reduce the overhead of handling user feedback information. Our experiments show that our solution is more effective than traditional IM methods on the partial information.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 OnlineInfluenceMaximization	Reynold Cheng Siyu Lei Silviu Maniu Luyi Mo Pierre Senellart			Online Influence Maximization				10.1145/2783258.2783271		2015