Massimo Bini
Optimal Targeting in Social Networks.
Rel. Fabrizio Dabbene, Paolo Frasca, Chiara Ravazzi. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2020

PDF (Tesi_di_laurea)
 Tesi
Licenza: Creative Commons Attribution Noncommercial No Derivatives. Download (1MB)  Preview 
Abstract: 
This thesis work considers a competition between two strategic agents who try to maximally influence a social network by targeting a finite number of nonstrategic/regular agents. We assume that regular agents adjust their opinion through a distributed averaging process, whereas the strategic agents present a fixed belief, towards which they try to shift the average opinion of the overall network by identifying the optimal targets to connect to. More specifically, the competition is set from the perspective of one of the strategic agents, as the optimization problem of selecting at most k regular agents to connect to in order to shift the network average opinion. Such a problem is known to be computationally hard, and effective heuristics are needed to reduce its complexity. The core of this thesis work consists in the technical results upon which these heuristics are built. In particular, we tackle the problem in two ways. On one hand, we provide an alternative proof (with respect to the literature) of the submodularity of the objective function, so as to reduce the problem to a greedy heuristic  in this way, rather than solving one computationally challenging optimal targeting problem, it is possible to find a suboptimal solution by solving k separate single targeting problems. On the other hand, we exploit the underlying graph structure to solve special instances of the problem, upon which we build more refined heuristics. As a first instance, we exploit the electrical analogy to provide the analytical solution for the single targeting problem over line graphs. Then, the peculiar behavior of the objective function over such a graph is proved to be extendable to generic tree graphs, by considering the tree branches as pseudoline graphs. From these findings, we define an algorithm which finds the optimal solution in a much faster way with respect to a bruteforce approach. Upon this result, then, we build heuristics that work for single targeting over sparse graphs. Nevertheless, as a second instance, we provide the analytical solution for the optimal targeting problem over complete graphs. The result here is huge, since it tells us in a simple way whether it is convenient or not to block the opponent's influence by targeting the same nodes. We then extend the same argument, with some modifications, to generic graphs in building the heuristics, generically leading the more accurate results with respect to the greedy approach. Upon these results, we combine blocking heuristics and greedy ones to get more accurate results, while we additionally combine them with degree based heuristics to save computational time. Finally, we compare on different special graphs and real social networks all these heuristics with respect to zero cost heuristics, built based on degree and blocking strategy. Summarizing the theoretical results, we obtain a scheme that tells which algorithm is more accurate and less computationally expensive, based on the underlying graph. 

Relators:  Fabrizio Dabbene, Paolo Frasca, Chiara Ravazzi 
Academic year:  2020/21 
Publication type:  Electronic 
Number of Pages:  120 
Subjects:  
Corso di laurea:  Corso di laurea magistrale in Ingegneria Matematica 
Classe di laurea:  New organization > Master science > LM44  MATHEMATICAL MODELLING FOR ENGINEERING 
Aziende collaboratrici:  UNSPECIFIED 
URI:  http://webthesis.biblio.polito.it/id/eprint/17078 
Modify record (reserved for operators) 