Discovering Social Network Structure

What do social networks look like? With increasing amounts of data and computational power, it seems like we are closer than ever to answering this question. However, there may be limits to the kinds of properties that can be reconstructed from sampled data. Moreover, even if we had all the data, we might still be asking computationally infeasible questions that require solving intractable problems. For example, can we really expect to uncover all the dense regions of a social network when in the worst case this problem is NP-hard? This talk will be a computer scientist's view of where we are in our understanding of social network structure and what future directions may lead to deeper insights.

I will present recent work which shows that many structural properties can appear in sampled networks even when the networks the sample is drawn from do not contain these properties. Next, I will show that, while the problem of detecting community structure is NP-hard in the worst-case, overlapping communities can be recovered efficiently in many cases of interest. This work initiates a rigorous approach to the problem of finding overlapping communities, where "rigorous" means that we clearly state the following: (a) the object sought by our algorithm (b) the assumptions about the underlying network (c) the (worst-case) running time. Our assumptions about network parameters draw on a long body of work in the sociology community focusing on the study of individual communities and ego-centric networks"”thus our assumptions are somewhat "local" in nature. Nevertheless they suffice to permit a rigorous analysis of the running time of algorithms that recover global structure.