Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/1285
Title: Variable Neighborhood Search for Weighted Total Domination Problem and Its Application in Social Network Information Spreading
Authors: Kapunac, Stefan 
Kartelj, Aleksandar 
Djukanović, Marko
Affiliations: Informatics and Computer Science 
Informatics and Computer Science 
Issue Date: 2023
Rank: M21a
Publisher: Elsevier
Journal: Applied Soft Computing
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.
Description: 
Copzright 2023 by Elsevier.
DOI https://doi.org/10.1016/j.asoc.2023.110387
URI: https://research.matf.bg.ac.rs/handle/123456789/1285
DOI: 10.1016/j.asoc.2023.110387
Rights: Attribution-NonCommercial-NoDerivs 3.0 United States
Appears in Collections:Research outputs

Files in This Item:
File Description SizeFormat Existing users please
paper_clean.pdf1.48 MBAdobe PDF
Embargoed until May 26, 2025    Request a copy
Show full item record

SCOPUSTM   
Citations

2
checked on Dec 18, 2024

Page view(s)

21
checked on Dec 24, 2024

Download(s)

1
checked on Dec 24, 2024

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons