Computational Perspectives On Large-Scale Social Networks

Abstract

This thesis investigates both how computational perspectives can improve our understanding of social networks, and also how modern insights about social networks can be put to work to address difficult computational and inferential challenges across systems engineering and the social sciences. The microstructure of human behavior has a rich history of study across many disciplines, and only recently - through the data deluge of online instrumentation and experimentation - has the role networks play across social and economic domains come into full view. Work in this thesis examines how social network neighborhoods, the rich local networks that surround individuals, function as contact surfaces through which individuals process information, mediating social decision and social contagion processes. Work in this thesis on distributing graph computations at Facebook, the online social networking service, has led to dramatic efficiency gains there, successfully deploying a new partitioning algorithm to reduce average query times for their "People You May Know" link prediction system by 50%. These improvements were achieved by harnessing both geographic and network structures of social graphs not necessarily found in other graph contexts. Additional work presents a highly scalable "restreaming" approach to partitioning massive graphs with rich local structure. Lastly, work on interference in online experiments (A/B tests) offers a framework based on graph partitioning to design lower variance estimators for treatment effects under network interference, a grand challenge of modern online experimentation. As individuals bring their social relations online, the web is rapidly evolving from a network of documents to a network of people, and computing with social data will require richer, novel methods for working with the subtleties that give social networks their distinctive character.