C2IM: Community based context-aware influence maximization in social networks

Abstract

Influence Maximization (IM) is an optimization problem in viral marketing to identify k most influential users in social networks. IM problem, with large-scale data, faces many challenges like time-efficiency, accuracy, and effectiveness of seed. To solve these challenges, we propose a Community based Context-aware Influence Maximization (C2IM) algorithm. C2IM uses a community-based framework to improve the time-efficiency that reduces the search space significantly. It considers user's interests (known as topics) to address the effectiveness of seed. We extend the traditional information diffusion models (i.e., linear threshold and independent cascade) to Context-aware Linear Threshold model (CLT) and Context-aware Independent Cascade model (CIC) for influence spreading. We show that C2IM is NP-hard in nature under CLT and CIC models. To identify k most influential users, we first propose a Community Detection Algorithm (CDA) to partitions the network into sub-networks. We then devise a Non-Desirable nodes Finder (NDF) technique to identify non-desirable nodes. We introduce Seed Selection Algorithm (SSA) to compute most influential seed nodes based on diffusion degree of nodes. Experimental results show that the proposed algorithm performs better than CIM on influence spread and faster than TIM. Thus, C2IM algorithm is a trade-off between quality and efficiency. © 2018 Elsevier B.V.