期刊
COMPUTATIONAL DATA AND SOCIAL NETWORKS
卷 11917, 期 -, 页码 108-119出版社
SPRINGER INTERNATIONAL PUBLISHING AG
DOI: 10.1007/978-3-030-34980-6_13
关键词
Profit maximization; Group influence; Non-submodular; Social networks
资金
- US National Science Foundation [1747818]
- National Natural Science Foundation of China [91324012]
- Project of Promoting Scientific Research Ability of Excellent Young Teachers in University of Chinese Academy of Sciences
People with the same interests, hobbies or political orientation always form a group to share all kinds of topics in Online Social Networks (OSN). Product producers often hire the OSN provider to propagate their advertisements in order to influence all possible potential groups. In this paper, a group is assumed to be activated if beta percent of members are activated. Product producers will gain revenue from all activated groups through group-buying behavior. Meanwhile, to propagate influence, producers need pay diffusion cost to the OSN provider, while the cost is usually relevant to total hits on the advertisements. We aim to select k seed users to maximize the expected profit that combines the benefit of activated groups with the diffusion cost of influence propagation, which is called Group Profit Maximization (GPM) problem. The information diffusion model is based on Independent Cascade (IC), and we prove GPM is NP-hard and the objective function is neither submodular nor supermodular. We develop an upper bound and a lower bound that both are difference of two submodular functions. Then we design an Submodular-Modular Algorithm (SMA) for solving difference of submodular functions and SMA is proved to converge to local optimal. Further, we present an randomized algorithm based on weighted group coverage maximization for GPM and apply Sandwich framework to get theoretical results. Our experiments verify the effectiveness of our method, as well as the advantage of our method against the other heuristic methods.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据