Social Media for Social Good: Models and Algorithms

Social 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.