Detecting and Tracking Communities in Social Networks

Community detection is an important task in social network analysis. Social interactions exist within some social context and communities are a fundamental form of social contexts. Communities are intuitively characterized as “unusually densely knit” subsets of a social network. This notation becomes more problematic if the social interactions change over time. The interplay between social interacts and social contexts are crucial to understand the evolution of networks. Thus, it is important to both detect communities and track their changes. My contributions fall into two categories. First, I consider the problem of tracking communities over time, assuming that partitions into communities are already given for all snapshot graphs. The question is which community snapshot becomes which community snapshot at another point in time. My contributions to the first part are models and algorithms for tracking communities. I show a constant-factor approximation algorithm based on path cover, another algorithm based on a state-of-the-art approximation algorithm for the Correlation Clustering problem, and a fast heuristic algorithm which produces even better solutions in practice than the two prior algorithms. Tools developed for this task can be used for longitudinal social network analysis, ecological inference, etc. Secondly, I consider the combined problem of detecting communities in network snapshots and simultaneously tracking them. For this second part, I show an algorithm based on the state-of-the-art approximation algorithm, similar to the above. This gives the first algorithm for the dynamic community detection problem which produces a numerical approximation guarantee of a solution.