Target users' activation probability maximization with different seed set constraints in social networks
Target users' activation probability maximization with different seed set constraints in social networks
复制标题
社交网络中不同种子集约束下目标用户的激活概率最大化
DOI：
10.1016/j.tcs.2020.06.008
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Li Deying
中科院分区：
文献类型：
--
作者：
Yan Ruidong;Du Hongwei;Li Yi;Chen Wenping;Wang Yongcai;Zhu Yuqing;Li Deying
在线社交网络上的影响最大化（Influence Maximization，IM）近年来得到了广泛的研究，其使用有限的预算从网络中的节点中选择种子集合，使得受种子集合影响的节点的期望数量最大化。然而，如何激活一组经过考虑的目标用户T，例如将产品销售给特定的目标群体，是一个更实际的问题。针对这一问题，我们分别提出了带约束的目标用户激活概率最大化（TUAPM-WC）问题和无约束的目标用户激活概率最大化（TUAPM-WOC）问题，即选择一个有/无大小约束的种子集S，使得T中目标用户的激活概率最大化。考虑到影响力在信息传播过程中会衰减，提出了一种新颖实用的影响力衰减模型（IDM）作为信息扩散模型。基于IDM，我们证明了TUAPM-WC和TUAPM-WOC问题是NP-难的。我们还证明了TUAPM-WC和TUAPM-WOC问题的目标函数是单调非减的和次模的。一方面，我们采用双贪婪算法（DGA），以保证（1/3）-近似比TUAPM-WOC问题时，|S|是不受约束的另一方面，我们提出了一系列的算法来解决TUAPM-WC时，|S| ≤ B，其中B为正整数。更具体地说，我们提供了（1 - 1/e）近似的基本贪婪算法（BGA）。在此基础上，提出了一种适用于在线大型社交网络的加速可扩展算法。最后，我们运行我们的算法模拟合成和现实生活中的社交网络，以评估所提出的算法的有效性和效率。实验结果验证了本文算法的上级性能。
Influence Maximization (IM) over the online social networks have been widely explored in recent years, which selects a seed set from nodes in the network using a limited budget such that the expected number of nodes influenced by the seed set is maximized. However, how to activate a considered set of targeting users T, eg, selling a product to a specific target group, is a more practical problem. To address this problem, we respectively propose the Target Users' Activation Probability Maximization with Constraint (TUAPM-WC) problem and the Target Users' Activation Probability Maximization without Constraint (TUAPM-WOC) problem, ie, to select a seed set S with/without size constraints such that the activation probabilities of the target users in T are maximized. Considering that the influence will decay during information propagation, we propose a novel and practical Influence Decay Model (IDM) as the information diffusion model. Based on the IDM, we show that the TUAPM-WC and the TUAPM-WOC problems are NP-hard. We also prove that the objective functions of TUAPM-WC and TUAPM-WOC problems are monotone non-decreasing and submodular. On one hand, we employ a Double Greedy Algorithm (DGA) to guarantee a (1/3)-approximation ratio for TUAPM-WOC problem when| S| is unconstrained. On the other hand, we propose a series of algorithms to solve the TUAPM-WC when| S|≤ b, where b is a positive integer. More specifically, we provide a (1− 1/e)-approximation Basic Greedy Algorithm (BGA). Furthermore, a speed-up Scalable Algorithm (SA) is proposed for online large social networks. Finally, we run our algorithms by simulations on synthetic and real-life social networks to evaluate the effectiveness and efficiency of the proposed algorithms. Experimental results validate our algorithms' superior to the comparison algorithms.