Maximizing the spread of influence through a social network using partial incentives
This paper studies fractional influence maximization, a continuous generalization of the classical discrete influence maximization problem. Instead of giving free products to a small set of influencers, marketers may allocate partial discounts, allowing broader but weaker incentives. The paper shows that fractional influence maximization corresponds to maximizing the multilinear extension of a monotone submodular function under an \(L_1\) budget constraint, noting that the expected influence function is the multilinear extension of the discrete influence maximization influence function. The paper characterizes optimal solutions, proposes a \((1-1/e)\)-approximation algorithm, and demonstrate its efficiency and practicality through synthetic and real-world experiments.
- An analysis of approximations for maximizing submodular set functions—I
- An analysis of the greedy algorithm for the submodular set covering problem
- Fair Influence Maximization in Large-scale Social Networks Based on Attribute-aware Reverse Influence Sampling
- Fairness in Influence Maximization through Randomization
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Maximizing social influence in nearly optimal time
- Optimal approximation for the submodular welfare problem in the value oracle model
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Submodular function maximization in parallel via the multilinear relaxation
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
This page was built for publication: Maximizing the spread of influence through a social network using partial incentives
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7307235)
