%0 Journal Article
%T Proximity-Aware Degree-Based Heuristics for the Influence Maximization Problem
%J Computer and Knowledge Engineering
%I Ferdowsi University of Mashhad
%Z 2538-5453
%A Adineh, Maryam
%A Nouri Baygi, Mostafa
%D 2022
%\ 06/01/2022
%V 5
%N 1
%P 37-46
%! Proximity-Aware Degree-Based Heuristics for the Influence Maximization Problem
%K Degree centrality
%K Heuristic algorithm
%K Independent cascade model
%K Influence maximization
%R 10.22067/cke.2022.63265.0
%X 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).
%U https://cke.um.ac.ir/article_41641_a1e357c754e88f1edcfae69a013f593d.pdf