CS673: Structure and Dynamics of Networked Information (Spring 2025)

Most recent message posted: 03/31/2025

Administrativa

• Time and Location: Monday and Wednesday, from 16:00-17:50, in room GFS 107.
• Instructor: David Kempe (office GHC 502L).
• Office hours: by appointment (i.e., drop by whenever you want to talk, but ideally give me a heads-up, so I'm there and not in a meeting). If you are unable to enter the 5th floor of GHC (typically if you're an undergraduate or MS student), let me know ahead of time, and we can meet on the first floor and go from there.
• There are no TAs.

Scope of Course

Thanks in large part to the Internet and World Wide Web, we are now seeing an explosion in networked resources, and in particular of networked information. The network structure and information content interact in many ways, creating challenging and exciting problems. A sample of the questions we will examine in the course: How does link structure between documents help us evaluate content, relevance, relatedness, or importance? What are natural models for the growth of networks? What graph-theoretic properties do these networks have? What properties of networks allow for easy routing or searching? How should we design networks to allow searching for information? How should we disseminate information through a network if we can design the network? How should we do it if we can't? Using tools from graph theory, linear algebra and probabilistic analysis, we will examine these questions focusing on the theoretical aspects.

Topics

• Properties of the Internet and WWW
• Latent Semantic Analysis, Eigenvector-based link analysis (HITS, PageRank, ...)
• Link-based classification
• Community Structure
• Models for graphs and graph growth
• Small-world networks and decentralized search
• Peer-to-peer systems
• Gossip, Broadcast, and Epidemic Algorithms
• Diffusion of information, Social networks

Prerequisites

• There are no formal prerequisites, but students who have not yet taken CS570 or CS670 (or have taken it and obtained a grade worse than A-) should check with the instructor, as they likely will not derive much benefit from the course.
• In addition, familiarity with mathematical reasoning, in particular basic linear algebra and probabilities, is required.

Readings and Assignments

The readings for the course will be mostly recent (and a few not so recent) research papers from the areas covered. A preliminary reading list is available, and will be updated as needed.

A good overview of the course material is given in Lecture notes for this course, but keep in mind that the original papers often contain significant additional material that will be of interest to students in the class. Thus, the lecture notes are meant as a guide, but not as a substitute for reading the original papers.

The grade will be based mostly on a substantial final project. In addition a few shorter reaction papers are assigned during the semester. There will not be a midterm or final exam.

The final project should be done in groups of usually 2-4 students. Individual projects or larger groups will only be approved in exceptional cases. Your project should draw on ideas from the class, and will often (but not necessarily) be based on ideas that one or more of you included in your reaction papers. It must have at least a small theory component, although it is acceptable if the bulk of the project is experimental, e.g., building a tool or exploring a particular data set. About 1 week into the project, your group should present a short (3-5 page) proposal to me, mostly so that I can provide feedback on the viability of your proposed work. At the end of the semester, the final project report is due, which should be about 10-15 pages long, and report on your results (and possibly also unsucessful ideas) in detail.

Messages

• 03/31/2025: As announced in class, you should start working on forming groups for your final project, and converging towards a project idea. Groups should be between 2-4 students each (3 being an ideal size). Your project topic should be inspired by class, and not just a repackaging of something you are already working on. Groups should submit project proposals by no later than Monday, April 14. I recommend earlier submissions, as that will let me give you feedback earlier, in case your project is too hard or otherwise should be modified. The ideas all of your group members discussed in your reaction papers may be good departure points for choosing a project topic.
• 03/31/2025: As announced in class, the third reaction paper has been assigned and is due in class on Monday, 04/07. It can be on any topic covered in class so far, except whatever you wrote about in your first two reaction papers.
• 03/06/2025: As announced in class on 03/05, the second reaction paper has been assigned and is due in class on Wednesday, 03/12. It can be on any topic covered in class so far, except whatever you wrote about in your first reaction paper.
• 02/05/2025: As announced in class on 02/03, the first reaction paper has been assigned and is due in class on Wednesday, 02/12.
• 01/12/2025: This page is where you will find relevant announcements about the class. The Brightspace page for the class will not be used.