Models and Algorithms for Addressing Challenges in Online Social Networks

QC 20250514

Abstract

Social network platforms such as Facebook and X (formerly Twitter) facilitate convenient access to news and discussions and enable individuals to express their opinions on societal issues. In recent years, numerous challenges have emerged as social network platforms present significant societal issues, such as increasing political polarization and the circulation of misinformation and disinformation. Malicious actors have exploited these platforms to target vulnerable individuals and manipulate the content they encounter on critical societal matters. Furthermore, algorithmic mechanisms implemented by these platforms, such as information filtering and personalized news feeds, have contributed to the formation of filter bubbles. The filter bubbles restrict individuals’ exposure to diverse perspectives and reinforce existing biases on societal issues. This thesis aims to deepen our understanding of emerging challenges in social network platforms by conceptualizing them as computational problems. We examine the intricate interplay between information flow, human interactions, and algorithmic interventions, selecting and proposing appropriate models to frame these dynamics. We transform complex real-world challenges into computational problems with precise mathematical formulations. We then analyze the complexity of these problems and design approximation algorithms to address them. This thesis comprises six publications and is organized around four research topics. First, we examine the capacity of malicious actors to amplify political polarization and shift individuals’ opinions toward extreme viewpoints. The two associated publications consider scenarios in which malicious actors either influence the opinions of a small subset of individuals or have extensive connections in the network. Second, we propose methods to mitigate filter bubbles by increasing individuals’ exposure to diverse information, achieved either through a viral marketing campaign or by adjusting the exposure of a small subset of individuals. Third, we analyze the impact of viral marketing campaigns on the opinion-formation process, introducing a model that integrates the dynamics of information dissemination with opinion formation. Fourth, we propose the OptiRefine framework for classical problems in social network analysis, such as the max-cut problem and the densest subgraph problem. The framework defines a class of problems for which an initial solution is given. The goal is to identify a new solution that remains close to the original while optimizing predefined objective functions, such as the cut value or the subgraph density. All proposed approaches are rigorously evaluated against multiple baseline algorithms and heuristics in all publications. 

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-363348