Dynamics and Social Networks

Social networks are everywhere in everyday life. We aggregate information, make decisions, and form opinions through these interactions on social networks. This thesis aims to improve our understanding of social network structures, social network dynamics, including the spread of social contagions, opinion formation, and myopic routing.

We first consider complex contagions where a node requires several infected neighbors before becoming infected itself, and give a theoretical analysis of which properties of social networks, small-world properties, power-law degree distribution, time evolving, and community structure, can affect the spread of contagions. Finally, we consider the influence maximization problem on social networks with community structure when the contagions are complex.

For social network structures, we begin with the role of strong and weak ties. Exploiting the idea of strong ties we propose a Sybil Detection algorithm which prevents an adversary from creating a large number of identities to attack a recommendation system. Later, we study the role of weak ties in echo chambers and bubble filters.

Finally, we focus on opinion formation and community structures. We propose a family of general rich-get-richer dynamics which includes several well-studied models as special cases and shows this family of dynamics reaches consensus fast on graphs close to complete graph, dense Erd\"os-R\'enyi graphs. In contrast to this result, we prove a dichotomy theorem about community structures and these richer-get-richer dynamics.