Online influence maximization

Abstract

Social networks, such as Twitter and Facebook, enable the wide spread of information through users’ influence on each other. These networks are very useful for marketing purposes. For example, free samples of a product can be given to a few influencers (seed nodes), with the hope that they will convince their friends to buy it. One way to formalize marketers’ objective is through the influence maximization problem, which is to find the best seed nodes to influence under a fixed budget so that the number of people who get influenced in the end is maximized. Recent solutions to influence maximization rely on the knowledge of the influence probability of every social network user. This is the probability that a user influences another one, and can be obtained by using users’ history of influencing others (called action logs). However, this information is not always available.

We propose a novel Online Influence Maximization (OIM) framework, showing that it is possible to maximize influence in a social network in the absence of exact information about influence probabilities. In our OIM framework, we investigate an Explore-Exploit (EE) strategy, which could run any one of the existing influence maximization algorithms to select the seed nodes using the current influence probability estimation (exploit), or the confidence bound of the estimation (explore). We then start the influence campaign using the seed nodes, and consider users’ immediate feedback to the campaign to further decide which seed nodes to influence next. Influence probabilities are modeled as random variables and their probability distributions are updated as we get feedback. In essence, we perform influence maximization and learning of influence probabilities at the same time. We further develop an incremental algorithm that can significantly reduce the overhead of handling users’ feedback information. We validate the e↵ectiveness and efficiency of our OIM framework on large real-world datasets.