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, e.g. 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[subscript 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. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]