Influence maximization in social networks has attracted considerable attention during the past 20 years. With the explosive growth of malicious rumour in online social networks, the reverse problem of contrasting their diffusion has become very important. In this thesis, we investigate an optimization problem referred to as the least cost rumour influence limitation problem. Given a network, a set of initial promoters of a malicious rumours (propagating under a linear threshold model) and a cost for blocking each node, one has to decide which nodes to block so as to limit the spread of the rumour below a predefined fraction of network nodes, while minimizing the total blocking cost. We consider two problem variants within a specified time horizon: the single-step one with fixed costs, and the multi-step one with unit-period costs. First we propose time-indexed Integer Linear Programming (ILP) formulations for the two variants. Then, aiming at good quality solutions within a reasonable computing time, we develop various randomized heuristic algorithms. Carefully selected greedy criteria combined with adaptations of truncated mixed and evolutionary path-relinking are developed for the single-step problem variant, while a sampled iterative randomized greedy algorithm with an additional ad-hoc look ahead criterion is devised for the more complex multi-step variant. Computational experiments on instances up to 400 nodes for which the ILP formulations can be solved to optimality indicate that our heuristic algorithms provide solutions with an average gap between 0.8% and 3.5% for the single-step variant, and between 1.2% and 5.2% for the multi-step one. For larger size instances with 1000 nodes, our algorithms yield significant improvements within a reasonable computing time.
La massimizzazione dell'influenza nelle reti sociali ha attirato molta attenzione negli ultimi 20 anni. Con la crescita esplosiva di informazioni false e ingannevoli nelle piattaforme social online, il problema inverso di contrastare la loro diffusione è diventato molto importante. In questa tesi esaminiamo un problema di ottimizzazione che chiamiamo "least cost rumour influence limitation problem". Data una rete, una serie di promotori iniziali di una diceria malevola (che si propagaga tramite un modello di tipo "linear threshold") e un costo per bloccare ciascun nodo, si deve decidere quali nodi bloccare in modo da limitare la diffusione della diceria entro una frazione predefinita dei nodi, minimizzando il costo totale del bloccaggio. Consideriamo due varianti del problema all'interno di un orizzonte temporale specificato: una detta "single-step" con costi fissi, e una'altra detta "multi-step" con costi che si rinnovano ad ogni istante di tempo. Per prima cosa proponiamo formulazioni di programmazione lineare intera (ILP) indicizzate nel tempo per le due varianti. Quindi, con l'obiettivo di ottenere soluzioni di buona qualità in un tempo di calcolo ragionevole, sviluppiamo vari algoritmi euristici randomizzati. Per la variante "single-step" vengono sviluppati algoritmi che associano criteri di tipo greedy accuratamente scelti con adattamenti di tipo "truncated mixed path-relinking" e "evolutionary path-relinking", mentre per la più articolata variante "multi-step" viene ideato un algoritmo iterativo di tipo "sampled greedy" randomizzato, combinato con un aggiuntivo criterio appositiamente perfezionato. Esperimenti computazionali su istanze fino a 400 nodi per le quali le formulazioni ILP possono essere risolte all'ottimo, indicano che i nostri algoritmi euristici forniscono soluzioni con un gap medio tra 0.8% e 3.5% per la variante "single-step" e tra 1.2% e 5.2% per quella "multi-step". Per istanze di dimensioni maggiori con 1000 nodi, i nostri algoritmi offrono miglioramenti significativi in tempi computazionali ragionevoli.
Contrasting malicious rumour diffusion in social networks : least cost models and algorithms
RANZANI, PAOLO
2018/2019
Abstract
Influence maximization in social networks has attracted considerable attention during the past 20 years. With the explosive growth of malicious rumour in online social networks, the reverse problem of contrasting their diffusion has become very important. In this thesis, we investigate an optimization problem referred to as the least cost rumour influence limitation problem. Given a network, a set of initial promoters of a malicious rumours (propagating under a linear threshold model) and a cost for blocking each node, one has to decide which nodes to block so as to limit the spread of the rumour below a predefined fraction of network nodes, while minimizing the total blocking cost. We consider two problem variants within a specified time horizon: the single-step one with fixed costs, and the multi-step one with unit-period costs. First we propose time-indexed Integer Linear Programming (ILP) formulations for the two variants. Then, aiming at good quality solutions within a reasonable computing time, we develop various randomized heuristic algorithms. Carefully selected greedy criteria combined with adaptations of truncated mixed and evolutionary path-relinking are developed for the single-step problem variant, while a sampled iterative randomized greedy algorithm with an additional ad-hoc look ahead criterion is devised for the more complex multi-step variant. Computational experiments on instances up to 400 nodes for which the ILP formulations can be solved to optimality indicate that our heuristic algorithms provide solutions with an average gap between 0.8% and 3.5% for the single-step variant, and between 1.2% and 5.2% for the multi-step one. For larger size instances with 1000 nodes, our algorithms yield significant improvements within a reasonable computing time.| File | Dimensione | Formato | |
|---|---|---|---|
|
thesis.pdf
accessibile in internet per tutti
Descrizione: Testo della tesi def
Dimensione
3.01 MB
Formato
Adobe PDF
|
3.01 MB | Adobe PDF | Visualizza/Apri |
I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/10589/154071