Social Networks: Models and Applications
Fall 2007

This Term

Today's social networking Web sites, such as YouTube, Flickr, or MySpace, attract millions of users. These sites allow users to share their own data. For example, Skype has very recently added a feature to their VoIP application that allows users to share reviews/recommendations with friends on their contact list. While already being hugely popular, these applications only scratch the surface of what seems to be possible. Making more sophisticated use of social networking applications requires a better understanding of (1) how online social networks are formed, and (2) how these networks can be used to efficiently share/distributed information.

In this seminar, We will study these issues by discussing recent papers on mathematical models for social networks together with applications that make use of social networks. Participants are expected to present a paper. This seminar is organized by Yashar Ganjali, Nick Koudas, Peter Marbach, and Stefan Saroiu.

List of Topics

• September 18th
  Overview and Introduction.

• September 25th
  Navigation in a Small World. Jon Kleinberg. Nature 406(2000), 845.
  Discussion Leader: George Giakkoupis (slides).

• October 2nd
  On a Network Creation Game. A. Fabrikant, A. Luthra, E. Maneva, C. Papadimitriou, S. Shenker. PODC 2003.
  On Nash Equilibria for a Network Creation Game. S. Albers, S. Eilts, E. Evan-Dar, Y. Mansour, L. Roddity. SODA 2006.
  Discussion Leader: Stratis (slides)

• October 9th
  A Small World Threshold for Economic Network Formation. E. Evan-Dar and M. Kearns. NIPS 2006.
  A Network Formation for Bipartite Exchange Economies. E. Evan-Dar, M. Kearns, and S. Suri. SODA 2007.
  Discussion Leader: Xiaoyang (slides).

• October 16th
  Implication of Selfish Neighbor Selection in Overlay Networks. N. Louotaris et al.
  On the Topologies Formed by Selfish Peers. T. Moschibroda, S. Schimd, and R. Wattenhoger.
  Discussion Leader: Felix and Larry (slides).

• October 23rd
  Collaborate with Strangers to Find Own Preferences. B. Awerbuch et al.
  Tell Me Who I am: An Interactive Recommendation System. N. Alon.
  Discussion Leader: TBA.

• October 30th
  Convergent Algorithms for Collaborative Filtering. Jon Kleinberg.
  Discussion Leader: TBA.

• November 6th
  Social Recommendation Systems (Collaborative Filtering). Nick Koudas.
  Discussion Leader: TBA.

• November 12th
  Information Diffusion. Nick Koudas.
  Discussion Leader: TBA.

• November 19th
  Information Diffusion. Nick Koudas.
  Discussion Leader: TBA.

• November 26th
  Social Networking Applications. Yashar Ganjali and Stefan Saroiu.
  Discussion Leader: TBA.

• December 4th
  Social Networking Applications. Yashar Ganjali and Stefan Saroiu.
  Discussion Leader: TBA.