Variable Neighborhood Search for Weighted Total Domination Problem and Its Application in Social Network Information Spreading

Abstract

The weighted total domination problem (WTDP) is a practical extension of the well-known total domination problem. The most efficient literature approaches to tackle this problem are based on branch and cut or genetic algorithm. In this work, we propose a different strategy to solve WTDP that relies on the popular variable neighborhood search (VNS) metaheuristic. VNS is equipped with a carefully designed fitness function that allows for evaluation of both feasible and infeasible solutions, which further allows for a thorough search of the promising regions of the solution space. The method also utilizes two effective first-improvement local search procedures. The effectiveness of VNS is demonstrated on a wide range of benchmark sets compared to all three competing methods from the literature. For small-to-middle-sized instances (up to 100 nodes), VNS can obtain solutions that match the quality of optimal solutions in almost all cases (134 out of 135). For middle-to-large-sized instances, VNS can outperform all comparison algorithms in terms of solution quality, which is verified by statistical hypothesis tests. Another key aspect of this paper is presenting a potential application of the WTDP for boosting information spreading across social networks. Experiments confirmed that information spreading is accelerated when informed nodes (spreaders) are set to be solutions of the WTDP obtained by VNS. Although our method has been successfully applied to samples of real social networks of up to approximately 81 thousand nodes and 1.34 million edges, further research might enhance the method to be used on various (unsampled) social network datasets.