Jisuanji kexue (Apr 2022)
Budget-aware Influence Maximization in Social Networks
Abstract
The influence maximization of social networks is a crucial problem in the field of network science, which has wide applications from advertising to public opinion control.This problem refers to selecting a set of source nodes in a social graph to achieve the greatest influence under a certain propagation model.Since the node selection problem is a typical NP-hard problem, it will encounter the combinatorial explosion when facing large-scale networks.Hence, in recent years, heuristic algorithms are ge-nerally adopted to obtain approximate solutions to the problems in acceptable time.However, the existing work rarely considers the cost of selected nodes, and hence the solutions obtained cannot meet the budget limitations in practical applications.This paper aims to solve the influence maximization problem of social networks under cost-constrained conditions.By fully considering the costs, we build a budget-aware influence maximization model and propose a node selection algorithm named community detection-based ant colony system (CDACS) to deal with it.First, in order to save the unnecessary expenditure coming from the redundant coverage of source nodes, we use the fast greedy modularity maximization algorithm to cluster the network, and introduce a cross-community walking factor in the state transition process of ants to enhance the global exploration ability of the ant colony on the network.Second, we specifically design a penalty-based evaluation function to guide the search towards budget-feasible region as well as developing new heuristic and pheromone forms to enhance the search efficiency.Experimental results on real datasets show that the CDACS algorithm enhances the traditional ant colony algorithm by achieving a 15% improvement in the average coverage rate and a 20% reduction in the running time overhead.Compared with other existing influence maximization algorithms, the coverage effect has also been significantly improved.Moreover, the reliability of the CDACS algorithm in cost control has been validated by experiments.
Keywords
