Titolo della tesi: On the Impact of Graph Structure on (Mis)Information Diffusion and Polarized Niches Identification in Social Networks
Social networks play a crucial role in modern society, weaving into the daily lives of the vast majority of people. They have become the primary arenas for public discourse. In this thriving participatory environment, accessible to all, individuals can easily engage in societal discussions by expressing their viewpoints. This environment is extensively utilized by authorities and official entities, as well as various sources of low-quality information and even misinformation. Considering the ubiquity of social networks and the ease with which misinformation can proliferate, it is imperative to investigate the dynamics of (mis)information propagation and persistence within these networks.
This Ph.D. thesis delves into the role of network structure in the spread and persistence of (mis)information.
First, we demonstrate how the structure of a social network can be leveraged to identify user niches prone to misinformation and polarization. We model polarization niches as close-knit, dense communities of users under the influence of well-known sources of misinformation, isolated from authoritative information sources. Based on this intuition, we define the problem of finding a subgraph that maximizes a combination of (i) density, (ii) proximity to a small set of nodes $A$ (referred to as \textit{Attractors}), and (iii) distance from another small set of nodes $R$ (referred to as \textit{Repulsers}). Diverging from the bulk of the literature on detecting polarization, we do not rely on text mining, sentiment analysis, or track information propagation. Instead, we solely leverage the network structure and background knowledge about sets A and R provided as input. Building upon recent algorithmic advancements in \textit{supermodular maximization}, we offer an iterative greedy algorithm dubbed \textit{Down in the Hollow} (DITH) that converges rapidly to a near-optimal solution. Thanks to a novel theoretical upper bound, it includes a practical feature allowing for termination as soon as a solution with a user-specified approximation factor is found, rendering DITH very efficient in practice. Our experiments on very large networks confirm that our algorithm always returns a solution with an approximation factor better or equal to the one specified by the user, and it is scalable. Our case studies in polarized settings confirm the usefulness of our algorithmic primitive in detecting polarization niches.
Second, we obtain tight thresholds for bond percolation on one-dimensional small-world graphs, that are random networks sampled from a network generative model distinguishing local and long-range connections, and apply such results to obtain tight thresholds for the Reed-Frost process in such graphs. Although one-dimensional small-world graphs are an idealized and unrealistic network model, several realistic qualitative epidemiological phenomena emerge from our analysis, including the epidemic spread through a sequence of local outbreaks, the danger posed by random connections, and the effect of super-spreader events.