Maximizing social influence for the awareness threshold model

Abstract

Given a social network G, the Influence Maximization (IM) problem aims to find a seed set S ⊆ G of k users. These users are advertised, or activated, through marketing campaigns, with the hope that they will continue to influence others in G (e.g., by spreading messages about a new book). The goal of IM is to find the set S that achieves an optimal advertising effect or expected spread (e.g., make the largest number of users in G know about the book). Existing IM solutions make extensive use of propagation models, such as Linear Threshold (LT) or the Independent Cascade (IC). These models define the activation probability, or the chance that a user successfully gets activated by his/her neighbors in G. Although these models are well-studied, they overlook the fact that a user’s influence on others decreases with time. This can lead to an over-estimation of activation probabilities, as well as the expected spread. To address the drawbacks of LT and IC, we develop a new propagation model, called Awareness Threshold (or AT), which considers the fact that a user’s influence decays with time. We further study the Scheduled Influence Maximization (or SIM), to find out the set S of users to activate, as well as when they should be activated. The SIM problem considers the time-decaying nature of influence based on the AT model. We show that the problem is NP-hard, and we develop three approximation solutions with accuracy guarantees. Extensive experiments on real social networks show that (1) AT yields a more accurate estimation of activation probability; and (2) Solutions to the SIM gives a better expected spread than IM algorithms on the AT model.