Paper Info
Title
Minimum Cost Seed Selection for Multiple Influences Diffusion in Communities
Abstract
Recently, influence maximization in social networks has attracted great attention. In this paper, we consider that a company intends to select some users to promote its multiple products (called influences) in online social network consisting of many communities, in which each user has different preferences for each influence. We focus on the Minimum Cost Seed Selection (MCSS) problem for multiple influences, that is, how to select some seeds with minimum cost so that the average influenced probability of all users in each community is not less than a threshold. To solve the MCSS problem, we design a submodular utility function, based on which we turn our problem into a non-trivial set cover problem with non-linear constraints. After proving the NP-hardness of MCSS, we propose a greedy algorithm, called G-MCSS, to solve it. We analyze the approximation ratio of G-MCSS. Additionally, we extend the MCSS problem to a complex case, where the number of acceptable influences for each user is limited, and the cost is proportional to the number of allocated influences. We further propose another greedy algorithm to solve the extended problem. Finally, we demonstrate the significant performances of our algorithms through extensive experiments based on real social network traces.
Year
DOI
Venue
2018
10.1109/MASS.2018.00048
2018 IEEE 15th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)
Keywords
Field
DocType
minimum cost seed selection,multiple influences diffusion,online social networks,virtual community
Set cover problem,Mathematical optimization,Social network,Computer science,Submodular set function,Greedy algorithm,Maximization,Virtual community,Distributed computing
Conference
ISSN
ISBN
Citations 
2155-6806
978-1-5386-5581-8
0
PageRank 
References 
Authors
0.34
11
5
Name
Order
Citations
PageRank
Guoju Gao1366.25
Mingjun Xiao252041.54
Jie Wu38307592.07
He Huang482965.14
Chen Guoliang538126.16