Influence maximization algorithm: Review on current approaches and limitations

Abstract

Influencing customers through social media is a new form of marketing. Recently, there were studies on the Influence Maximization (IM) problem, which aimed to identify influencers that can spread influence to a wider audience. The complex social media network requires efficient IM algorithms, in which small improvements will lead to a performance boost. In this research, recent articles on IM were reviewed. This review aims to identify the current approaches, enhancements, factors, diffusion models, and objectives of IM. In typical IM formulation, a social network is represented as a graph with nodes (user) and edges (relation). There are graph-based and non-graph-based IM approaches. Graph-based IM approaches include greedy and heuristic algorithms. The objectives of IM studies were optimizations on large or complex networks, on unknown networks, using bandit, using relation impacts, or general optimization. IM algorithms were continuously getting better. However, there are aspects that are still improvable, i.e. pre-calculation, thresholds estimation, seeds selection, integration of neural networks, and more importantly, real-life validation methods. This study will help in identifying possible improvements based on current IM limitations. Effective IM methods will help business users to identify influencers more accurately.

Keywords

• influence maximization
• social media
• graph theory
• algorithm design