Fractional Budget Allocation for Influence Maximization under General Marketing Strategies
This addresses a practical problem in marketing for businesses seeking to optimize promotional strategies on social networks, though it is incremental as it builds on existing influence maximization frameworks.
The paper tackles the fractional influence maximization problem on social networks by allocating partial discounts to users to maximize influence spread, subject to a budget constraint, and proposes an efficient (1-1/e)-approximation algorithm for NP-hard cases with affine activation functions.
We consider the fractional influence maximization problem, i.e., identifying users on a social network to be incentivized with potentially partial discounts to maximize the influence on the network. The larger the discount given to a user, the higher the likelihood of its activation (adopting a new product or innovation), who then attempts to activate its neighboring users, causing a cascade effect of influence through the network. Our goal is to devise efficient algorithms that assign initial discounts to the network's users to maximize the total number of activated users at the end of the cascade, subject to a constraint on the total sum of discounts given. In general, the activation likelihood could be any non-decreasing function of the discount, whereas, our focus lies on the case when the activation likelihood is an affine function of the discount, potentially varying across different users. As this problem is shown to be NP-hard, we propose and analyze an efficient (1-1/e)-approximation algorithm. Furthermore, we run experiments on real-world social networks to show the performance and scalability of our method.