文献详情
Community based acceptance probability maximization for target users on social networks: Algorithms and analysis
文献类型：期刊
通讯作者：Li, DY (reprint author), Renmin Univ China, Sch Informat, Beijing 100872, Peoples R China.
期刊名称：THEORETICAL COMPUTER SCIENCE影响因子和分区
年：2020
卷：803
页码：116-129
ISSN：0304-3975
关键词：Social influence; Diffusion model; Seed selection; Submodularity
所属部门：信息学院
摘要：Different from previous social influence problems such as Influence Maximization (IM), we in this paper first propose the Acceptance Probability Maximization (APM) problem, i.e., we select a seed set S with a budget b such that the acceptance probability of the target user set T is maximized. Then we employ the classical Independent Cascade (IC) model as the information diffusion model. Based on the IC model, we prove that the APM problem is NP-hard and the objective function is monotone non-dec ...More
Different from previous social influence problems such as Influence Maximization (IM), we in this paper first propose the Acceptance Probability Maximization (APM) problem, i.e., we select a seed set S with a budget b such that the acceptance probability of the target user set T is maximized. Then we employ the classical Independent Cascade (IC) model as the information diffusion model. Based on the IC model, we prove that the APM problem is NP-hard and the objective function is monotone non-decreasing and submodular. Considering community components of the social network, we convert the APM problem to the Maximum Weight Hitting Set (MWHS) problem. Next we develop a pipage rounding algorithm whose approximation ratio is (1 - 1/e). Furthermore, we also propose a basic greedy algorithm and a heuristic algorithm as comparison methods. Finally, we conduct extensive simulations on synthetic and real-life social networks to evaluate the efficacy and efficiency of our algorithms. Empirical evaluation results validate the superiority of proposed algorithms in both effectiveness and efficiency compared with a few baseline comparison methods. (C) 2019 Elsevier B.V. All rights reserved. ...Hide

DOI：10.1016/j.tcs.2019.07.032
百度学术：Community based acceptance probability maximization for target users on social networks: Algorithms and analysis
语言：外文
基金：National Natural Science Foundation of ChinaNational Natural Science Foundation of China [11671400, 61672524]; Fundamental Research Funds for the Central University; Research Funds of Renmin University of China [2015030273]
作者其他论文



A New Greedy Algorithm for Constructing the Minimum Size Connected Dominating Sets in Wireless Networks.Luo, Chuanwen, Wang, Yongcai, Yu, Jiguo, et al. .WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, WASA 2017. 2017, 10251, 109-114.
Fair Multi-influence Maximization in Competitive Social Networks.Yu, Ying, Jia, Jinglan, Li, Deying, et al. .WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, WASA 2017. 2017, 10251, 253-265.
WCS: Weighted Component Stitching for Sparse Network Localization.Sun, Tianyuan, Wang, Yongcai, Li, Deying, et al. .IEEE-ACM TRANSACTIONS ON NETWORKING. 2018, 26(5), 2242-2253.
Robust Component-based Network Localization with Noisy Range Measurements.Sun, Tianyuan, Wang, Yongcai, Li, Deying, et al. .2018 27TH INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATION AND NETWORKS (ICCCN). 2018.
Robust Passive Location in Zero-Calibrated Environment Using Smoothed Ordinal Constraints.Ye, Xuehan, Lei, Zhixian, Wang, Yongcai, et al. .2017 14TH INTERNATIONAL SYMPOSIUM ON PERVASIVE SYSTEMS, ALGORITHMS AND NETWORKS & 2017 11TH INTERNATIONAL CONFERENCE ON FRONTIER OF COMPUTER SCIENCE AND TECHNOLOGY & 2017 THIRD INTERNATIONAL SYMPOSIUM OF CREATIVE COMPUTING (ISPAN-FCST-ISCC). 2017