An efficient percolation-based method for influence maximization problem

Identification of influential nodes is one of the important aspects of social network analysis. These nodes are used for maximizing influence in many applications. Since Influence maximization is an NP-Hard problem, many other greedy and heuristic methods have been proposed in recentdecades to find near optimal seed nodes in large-scale data. However, they have challenges such as time complexity, accuracy, and efficiency. This paper offers a new percolationbased node selection method for influence maximization problem that is called PBN algorithm. This method selectsinfluential nodes based on the percolation, weighting, and removing approach in social networks. Experimental results show that the proposed algorithm outperforms other compared algorithms such as LIR, ProbDegree, and K-core in terms of influence spread with acceptable time-complexity.

Keywords:

Influence Maximization , Percolation , Seed Node selection , Influence Spread , Social Networks Analysis.I.