[Colloquium] JOB TALK: Grant Schoenebeck, Princeton on February 22

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Wednesday, February 22, 2012
Time: 2:30 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:		Grant Schoenebeck

From:		Princeton University

Web page:	http://www.cs.princeton.edu/~gschoene/

Title: 		Discovering Social Network Structure

Abstract: 		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.

Host: Alexander Razborov

Refreshments will be served in Ryerson 255 following the talk at 3:30.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120208/13a71c46/attachment.htm