Theses Doctoral

Algorithmic Design for Social Networks: Inequality, Bias, and Diversity

Stoica, Ana-Andreea

Algorithms that use relational data are increasingly used to allocate resources within society. As researchers and decision-makers have adapted the role of algorithms from a descriptive one (describing patterns in data) to a prescriptive one (making decisions in predictive systems), there is an increasing concern that algorithms may replicate and even amplify societal bias, allocating worse or less resources to minorities and underrepresented groups. This dissertation proposes methodology for diagnosing when and how algorithms amplify inequality on networks as well as designing interventions for mitigating algorithmic bias.

We leverage methods from network modeling, algorithmic game theory, and fair machine learning to uncover the root driver of bias in network data and to leverage this knowledge in order to design fair algorithms. In this thesis, we mostly focus on unsupervised learning problems, which present unique challenges that require a multi-faceted approach. We propose a unifying formulation for unifying different problems in unsupervised learning on networks and use it to propose methods to find the root cause of bias through modeling patterns of connections and embeddings. We leverage this knowledge to design fairer algorithms as well as to define diagnoses metrics for evaluating inequality before and after an algorithm is introduced. Furthermore, we argue for the need to bridge optimization-based learning and utility-based learning in creating stable, efficient, and useful systems.

We use network models and mathematical formulations of distributional inequality in diagnosing the algorithmic amplification of bias in social recommendations and ranking algorithms. We find that the most common and neutral algorithms may further underrepresent minority groups in creating new connections or achieving high levels of visibility in networks that exhibit competition in increasing social capital and homophily (the tendency of people to connect with those similar to them). We uncover the role of homophily in helping a minority group overcome their initial disadvantage and we leverage it to design fairer information campaigns that equitable distribute messages across a population.

Akin to this goal, we incorporate notions of utility and welfare in our algorithmic design, re-designing heuristics for grouping and clustering that improve the diversity of groups while preserving their usefulness, with applications in political and educational districting. Overall, this set of results aims to investigate the impact of algorithms on the outcomes of different populations and to open new avenues for inter-disciplinary research methods that can alleviate algorithmic bias. We close by discussing connections between different fields and methods as well as directions for future research.


  • thumnail for Stoica_columbia_0054D_17421.pdf Stoica_columbia_0054D_17421.pdf application/pdf 32.7 MB Download File

More About This Work

Academic Units
Computer Science
Thesis Advisors
Chaintreau, Augustin
Ph.D., Columbia University
Published Here
August 17, 2022