Browsing by Author "Gionis, Aristides, Adj. Prof., Aalto University, Department of Computer Science, Finland, KTH Royal Institute of Technology, Sweden"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Scalable algorithm designs for mining massive datasets(Aalto University, 2022) Thejaswi, Suhas; Ordozgoiti, Bruno, Lecturer, Queen Mary University of London, UK; Tietotekniikan laitos; Department of Computer Science; Perustieteiden korkeakoulu; School of Science; Gionis, Aristides, Adj. Prof., Aalto University, Department of Computer Science, Finland, KTH Royal Institute of Technology, SwedenCombinatorial problems are everywhere, starting from operations-research problems such as finding connectivity for efficient network design, placement of facilities such that the travelling distance from clients to facilities is minimized, detecting patterns in database transactions and genetic material, contact tracing in epidemic- propagation networks, and efficient advertising in social media, among others. Many of these aforementioned problems are known to be computationally intractable, meaning that, no efficient solutions are known to solve these problems. Despite being intractable, these problems have enormous impact on the society and our day-to-day activities, which prompts us to find effective solutions that can practically solve large instances of these real-world problem scenarios. A broad topic of this thesis is to design algorithms that can practically solve a set of computationally-intractable problems under restrictive settings, using mathematical abstractions and computational tools. In particular, the problems of our interest include pattern detection in graphs and data clustering with fairness constraints. Pattern detection in graphs is the problem of deciding the existence of a smaller subgraph in a usually larger graph. The problem has applications in understanding complex biological and metabolic systems, discovering controversies in social media discussions, studying epidemic propagation in contact networks, among others. Clustering with fairness constraints is the problem of grouping similar objects together in to clusters, while simultaneously taking a fairness notion into consideration. The fairness notion arise from different societal norms, including, avoiding discrimination based on gender, race, ethnicity and financial status, among others. This thesis is organized around many algorithmic techniques and computational tools for the design of algorithms that can practically solve large instances of intractable problems. These computational tools include, parameterized algorithms, approximation algorithms, heuristics, and implementation engineering. We introduce novel-problem formulations in the field of pattern detection and data clustering, analyze the computational complexity of problems that we introduce, and present algorithmic solutions that can solve these problems under restrictive settings, that is, when certain parameters of the problem are small. In cases where it is not possible to design efficient algorithmic solutions, we present careful validations in the form of computational-complexity results, lower bound on the running time, and lower bound on the approximation factor. Finally, we present carefully engineered implementation of our proposed algorithmic solutions, and validate our scalability claims using both synthetic and real-world datasets.Item Social Media for Social Good: Models and Algorithms(Aalto University, 2022) Matakos, Antonis; Tietotekniikan laitos; Department of Computer Science; Perustieteiden korkeakoulu; School of Science; Gionis, Aristides, Adj. Prof., Aalto University, Department of Computer Science, Finland, KTH Royal Institute of Technology, SwedenSocial media employ algorithms to promote content that their users would find interesting, so as to maximize user engagement. Therefore they act as a lens, through which an individual looks at reality, or a "filter". These filters create alternative "digital realities" for participants of social networks. A "filter bubble" refers to the state of ideological isolation resulting from social media personalization algorithms. In this thesis we propose approaches to algorithmically break these filter bubbles. In order to successfully break filter bubbles we come up with methods to detect them, and characterize their strength. First, we look at measuring polarization of opinions, which is a typical manifestation of a filter bubble. Our approach is based on a well-known opinion formation model, and is based on characterizing the random-walk distance of all individuals to the two opposing opinions present in the polarized discussion. We then turn our focus to signed networks, where relationships are characterized by friendship or enmity. We aim to find the maximum possible partition of the graph into two opposing hostile factions. Then, in another line of work, comprising of two papers, we look at measuring the diversity of the exposure of individuals to different opinions. In the first paper, we look at the difference of the values describing information exposure, across all edges in a social graph. In the second, we measure diversity with respect to a model of news item propagation in a network, based on a variant of the well-studied independent cascade model. Subsequently, we propose algorithmic interventions to break filter bubbles, based on the aforementioned measures of polarization and diversity of exposure. Regarding polarization, we consider the task of moderating the opinions of a small subset of individuals in order to minimize polarization. With respect to diversity of exposure, we consider it a beneficial quantity, which should be maximized. Therefore, we consider the problem of maximizing the diversity index, by changing the exposure of a small subset of individuals to the opposite one. Regarding the "lack of diversity of exposure", we define a function to be maximized, that contains its negation. The resulting maximization problem consists of selecting a small subset of individuals to share a set of news articles in their network, starting multiple parallel cascades. Finally, we examine a different type of intervention that does not directly optimize any measure. We organically increase the number of edges in a network, by leveraging the strong triadic closure property, a well known principle from sociology. Given this property, we ask the question "which friendships should be converted from weak to strong in order to maximize the potential for new edges?". For all proposed problems we present a complexity analysis, and in most cases, we offer performance guarantees. We evaluate our methods on real-life social networks and we compare them against some baselines.