Lecture by Dr. Christian Borgs of Microsoft Research for the Computer Science Department (Prof. M. Karpinski)

Friday, 14:00 (2 PM), Location: Hausdorff Research Institute, Poppelsdorfer Allee 45, main lecture hall

Title: " Modeling Social Networks: From Network Formation to Community Detection"



In the first part of this talk, I will consider a new game theoretic model of network formation. The model is motivated by the observation that the social cost of relationships is often the effort needed to maintain them. In contrast to many popular models of network formation whose equilibria tend to be complete graphs or trees, our model has equilibria which support many observed network structures, including triadic closure and heavy-tailed degree distributions. This part of the talk represents work with J.T. Chayes, J. Ding and B. Lucier. If time permits, I will then turn to recent work by N. Balcan, M. Braverman, J.T. Chayes, S.-H. Teng, and myself in which we give an algorithm to discover overlapping communities within a social network.