Discovering Social Network Structure
When: Friday, February 17, 2012 - 9:45am - 11:00am
Where: KEC 1007
Speaker Information
Speaker Name: Grant Schoenebeck
Speaker Title/Description:
Simons Foundation Postdoctoral Fellow
Princeton University
Speaker Biography:
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.
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.
_______________________________________________
Colloquium mailing list
[email protected]
https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
