Determining good solutions and validating them with a metaheuristic approach in social network influence minimization problems

Abstract

The evolution of social networks has given rise to significant challenges associated with the overwhelming amount of information available. These challenges encompass various areas such as viral marketing, disease management, and misinformation control. Crafting effective strategies for minimizing influence is heavily influenced by factors like network topology, user behavior, and the dynamics of information propagation. As social networks become more intricate, the imperative to utilize data-driven insights becomes increasingly apparent. The Social Influence Minimization Problems (IMIN) aims to identify and strategically block users to limit the spread of information. Extracting structural insights through data-mining techniques can guide the development of efficient heuristics and the identification of influential users to be targeted for blocking. To address the NP-hard nature of the IMIN problem, a robust metaheuristic algorithm based on the Greedy Randomized Adaptive Search (GRASP) framework has been introduced. This method is derived from a deep understanding of how network features contribute to impactful solutions, proving to be effective and cost-efficient when compared to state-of-the-art methods.