Uncovering Structure in Social Networks



Journal Title

Journal ISSN

Volume Title



Social networks are defined by relationships between people and permeate all aspects of human life. Improving our understanding of the structure and dynamics of networks enhances our knowledge of many human systems. In this dissertation, I present novel techniques and methodologies for the tasks of community detection, role discovery, and community evolution prediction as well as an analysis on temporal artifacts that may occur when constructing social network datasets. Community detection in networks is a broad problem with many proposed solutions. Existing methods frequently make use of edge density and node attributes; however, the methods ultimately have different definitions of community and build strong assumptions about community features into their models. I propose a new method for community detection, which estimates both per-community feature distributions (topics) and per-node community membership. Communities are modeled as connected subgraphs with nodes sharing similar attributes. Nodes may join multiple communities and share common attributes with each. Communities have an associated probability distribution over attributes and node attributes are modeled as draws from a mixture distribution. The method includes two basic assumptions about community structure: communities are densely connected and have a small network diameter. These assumptions inform the estimation of community topics and membership assignments without being too prescriptive. There has been extensive research on social networks and methods for specific tasks such as: community detection, link prediction, and tracing information cascades; and a recent emphasis on using temporal dynamics of social networks to improve method performance. The underlying models are based on structural properties of the network, some of which we believe to be artifacts introduced from common misrepresentations of social networks. Specifically, representing a social network or series of social networks as an accumulation of network snapshots is problematic. I demonstrate how cumulative graphs differ from activity-based graphs and may introduce temporal artifacts. Users in online social networks often have very different structural positions which may be attributed to a latent factor: roles. We analyze dynamic networks from two datasets (Facebook and Scratch) to find roles which define users' structural positions. Each dynamic network is partitioned into snapshots and we independently find roles for each network snapshot. I developed a role discovery methodology and investigate how roles differ between snapshots and datasets. Six persistent roles are found and user role membership, transitions between roles, and interaction preferences are analyzed and presented. Communities in social networks evolve over time as nodes enter and leave the network and their activity behaviors shift. I present a novel technique for predicting community evolution events based on group-node attention. Group-node attention enables support for variable-sized inputs and learned representation of groups based on member and neighbor node features, including temporal information. Existing work on community evolution prediction has focused on the development of frameworks for defining events while using traditional classification methods to perform the actual prediction. It is my hope this work on a prediction model for community evolution events will prompt the development of additional novel prediction models.