Project Description

The project provides an opportunity for students to learn about a topic of interest to them as well as to teach other students in the class. Each project team should consist of two or three students. The project consists of a written paper (typically 10 to 15 double spaced pages) as well as an in-class oral presentation of 20 minutes. The project should have some connection to "Network Optimization" and should be original. In particular, the project should not consist primarily of research that was developed for another subject or for a thesis at MIT. But it is acceptable (and desirable) if the project has synergies with other projects at MIT.

The project can be on a theoretical topic, an applied topic, or a computational topic.

The project counts for 16% of the final grade.

Deliverables

Ses #11: Choose your teammates and the topic for your project. Submit the names of the people in the team and the topic of your project.

Ses #17: Submit a written outline that includes a title and a brief description of the presentation's coverage and describes what you hope to teach your classmates.

Ses #24: Written report (around 10-15 pages) due.

Ses #24-25: Project presentations (20 minutes each).

Suggested Topics

Visualization of Networks

From Wikipedia: "Visual representation of [networks, including social networks] is important to understand the network data and convey the result of the analysis. … Exploration of the data is done through displaying nodes and ties in various layouts, and attributing colors, size and other advanced properties to nodes." This project would survey different techniques for visualizing networks and report on the pros and cons of the differing approaches.

A New Approximation Algorithm for Maximum Flows in Undirected Networks

On October 13^th, 2010, Christiano et al. completed a research paper that gives a fast approximation algorithm for maximum s-t flows on an undirected graph. It uses as a subroutine an algorithm for computing an electrical flow in an electrical network with differing voltages at nodes s and t and with differing resistances on arcs. It is an interesting issue to see how well this algorithm performs in practice. The project would be to test the algorithm on data sets. The algorithm should not be difficult to implement, assuming that one has available as a subroutine the algorithm that computes electrical flows.

Christiano, Paul, Jonathan A. Kelner, Aleksander Madry, Daniel Spielman and Shang-Hua Teng. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs. Unpublished manuscript, October 19, 2010. (PDF)

Topics in Social Networks

The theory of social networks has attracted a lot of attention in recent years, as well as a lot of research publications. This project would primarily consist of reviewing the literature on a subtopic in social networks, such as one of the following:

• analysis of the spreading of rumors or the spreading of diseases
• the small world phenomenon
• visualization (see the topic on visualization above)

Report Appendices

Please include additional appendices for the project report. The first is an appendix for the group. Include a description of up to 4 references that your team relied on. If you relied heavily on a book, then each chapter can be viewed as a different reference. The write-up should be between 1 and 1.5 pages and should be a brief summary of the content of the references.

The second should be a separate appendix for each member of the group, with a limit of 1/2 page per question per person. Each person on the team should address the following two questions:

1. What was the most interesting, surprising or useful thing that you learned while carrying out this project?
2. Answer either (a) or (b):
   1. What are you really glad you knew prior to starting the project?
   2. What do you wish you had known before starting this project?