CSL 865: Special Topics in Computer Applications - Social Networks (Semester II 2007-2008)

Most of us have used (at least heard) of hugely popular online social networks such as Orkut, Facebook, Live Journal, and MySpace. These social networks have fundamentally altered how information is exchanged on the Internet and how users interact on the Internet. The purpose of this course is to study networked social networks such as the ones mentioned above. Specifically, we will study the structure and properties of online social networks, the evolution of online social networks, and the design of next-generation social networks. Were appropriate, we will try to understand how much online social networking is inspired by real world social networking.

This page provides information on the following:

Announcements

27/04/08: As discussed and mentioned time and again during lectures, Monday April 28 is the last day for submission of your project reports for the course. If I do not receive the reports by 4:30 PM on April 28, I will be awarding a zero for the project component of the course.
08/02/08: Presentation schedule for Feb 15th: note that Rakhi will present two paper, i.e., papers numbered 8 and 9 under the "small world" category.
08/02/08: We will read the Granovetter paper and the Klienberg paper for this coming Tuesday. Presenters, please carefully read the paper and prepare a presentation; pre-presentation reviewers, please bring a hard copy of your review.
08/02/08: Pre-presentation reviewers, please bring a hard copy of your report to class.
02/02/08: Presenters and reviewers for this coming Friday's class have been finalized. If you have any issues with the assigned tasks, please come and see me.
23/01/08: Presenters and reviewers for the next two classes have been finalized. Please check the reading list for details.
22/01/08: Today we will talk about project ideas. Come prepared with your thoughts.
16/01/08: The next presentation will be by Siddharth; Garima, Sonal, Vishal, and Mujtaba will write the pre-presentation reviews. We will discuss the paper: Measurement and Analysis of Online Social Networks by Mislove et al. from IMC 2007.
7/01/08: Course web page goes live!

Administrative Information

Here you will find administrative information for the CSL 865.

Textbook

This is a graduate-level seminar driven course. We will not follow any particular textbook; instead we will be discussing papers from the literature. A background in Computer Networks will be useful but is not a requirement for taking this course. If you do not have a background in Computer Networks, you may find the following textbook useful: The recommended textbook for this course is:

Since this course is research paper driven, you might want to read this very nice 2-page tutorial called How to Read a Paper by Prof. S. Keshav at U Waterloo.

Tentative Reading Schedule

Characterization of Online Social Networks

  1. Analysis of Topological Characteristics of Huge Online Social Networking Services, Y-Y Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong. Proc. of WWW '07.
    15/01/08 Presenter: Garima; Pre-presentation summary:

  2. Measurement and Analysis of Online Social Networks, A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, S. Bhattacharjee. Proc. of ACM IMC'07.
    19/01/08 Presenter: Siddharth; Pre-presentation summary: Garima, Sonal, Vishal, and Mujtaba

  3. Group Formation in Large Social Networks: Membership, Growth, and Evolution. Proc. of ACM KDD'06.
    29/01/08 Presenter: Neha; Pre-presentation summary: Himanshu, Siddharth, Anand, and Rakhi

  4. Structure and Evolution of Online Social Networks, R. Kumar, J. Novak, and A. Tomkins. Proc. of ACM KDD'06.
    01/02/08 Presenter: Arpit; Pre-presentation summary: Rakhi, Pankaj, Sonal, and Pratyush

Small World Phenomenon (From Sociology to the Web)

  1. The Small World Problem, S. Milgram. Psychology Today, 2(60), 1976.

  2. Navigation in a Small World, J. Kleinberg. Nature, Vol. 406, 845, 2000.

  3. Collective Dynamics of Small-World Networks, D. J. Watts and S. H. Strogatz. Nature, Vol. 393, 440-442, 1998.

  4. The Small-World Phenomenon: An Algorithmic Perspective, J. Kleinberg. Proc. of ACM STOC'00.
    08/02/08 Presenter: Pankaj Sharma; Pre-presentation summary:Neha, Pratyush, Mujtaba; Note: We should be reading papers 1-4 for this class.

  5. Graph Structure in the Web: Experiments and Models, A. Broder, R. Kumar, F. Maghoul, and J. Wiener. Proc. of WWW'00.
    08/02/08 Presenter: Abhishek Gramin; Pre-presentation summary: Arpit, Neeraj, Vishal

  6. Authoratative Sources in a Hyperlinked Environment, J. Klienberg. Journal of the ACM, 46:604-632, 1999.
    12/02/08 Presenter: Mujtaba; Pre-presentation summary: Pankaj, Niraj

  7. The Strength of Weak Ties: A Network Theory Revisited, M. Granovetter. Sociology Theory, Vol. 1, 1983, 210-233.
    12/02/08 Presenter: Anand; Pre-presentation summary: Rakhi, Neha

  8. Identity and Search in Social Networks, D. J. Watts, P. S. Dodds, M. E. J. Newman. Science, Vol. 269, 2002.
    15/02/08 Presenter: Rakhi; Pre-presentation summary: Neeraj, Anand, Siddharth

  9. Exploiting Social Networks for Internet Search, A. Mislove, K. P. Gummadi, and P. Druschel. HotNets 2006.
    15/02/08: Presenter and pre-presentation reviewers same as above. Try to summarize both papers in one presentation.

Complex Networks (Sampling Techniques and Statistical Properties)

  1. A Comparison of Sampling Techniques for Web Graph Characterization, L. Becchetti, C. Castillo, D. Donato, and A. Fazzone. Proc. of LinkKDD'06.
    15/02/08: Presenter: Pratyush; pre-presentation reviewers: Pankaj, Niraj, Garima.

  2. The Structure and Function of Complex Networks, M. J. Newman. SIAM Review, Vol. 45, 167-256, 2003.

  3. Statistical Properties of Sampled Networks, S. Lee, P. Kim, and H. Jeong. Physical Review E, 73, 2006.

  4. Emergence of Scaling in Random Networks, A. Barabasi and R. Albert. Science, 286:509-512, 1999.

  5. Distributed Uniform Sampling in Real-World Networks, A. Awan, R. Ferreira, S. Jagannathan, and A. Grama. Technical Report CSD-TR-04-029, Purdue University, 2004.

Potential Applications

  1. The Sybil Attack, J. R. Douceur, IPTPS 2002.

  2. Defending against Eclipse Attacks on Overlay Networks, A. Singh, M. Castro, P. Druschel, A. Rowstron. Sigops 2004.

  3. SybilGuard: Defending Against Sybil Attacks via Social Networks H. Yu, M. Kaminsky, P. B. Gibbons, A. Flaxman. Sigcomm 2006.

  4. RE: Reliable Email, S. Garriss, M. Kaminsky, M. J. Freedman, B. Karp, D. Mazieres. NSDI 2006.

  5. Exploiting Social Interactions in Mobile Systems, A. G. Miklas, K. K. Gollu, K. K. W. Chan, S. Saroiu, K. P. Gummadi, E. de Lara. Ubicomp 2007.

Miscellaneous

  1. On Six Degrees of Separation in DBLP-DB and More, E. Elmacioglu and D. Lee. Sigmod Record 2005.

  2. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes, E. K. Lua, J. Crowcroft, M. Pias, R. Sharma, S. Linn. IEEE Communications Surveys and Tutorials, Vol. 7, 2005.

  3. Efficient Private Techniques for Verifying Social Proximity, M. J. Freedman and A. Nicolosi. IPTPS 2007.

  4. Separating key management from file system security, D. Mazieres, M. Kaminsky, M. F. Kaashoek, E. Witchel. SOSP 1999.

  5. Decentralized User Authentication in a Global File System., M. Kaminsky, G. Savvides, D. Mazieres, M. F. Kaashoek. SOSP 2003.

  6. HomeViews: Peer-to-Peer Middleware for Personal Data Sharing Applications, R. Geambasu, M. Balazinska, S. D. Gribble, and H. M. Levy. Sigmod 2007.

Evaluation

The total for the course will be calculated using the weights given below. The weighted total will be converted to a letter grade according to IIT-D's grade point system.

  1. Presentation (30%): Each student is expected to present at least two research papers. Each presentation will be 30 minutes long, and should be prepared in electronic format (e.g., PPT, PDF). As a presenter, you are also responsible for leading the discussion of the paper along with the reviwers assigned for the paper (see below). I would expect you to make your presentation available to the class and me at least one day prior to your presentation.
  2. Pre-Presentation Paper Review (15%): Reviewers will be assigned to each paper being presented. I expect to assign each paper to between 2-3 students for reviewing. As a reviewer, you are expected to read the paper in detail and be ready to participate in the discussion of the paper. Your reviews are due 12 hours prior to the scheduled lecture time. Late submissions will not be graded. the paper being present
  3. Post-Presentation Paper Review (15%): Students who on a schdeuled lecture neither present a paper nor write a pre-presentation review of a paper will submit a post-presentation report of the paper. Your task is to summarize the salient points of the paper and to note any possible ideas discussed that may lead to a possible publication in the future. Implicit in this requirement is class participation. I expect students to attend all lectures and actively participate in the discussion of the research papers.
  4. Project (40%): Each student is expected to complete a project by the end of the semester. Projects can be undertaken individually or in groups of two. The project should take the form of a research paper, approximately 10-12 pages in length (using 10 pt font, double column, standard ACM conference template), including abstract, figures, tables, and bibliography. The paper should demonstrate your creativity, originality, and contributions in the chosen topic. Your goal should be to produce a project which with some effort can produce a high-quality publication. A survey paper is not acceptable as a project.

    Note that the project accounts for a significant portion (40%) of the final grade for the course, and thus should represent about 1.5 months of significant research effort. It is also important to start thinking about the project early in the semester. A concise (2 page) project proposal will be required by the end of week 4. This proposal should describe the goals and objectives of the project, and why the project is worthwhile doing. The proposal should present the proposed research in the context of previous work in the chosen area.