Collaborative Computing: Networking, Applications and Worksharing. 14th EAI International Conference, CollaborateCom 2018, Shanghai, China, December 1-3, 2018, Proceedings

Research Article

Cost-Aware Targeted Viral Marketing with Time Constraints in Social Networks

Download
129 downloads
  • @INPROCEEDINGS{10.1007/978-3-030-12981-1_5,
        author={Ke Xu and Kai Han},
        title={Cost-Aware Targeted Viral Marketing with Time Constraints in Social Networks},
        proceedings={Collaborative Computing: Networking, Applications and Worksharing. 14th EAI International Conference, CollaborateCom 2018, Shanghai, China, December 1-3, 2018, Proceedings},
        proceedings_a={COLLABORATECOM},
        year={2019},
        month={2},
        keywords={Social network Influence maximization Time constraints},
        doi={10.1007/978-3-030-12981-1_5}
    }
    
  • Ke Xu
    Kai Han
    Year: 2019
    Cost-Aware Targeted Viral Marketing with Time Constraints in Social Networks
    COLLABORATECOM
    Springer
    DOI: 10.1007/978-3-030-12981-1_5
Ke Xu1,*, Kai Han1,*
  • 1: University of Science and Technology of China
*Contact email: ustcxk@mail.ustc.edu.cn, hankai@ustc.edu.cn

Abstract

Online social networks have been one of the most effective platforms for marketing which is called . The main challenge of viral marketing is to seek a set of users that can maximize the expected influence, which is known as Influence Maximization (IM) problem. In this paper, we incorporate of users and , including and of influence diffusion, in IM problem and propose (CTVMT) problem to find the most cost-effective seed users who can influence the most relevant users within a time deadline. We study the problem under IC-M and LT-M diffusion model which extends IC and LT model with time constraints. Since CTVMT is NP-hard under two models, we design a algorithm using two new benefit sampling algorithms designed for IC-M and LT-M respectively to get a solution with an approximation ratio. To the best of our knowledge, this is the first algorithm that can provide approximation guarantee for our problem. Our empirical study over several real-world networks demonstrates the performances of our proposed solutions.