As algorithmic systems increasingly shape human experiences, ensuring fairness and diversity has become a central challenge. This thesis studies fairness and diversity through the lens of algorithm design and optimization theory, providing formal frameworks and efficient algorithms across three domains: ranking-based recommendation, streaming recommendation, and graph analysis.

The first part of the thesis investigates diversity maximization in recommender systems with stochastic user engagement. We first study how to rank items in recommendation systems, where users engage with content sequentially and probabilistically. We introduce two novel diversity measures, sequential sum diversity and sequential coverage diversity, which account for uncertainty in user engagement. Our goal is to find a ranking of items that maximizes these sequential diversity measures. We show that sequential coverage diversity is ordered submodular, enabling a greedy 1/2-approximation. For sequential sum diversity, we provide polynomial-time constant-factor approximation algorithms. Separately, we study a streaming setting where items arrive continuously and users may visit the system multiple times at arbitrary moments. For this setting, we aim to design a streaming algorithm that maximizes a stochastic coverage diversity measure. We show that a classic greedy algorithm achieves a tight 1/2-competitive ratio but requires memory linear in the stream length. With sublinear memory and an upper bound T' on the number of user visits T, we propose STORM, which achieves a 1/4(T'-T+1)-competitive ratio. We further propose STORM++, improving the competitive ratio to 1/8delta, where the integer parameter delta controls the tradeoff between solution quality and computational cost.

The second part of the thesis studies diversity as a constraint in densest subgraph discovery and addresses the problem of finding dense communities in networks with heterogeneous relationship types. We model relationship types as edge colors and formulate the At Least h Colored Edges Densest Subgraph problem (ALHCEDGESDSP), which seeks subgraphs that are both dense and contain at least h_i edges of each color i. We prove that even the simplest variant of this problem is NP-hard and develop constant-factor approximation algorithms. Our key technical contribution links the edge-constrained and node-constrained versions of the densest subgraph problem. We first show that algorithms for the At Least k Nodes Densest Subgraph problem (DalkS) can approximate the At Least h Edges Densest Subgraph problem (ATLEASTHEDGESDSP), and then extend the algorithm for DalkS to handle colored edge constraints for solving ALHCEDGESDSP.

The third part of the thesis studies graph interventions for fairness in networks. We examine two fairness measures, PageRank fairness and hitting-time fairness, developing methods to balance influence and improve accessibility across groups. For each demographic group, the sum of PageRank scores within it quantifies the influence of that group. PageRank fairness measures how far the current group-wise influence deviates from a given target. We formulate the PageRank fairness problem as an optimization problem that adjusts edge weights such that the resulting graph achieves a group-wise influence distribution as close to the target as possible. The optimization problem involves a nonconvex objective over a convex feasible set under practical constraints, such as not adding new edges and limiting the magnitude of weight changes. We solve this PageRank fairness maximization problem using efficient projected gradient descent, proving convergence to a stationary point. For hitting-time fairness in bipartite graphs, we formulate two problems, minimizing the average (BMAH) and the maximum hitting time (BMMH) from one group to another via strategic edge additions. We provide a (2+epsilon)-approximation for BMAH by combining fast random walk simulation with greedy supermodular minimization. For the more challenging BMMH problem, we develop two approaches: the first leverages its connection to the BMAH problem, and the second employs a method based on the asymmetric k-center problem. Both approaches yield provable approximation guarantees for BMMH.

The algorithms and analysis techniques presented in this thesis contribute to the growing body of work on fairness and diversity in algorithmic systems. By formalizing new problem variants that capture realistic constraints in interactive and networked settings, and by providing approximation algorithms with provable guarantees, this work expands the toolkit available for addressing fairness and diversity challenges in computational systems.

Eftersom algoritmiska system i allt högre grad formar mänskliga upplevelser har det blivit en central utmaning att säkerställa rättvisa och mångfald. Denna avhandling studerar rättvisa och mångfald genom algoritm design och optimerings teori, och tillhandahåller formella ramverk och effektiva algoritmer inom tre domäner: rankningsbaserad rekommendation, strömmande rekommendation och grafanalys.

Den första delen av avhandlingen undersöker mångfaldsmaximering i rekommendationssystem med stokastiskt användarengagemang. Vi studerar först hur man rangordnar objekt i rekommendationssystem, där användare engagerar sig med innehåll sekventiellt och probabilistiskt. Vi introducerar två nya mångfaldsmått, sekventiell summa-mångfald och sekventiell täcknings-mångfald, som tar hänsyn till osäkerhet i användarengagemang. Vårt mål är att hitta en rangordning av objekt som maximerar dessa sekventiella mångfaldsmått. Vi visar att sekventiell täcknings-mångfald är ordnad submodulär, vilket möjliggör en girig 1/2-approximation. För sekventiell summa-mångfald tillhandahåller vi polynomtids konstant-faktor approximationsalgoritmer. Separat studerar vi en strömmande miljö där objekt anländer kontinuerligt och användare kan besöka systemet flera gånger vid godtyckliga tidpunkter. För denna miljö strävar vi efter att designa en strömmande algoritm som maximerar ett stokastiskt täcknings-mångfaldsmått. Vi visar att en klassisk girig algoritm uppnår ett tight 1/2-konkurrensförhållande men kräver minne linjärt i strömlängden. Med sublinjärt minne och en övre gräns T' på antalet användarbesök T, föreslår vi STORM, som uppnår ett 1/4(T'-T+1)-konkurrensförhållande. Vi föreslår vidare STORM++ som förbättrar konkurrensförhållandet till 1/8delta, där heltalsparametern delta kontrollerar avvägningen mellan lösningskvalitet och beräkningskostnad.

Den andra delen av avhandlingen studerar mångfald som en bivillkor i upptäckt av tätaste delgrafer och behandlar problemet med att hitta täta gemenskaper i nätverk med heterogena relationstyper. Vi modellerar relationstyper som kantfärger och formulerar problemet At Least h Colored Edges Densest Subgraph (ALHCEDGESDSP), som söker delgrafer som är både täta och innehåller åtminstone hi kanter av varje färg i. Vi bevisar att även den enklaste varianten av detta problem är NP-svår och utvecklar konstant-faktor approximationsalgoritmer. Vårt viktigaste tekniska bidrag kopplar samman kant-begränsade och nod-begränsade versionerna av tätaste delgraf-problemet. Vi visar först att algoritmer för problemet At Least k Nodes Densest Subgraph (DalkS) kan approximera problemet At Least h edges Densest Subgraph (ATLEASTHEDGESDSP), och utökar sedan algoritmen för DalkS för att hantera färgade kantbegränsningar för att lösa ALHCEDGESDSP.

Den tredje delen av avhandlingen studerar grafinterventioner för rättvisa i nätverk. Vi undersöker två rättvisemått, PageRank-rättvisa och träfftids-rättvisa, och utvecklar metoder för att balansera inflytande och förbättra tillgänglighet mellan grupper. För varje demografisk grupp kvantifierar summan av PageRank-poäng inom den gruppens inflytande. PageRank-rättvisa mäter hur långt den nuvarande gruppvisa influensfördelningen avviker från ett givet mål. Vi formulerar PageRank-rättvisaproblemet som ett optimeringsproblem som justerar kantvikter så att den resulterande grafen uppnår en gruppvis influensfördelning så nära målet som möjligt. Optimeringsproblemet involverar ett icke-konvext mål över en konvex genomförbar mängd under praktiska begränsningar, såsom att inte lägga till nya kanter och begränsa kantviktningsskalan. Vi löser detta PageRank rättvisemaximerings-problem med hjälp av effektiv projicerad gradientnedstigning, och bevisar konvergens till en stationär punkt. För träfftids-rättvisa i bipartita grafer formulerar vi två problem, att minimera medelvärdet (BMAH) och det maximala träfftidsvärdet (BMMH) från en grupp till en annan via strategiska kanttillägg. Vi tillhandahåller en (2+epsilon)-approximation för BMAH genom att kombinera snabb slumpvandrings-simulering med girig supermodulär minimering. För det mer utmanande BMMH-problemet utvecklar vi två tillvägagångssätt, det första utnyttjar dess koppling till BMAH-problemet, och det andra använder en metod baserad på det asymmetriska k center-problemet. Båda tillvägagångssätten ger bevisliga approximationsgarantier för BMMH.

Algoritmerna och analystekniker som presenteras i denna avhandling bidrar till den växande mängden arbete om rättvisa och mångfald i algoritmiska system. Genom att formalisera nya problemvarianter som fångar realistiska begränsningar i interaktiva och nätverksbaserade miljöer, och genom att tillhandahåller approximationsalgoritmer med bevisliga garantier, utökar detta arbete verktygslådan som finns tillgänglig för att hantera utmaningar kring rättvisa och mångfald i beräkningssystem.