Influence Maximization in Signed Social Networks with Opinion Formation
Influence Maximization in Signed Social Networks with Opinion Formation
复制标题
通过意见形成实现签名社交网络影响力最大化
DOI：
10.1109/access.2019.2918810
复制
发表时间：
2019
期刊：
影响因子：
3.9
通讯作者：
Hideyuki Takada
中科院分区：
文献类型：
--
作者：
Wenxin Liang;Chengguang Shen;Xiao Li;Ryo Nishide;Ian Piumarta;Hideyuki Takada
影响力最大化（IM）近年来得到了广泛的研究。给定固定数量的种子用户和一定的扩散模型，IM问题的目标是在社交网络中选择合适的种子用户，使其能够实现影响力的最大传播。之前的大多数工作都假设用户之间只存在积极的关系，因此用户会积极地传播影响力。然而，消极关系也普遍存在于各种社交网络中，并与信息传播中的积极关系相辅相成。在本文中，影响力最大化问题在包含积极和消极关系的签名社交网络中得到解决。我们提出了一种称为 LT-S 的新型扩散模型和两个影响扩散函数。所提出的 LT-S 模型通过意见形成扩展了经典的线性阈值模型，该模型融合了正面和负面意见，并模拟了现实世界社交网络中的信息扩散。 LT-S模型下的影响力扩散函数既不是单调的也不是子模的，这给最大化带来了挑战。 RLP 算法是为了解决这个问题而提出的，该算法是对 R-Greedy 算法的改进，结合了两种提出的加速技术，即基于实时边缘和基于传播路径的技术。对公共真实签名社交网络数据集进行广泛实验的结果表明，我们的算法在效率和有效性方面均优于基线算法。
Influence maximization (IM) has been widely studied in recent years. Given fixed number of seed users and certain diffusion models, the IM problem aims to select proper seed users in a social networks such that they can achieve the maximal spread of influence. Most previous work assumes that there are only positive relationships between users, and thus users spread influence positively. However, negative relationships also universally exist in various social networks and are complementary to positive relationships in information diffusion. In this paper, the influence maximization problem is addressed in signed social networks that contain both positive and negative relationships. We propose a novel diffusion model called LT-S and two influence spread functions. The proposed LT-S model extends the classical linear threshold model with opinion formation that incorporates both positive and negative opinions and simulates information diffusion in real-world social networks. The influence spread functions under the LT-S model are neither monotone nor submodular which bring challenges to maximization. The RLP algorithm is proposed to tackle the issue, which is improved from R-Greedy algorithm by incorporating two proposed accelerating techniques, the live-edge based and propagation-path based techniques. The results of the extensive experiments on public real signed social network datasets demonstrate that our algorithm outperforms the baseline algorithms in terms of both efficiency and effectiveness.