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. 

Sociala nätverksplattformar såsom Facebook och X (tidigare Twitter) underlättar bekväm tillgång till nyheter och diskussioner, samt möjliggör för individer att uttrycka sina åsikter i samhällsfrågor. Under de senaste åren har ett flertal utmaningar uppstått då dessa plattformar medför betydande samhällsproblem, såsom ökad politisk polarisering samt spridning av desinformation och missinformation. Illasinnade aktörer har utnyttjat dessa plattformar för att rikta sig mot sårbara individer och manipulera det innehåll de exponeras för i avgörande samhällsfrågor. Därtill har algoritmiska mekanismer som implementerats av plattformarna, såsom informationsfiltrering och personligt anpassade nyhetsflöden, bidragit till skapandet av så kallade filterbubblor. Dessa filterbubblor begränsar individers exponering för olika perspektiv och förstärker redan existerande fördomar i samhällsfrågor.

Denna avhandling syftar till att fördjupa vår förståelse för de framväxande utmaningarna med sociala nätverksplattformar genom att konceptualisera dem som beräkningsmässiga problem. Vi undersöker det intrikata samspelet mellan informationsflöde, mänsklig interaktion och algoritmiska ingripanden, och väljer samt föreslår lämpliga modeller för att rama in dessa dynamiker. Vi omformulerar komplexa verkliga utmaningar till beräkningsproblem med precisa matematiska formuleringar. Därefter analyserar vi problemen ur komplexitetssynpunkt och utvecklar approximationsalgoritmer för att hantera dem.

Avhandlingen består av sex publikationer och är organiserad kring fyra forskningsområden. För det första undersöker vi kapaciteten hos illasinnade aktörer att förstärka politisk polarisering och förskjuta individers åsikter mot extrema ståndpunkter. De två tillhörande publikationerna behandlar scenarier där illasinnade aktörer antingen påverkar åsikterna hos en liten grupp individer eller har omfattande nätverkskopplingar. För det andra föreslår vi metoder för att motverka filterbubblor genom att öka individers exponering för mångsidig information, antingen genom virala marknadsföringskampanjer eller genom att justera exponeringen för ett litet antal individer. För det tredje analyserar vi effekten av virala marknadsföringskampanjer på opinionsbildningsprocessen och introducerar en modell som integrerar dynamiken i informationsspridning med opinionsbildning. För det fjärde presenterar vi ramverket OptiRefine för klassiska problem inom analys av sociala nätverk, såsom max-cut-problemet och det tätaste delgrafsproblemet. Ramverket definierar en klass av problem där en initial lösning ges, och målet är att identifiera en ny lösning som ligger nära den ursprungliga, men som optimerar fördefinierade målfunktioner såsom snittvärde eller delgrafsdensitet. Alla föreslagna metoder har noggrant utvärderats mot flera baslinjealgoritmer och heuristiker i samtliga publikationer.