Friday, February 17, 2012 - 9:40am to 11:00am
KEC 1007

Speaker Information

Grant Schoenebeck
Simons Foundation Postdoctoral Fellow
Princeton University


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.

Speaker Bio

Grant Schoenebeck is currently the Simons Foundation Postdoctoral Fellow in Theoretical Computer Science at Princeton University, the Senior Postdoctoral Fellow at the Center for Computational Intractability, and a visitor at the Institute for Advanced Study. Dr. Schoenebeck studies how computational approaches and insights can help us to better understand the world we live in. His research interests span several fields of theoretical computer science including computational complexity theory and topics intersecting theoretical computer science and social and economic networks. He received his PhD in computer science from UC Berkeley, and graduated from Harvard University with highest honors in mathematics while also earning a master’s (SM) in computer science.