Alessio Gerardo Demattia
Intervention design for influence maximization in the Linear Threshold Model on networks.
Rel. Giacomo Como, Fabio Fagnani. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2026
|
Preview |
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (3MB) | Preview |
Abstract
Understanding the mechanisms of diffusion of behaviors in social groups represents a major challenge in social science. The Linear Threshold Model (LTM) on graphs provides a useful framework, modelling each individual as a node that adopts a behavior if the influence from active neighbours exceeds a personal threshold. In this thesis we address the problem faced by a social planner aiming to induce complete adoption through propagation while minimizing intervention costs. We analyze two intervention strategies: targeting, which selects individuals for direct activation, and partial incentive, which reduces thresholds to ease diffusion. Although both problems are NP-hard on arbitrary graphs, we prove that specific topologies admit polynomial-time exact algorithms.
We propose novel efficient algorithms for complete graphs with heterogeneous costs and complete multipartite graphs, and extend existing results on paths, trees, and cycles
Relatori
Anno Accademico
Tipo di pubblicazione
Numero di pagine
Corso di laurea
Classe di laurea
URI
![]() |
Modifica (riservato agli operatori) |
