The Degree of Segregation in Social Networks: Nicole Immorlica, Northwestern, MSR NE

11:00 am on Wednesday, February 6, 2013
12:00 pm on Wednesday, February 6, 2013
MCS 148
Abstract: Social networks form the basic medium of social interaction. The structure of these networks significantly impacts and co-evolves with the behavioral patterns of society. Important societal outcomes – the global reach of an epidemic, the degree of cooperation in an online network, the adoption of new technologies – are dictated by social networks. In this talk, we explore the impact of networks on segregation. In 1969, economist Thomas Schelling introduced a landmark model of racial segregation in which individuals move out of neighborhoods where their ethnicity constitutes a minority. Simple simulations of Schelling's model suggest that this local behavior can cause global segregation effects. In this talk, we provide a rigorous analysis of Schelling's model on ring networks. Our results show that, in contrast to prior interpretations, the outcome is nearly integrated: the average size of an ethnically-homogenous region is independent of the size of the society and only polynomial in the size of a neighborhood. Joint work with Christina Brandt, Gautam Kamath, and Robert D. Kleinberg. Bio: Nicole Immorlica is a researcher at Microsoft Research in New England (MSR NE) and an assistant professor in EECS at Northwestern University. She received her PhD from MIT in 2005 and continued on to do postdocs at Microsoft Research and Centruum voor Wiskunde en Informatica (CWI) before starting her tenure-track job. She is the recipient of various fellowships and awards including the NSF CAREER Award, the Sloan Fellowship and the Microsoft New Faculty Fellowship. Her research interests lie in the field of algorithmic game theory, specifically social networks, market design, and mechanism design.