Algorithms, statistical models, and their applications to real-world networks and choice systems
- 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.
|Type of resource
|electronic resource; remote; computer; online resource
|1 online resource.
|Degree committee member
|Degree committee member
|Stanford University, School of Engineering
|Stanford University, Institute for Computational and Mathematical Engineering
|Statement of responsibility
|Submitted to the Institute for Computational and Mathematical Engineering.
|Thesis Ph.D. Stanford University 2023.
- © 2023 by Amel Awadelkarim
Also listed in
Loading usage metrics...