A Denoising Diffusion Adaptive Search for the α-Domination Problem on Social Graphs

Abstract

The α-domination problem is a generalization of the classical dominating set problem and serves as a way to model influence structures in social networks. In this work, we build on previous research and explore the use of denoising diffusion models to generate high-quality solutions for this problem. Our main contribution is the introduction of a novel variation of the Greedy Randomized Adaptive Search Procedure (GRASP), utilizing a denoising diffusion model for the parallel construction of a diverse set of initial solutions, which we refer to as the Denoising Diffusion Adaptive Search Procedure (DDASP). By focusing our efforts on real-world social network graphs, we present a superior alternative to conventional metaheuristic algorithms, as prior work has shown that such algorithms often struggle with the unique structural properties of these graphs. Furthermore, we address the challenge of generating viable training data for our models, as the graphs under consideration are typically too large to be used directly. To this end, we employ two graph generation methods to produce artificial training data derived from a set of original input graphs. Experimental results on a benchmark suite of Facebook graphs demonstrate that, particularly in the context of social networks, DDASP consistently outperforms the leading metaheuristic approach under an equivalent time budget.