Optimal Targeting in Social Networks

This thesis work considers a competition between two strategic agents who try to maximally influence a social network by targeting a finite number of non-strategic/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 pseudo-line graphs. From these findings, we define an algorithm which finds the optimal solution in a much faster way with respect to a brute-force 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.