proximity-aware degree-based heuristics for the influence maximization problem

The problem of influence maximization is selecting the most influential individuals in a social network. with the popularity of social network sites and the development of viral marketing, the importance of the problem has increased. the influence maximization problem is np-hard, and therefore, there will not exist any polynomial-time algorithm to solve the problem unless p = np. many heuristics are proposed for finding a nearly good solution in a shorter time. this study proposes two heuristic algorithms for finding good solutions. the heuristics are based on two ideas: 1) vertices of high degree have more influence in the network, and 2) nearby vertices influence on almost analogous sets of vertices. we evaluate our algorithms on several well-known data sets and show that our heuristics achieve better results (up to 15% in the influence spread) for this problem in a shorter time (up to 85% improvement in the running time).