JavaScript is disabled for your browser. Some features of this site may not work without it.
Computational Perspectives On Large-Scale Social Networks

Author
Ugander, Johan
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.
Date Issued
2014-08-18Subject
social networks; graph partitioning; network experiments
Committee Chair
Kleinberg, Jon M
Committee Member
Huttenlocher, Daniel Peter; Strogatz, Steven H
Degree Discipline
Applied Mathematics
Degree Name
Ph. D., Applied Mathematics
Degree Level
Doctor of Philosophy
Type
dissertation or thesis