An Adaptive Community-Based Influence Maximization Algorithm in Social Networks

Influence maximization (IM) is a problem of selecting the most influential vertices with a limited budget under a given propagation model. A significant challenge faced by many existing algorithms pertains to their inability to reconcile the competing goals of solution quality and computational efficiency, rendering them unsuitable in large-scale social networks. In this paper, we propose an adaptive community-based influence maximization algorithm, named AComA, to solve the IM problem with a balance of effectiveness and efficiency. First, we introduce a community detection method to divide a large-scale network into several communities. An adaptive indicator is then defined to identify vertices with high propagation values in divided community networks. Based on community detection and the adaptive influence indicator, the number of candidate vertices is reduced, which significantly reduces the search space of the problem. Second, to select the final seed set from these candidate vertices, a genetic algorithm (GA) is introduced. The crossover and mutation operations are modified explicitly to adapt to the IM problem. By extracting information from the local neighborhood and the global community structure, AComA achieves a more accurate measurement of the influence spread for each vertex. The method proposed in this paper is tested on several real-world datasets. The experimental results show that AComA is promising.