A reverse randomized greedy algorithm for the minimum positive influence dominating set problem in social networks

Abstract

In this paper we propose heuristic approach to finding a minimum positive influence dominating set (MPIDS) with application in social network analysis. For a given social network represented by a graph, the goal is to find a minimal set of influential individuals (nodes) that allows for spreading positive influence throughout the whole network. Given the fast growth of social networks and the importance they have in modern human communication, these connections should be used in the best possible way. As the considered problem is NP-hard problem, this paper proposes a reverse randomized greedy algorithm (RRG) and a multi-start method based on the RRG algorithm as solution approaches. The proposed algorithms are tested on a set of real-world test instances from literature and the obtained results are analysed and compared with the results of existing greedy algorithms for solving the MPIDS problem.