Cost-aware Targeted Viral Marketing: Approximation with Less Samples

Cost-aware Targeted Viral Marketing (CTVM), a generalization of Influence Maximization (IM), has received a lot of attentions recently due to its commercial values. Previous approximation algorithms for this problem required a large number of samples to ensure approximate guarantee. In this paper, w...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-02
Main Authors: Pham, Canh V, Duong, Hieu V, Thai, My T
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Decision trees
Marketing
Mathematical analysis
Social networks
Viral marketing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Cost-aware Targeted Viral Marketing (CTVM), a generalization of Influence Maximization (IM), has received a lot of attentions recently due to its commercial values. Previous approximation algorithms for this problem required a large number of samples to ensure approximate guarantee. In this paper, we propose an efficient approximation algorithm which uses fewer samples but provides the same theoretical guarantees based on generating and using important samples in its operation. Experiments on real social networks show that our proposed method outperforms the state-of-the-art algorithm which provides the same approximation ratio in terms of the number of required samples and running time.
ISSN:2331-8422