标题：Minimizing the Cost to Win Competition in Social Network
作者：Liu, Ziyan; Hong, Xiaoguang; Peng, Zhaohui; Chen, Zhiyong; Wang, Weibo; Song, Tianhang
作者机构：[Liu, Ziyan; Hong, Xiaoguang; Peng, Zhaohui; Chen, Zhiyong; Wang, Weibo; Song, Tianhang] Shandong Univ, Sch Comp Sci & Technol, Jinan 250100, Peoples 更多
会议名称：17th Asia-Pacific Web Conference (APWeb)
会议日期：SEP 18-20, 2015
来源：WEB TECHNOLOGIES AND APPLICATIONS (APWEB 2015)
关键词：social network; influence propagation; competition; cost; Degree Adjust
摘要：In social network, influences are propagating among users. Influence maximizing is an important problem which has been studied widely in recent years. However, in the real world, sometimes users need to make their influence maximization through social network and defeat their competitors under minimum cost, such as online voting, expanding market share, etc. In this paper, we consider the problem of selecting a seed set with the minimum cost to influence more people than other competitors. We show this problem is NP-hard and propose a cost-effective greedy algorithm to approximately solve the problem and improve the efficiency based on the submodularity. Furthermore, a new cost-effective Degree Adjust heuristics is proposed to get high efficiency. Experimental results show that our cost-effective greedy algorithm achieves better effectiveness than other algorithms and the cost-effective Degree Adjust heuristic algorithm achieves high efficiency and gets better effectiveness than Degree and Random heuristics.