Algorithms, statistical models, and their applications to real-world networks and choice systems
Abstract/Contents
- Abstract
- With the rise in popularity of social media and e-commerce platforms, discrete math is at the heart of our online experiences, playing a front-end role in the recommendation of what to click, watch, or buy, or who to follow or friend, as well as a back-end role in data storage, access, and transfer. This thesis focuses on two such discrete math problems -- the modeling of discrete choices, and the efficient storage of massive graphs. On the latter, we study the problem of balanced graph partitioning, a problem of paramount importance in domains such as graph clustering, community detection, distributed graph computation, and also efficient data storage. Chapter 2 introduces a taxonomy of existing algorithms for finding a balanced partitioning of an input graph, and pioneers a novel class of prioritized restreaming algorithms, showcasing their superior performance in minimizing the edge-cut objective over industry state-of-the-art methods. We investigate the former, the statistical modeling of choices and rankings, in the context of social choice, eg. school choice and ranked-choice-voting. Such models are used for explanation of user behaviors, forecasting demand, or counterfactual analysis. Chapter 3 unveils the significance of within-agent taste-heterogeneity in the assembly of ranked preference lists, giving rise to the concept of rank-heterogeneous preference models. Applied to real-world school-choice data, these models demonstrate enhanced predictive accuracy and a better fit to observed ranking patterns than commonly-used rank-homogeneous strategies. Chapter 4 further extends the frontier by drawing attention to an under-studied task in the ranking modeling literature -- the modeling of partial orders. Specifically, this task is concerned with the development of models whose sample space is the space of orderings of any length of n items, a space that subsumes S_n. The work develops two classes of models, composite and augmented, and demonstrates their potential for simultaneously capturing preferences and length distributions within real-world partial ranking data from school choice and ranked-choice voting contexts.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2023; ©2023 |
| Publication date | 2023; 2023 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Awadelkarim, Amel |
|---|---|
| Degree supervisor | Ugander, Johan |
| Thesis advisor | Ugander, Johan |
| Thesis advisor | Ashlagi, Itai |
| Thesis advisor | Lo, Irene, (Management science professor) |
| Degree committee member | Ashlagi, Itai |
| Degree committee member | Lo, Irene, (Management science professor) |
| Associated with | Stanford University, School of Engineering |
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Amel Awadelkarim. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2023. |
| Location | https://purl.stanford.edu/sd306sc0215 |
Access conditions
- Copyright
- © 2023 by Amel Awadelkarim
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...