BatchedGreedy: A batch processing approach for influence maximization with candidate constraint

Xiaowei Han

doi:10.1007/s10489-022-03854-0

2022-07-12

PRE

Xiaowei Han

Hejiao Huang *

DOI：10.1007/s10489-022-03854-0

原文链接

原文求助

摘要

En 中文

Influence maximization (IM) aims to find k seed nodes from social network G to maximize the spread of influence under a given diffusion model. However, in real social marketing activities, only some users are connected with marketing initiators. In addition, not all users are willing to be a seed for a specific marketing activity. These factors restrict the range of nodes that can act as seed nodes. Therefore, we first propose the candidate constrained influence maximization (CCIM) problem. Here, only seeds from a predefined set of candidate nodes are selected. Despite the similarity in definition between IM and CCIM, many state-of-the-art algorithms for IM cannot be directly applied to CCIM . We propose a batch processing approach BatchedGreedy for CCIM, which utilizes the efficiency of bit operation in a computer to estimate the spread of influence of nodes in batches. Furthermore, for the traditional influence maximization(IM) problem, we propose the filtering-based BatchedGreedy (FB-BG) algorithm by incorporating node filtering with the BatchedGreedy approach. From experimental statistics, it is shown that FB-BG not only provides better performance than state-of-the-art algorithms in comparable running time, but is also more scalable to larger networks.

Keyword:

Influence maximization

Batch processing

Bit operation