Behaviors, Interactions, And Communities In Networks

Abstract

Exciting and unexpected patterns can emerge when systems are highly connected, even when they are composed of the simplest objects. In this thesis we investigate how networks of people, oscillators, apps, and nodes can be better understood through the behavior of the communities that emerge from their close interactions. Work in this thesis first examines how recent advances in dynamical systems have shed new light on the macrobehavior of networks of coupled oscillators. The dimensionality of the system is greatly reduced by viewing the system not as one of individual coupled oscillators, but as one of a smaller number of interacting groups. We demonstrate that the corresponding governing equations can be solved exactly. This thesis then investigates the seed set expansion problem, or how to uncover the local community structure hidden around nodes, in social and other real-world networks. We explore how topological properties of communities and seed sets correlate with algorithm performance, and explain these empirical observations with theoretical ones. We then turn our focus back to a theoretical setting and develop a principled framework for evaluating ranking methods by studying seed set expansion applied to the stochastic block model. We derive the optimal gradient for separating the two classes of nodes in a stochastic block model, and find, surprisingly, that it is asymptotically equivalent to personalized PageRank. This connection provides a novel formal motivation for the success of personalized PageRank in seed set expansion and node ranking generally. We then leverage this framework to develop several theoretically motivated heuristics that incorporate higher moments of landing probabilities, and show that these techniques yield much stronger performance on seed set expansion for stochastic block models. Work in the second part of this thesis discusses two other highly connected networks, the Facebook social network, and the network of communication between researchers in a series of massive collaborations. In the first case we develop a retention model that accurately models users' tendencies to continue using apps, and at the social level we organize apps along two fundamental axes - popularity and sociality - and show how a user's probability of adopting an app depends on properties of both the local network structure and the match between the user's attributes, their friends' attributes, and the dominant attributes within the app user population. We show how our models give rise to compact sets of features with strong performance in predicting app success. In the second case we study a series of massive online collaborations of professional and amateur mathematicians, who collectively attempt to solve open problems in mathematics research. We identify interesting patterns in the linguistic structure and social reactions that distinguish important research contributions from less important ones. We also observe distinct changes in the language behavior, and the structure and timing of interactions between the same group of contributors depending on whether they are working on a research problem, or simply a very difficult but solved problem taken from the International Math Olympiad.