MS&E 135: Networks

Aut 2024-25

Tu, Th 9:00-10:20am
Hewlett Teaching Center 201

INSTRUCTOR
Ashish Goel
ashishg@stanford.edu, 650 814 1478
Office Hours: Wed 5-6 pm in person (Y2E2 335), Wed 6-6:30 pm on Zoom.

TEACHING ASSISTANTS
Zhihao Jiang
faebdc@stanford.edu
Office Hours: Thu, 4-5pm, HEC 203.

Max Atsunobu Vandervelden
mvdvldn@stanford.edu
Office Hours: M 11-12am on on Zoom.

Betty Wu
bettyyw@stanford.edu
Office Hours: Tue, 4-5pm, HEC 203.

IMPORTANT NOTES

We will not have Office hours in the first week of class.
Unless an email is confidential for the instructor, or has very specific request for one person, please send it to msande135-win2425-staff@lists.stanford.edu so we can track internally. Emails sent to only one person sometimes get lost.
Class forum: We will use Ed Stem as a discussion forum, and Gradescope for assignments. Sign up links available here. We will use Canvas for posting handouts.
Auditors: please sign on to the mailman list msande135-win2425-guests and let the class staff know.
Attendance is mandatory (in that the class is not recorded, and anything covered in class is part of the curriculum), but we will not track it. However, a TA will approximately track your in-class participation.
Students who may need an academic accommodation based on the impact of a disability must initiate the request with the Office of Accessible Education (OAE).

DESCRIPTION and PRE-REQS
This course provides an introduction to how networks underly our social, technological, and natural worlds, with an emphasis on developing intuitions for broadly applicable concepts in network analysis. The course will include: an introduction to graph theory and graph concepts; social networks; information networks; the aggregate behavior of markets and crowds; network dynamics; information diffusion; the implications of popular concepts such as “six degrees of separation”, the “friendship paradox”, and the “wisdom of crowds”. No advanced mathematical knowledge is assumed. We will use some basic probability (random variables, expectation, independence), and will briefly review these when they are first introduced.

PHILOSOPHY AND LEARNING GOALS
The class aims to provide an Engineering perspective on networked systems, specially those that are socio-economic in nature (e.g. we will not discuss how the Internet routing protocols work). We will take “A first course” approach and focus on intuition. There will be no coding (except for demo purposes or generated by AI agents).

The learning goals are:

Understand basic graph theory and network analysis
Understand basic game theory and strategic behavior
Develop a quantitative and qualitative intuition for the role of networks in social and technological systems.

BLOG POSTS

DETAILED PLAN
All chapters below refer to the text by Easley and Kleinberg: Networks, Crowds, and Markets, Cambridge University Press, 2010. The text is available online for free and also available as a reasonably priced hard-cover.

Week	Day	Topic	Reading	Assignments
Week 1	Tu	Course overview; Introduction to graph theory	Ch 1, 2.1-2.3	Visit Canvas
Week 1	Th	Strong and weak ties	Ch 3.1-3.3	PS0 and PS1 handed Out
Week 2	Tu	Homophily, Affiliation; Friendship paradox	Ch 4.1-4.3
Week 2	Th	Structural balance	Ch 5.1-5.4	PS0 and PS1 due the next day at 5pm; Sign-ups due for the blog post; PS2 Out
Week 3	Tu	Game theory	Ch 6.1-6.9
Week 3	Th	Congestion, Auctions	Ch 8.1-8.2, 9.1-9.2
Week 4	Tu	Matching markets	Ch 9.3-9.6, 10.1-10.4
Week 4	Th	Bargaining & power	Ch 12.1-12.3, 12.5-12.8	PS2 due the next day at 5pm; PS3 Out
Week 5	Tu	The web as a network	Ch 13.1-13.5
Week 5	Th	Link analysis	Ch 14.1-14.3
Week 6	Tu	Web search	Ch 14.4-14.5
Week 6	Th	Sponsored search as a market	Ch 15.1-15.5	PS3 due the next day at 5pm; PS4 Out
Week 7	Tu	Information cascades	Ch 16.1-16.7
Week 7	Th	Network effects, cascading behavior	Ch 17.1-17.3, 19.1-19.4
Week 8	Tu	Rich-get-richer	Ch 18.1-18.6
Week 8	Th	Small worlds	Ch 20.1-20.6	PS4 due the next day at 5pm; PS5 Out
Week 9	Tu	Guest lecture
Week 9	Th	Epidemics	Ch 21.1-21.4, 21.6
Week 10	Tu	Finish any material that did not get covered; special topics		PS5 due the next day at 5pm
Week 10	Th	Course review
Final	Weds	March 19, 9:00-11:30

Slides will be posted on canvas or emailed by the start of lectures.

REQUIREMENTS

There will be 5 regular Problem Sets (50% of class grade), and one extra ungraded Problem Set (PS0) that will be a check-list confirming that you have done the basic things for the class: downloaded the text, read the syllabus, read the blog-post rules, signed up for the blog-post, read the primer, etc.
There will a final exam (35%)
You will have to write two blog posts (details below, 10%)
Class participation (asking and answering questions in class and on the forum; blog participation; collegiality)
Problem Set Rules:
1. All problem sets are to be submitted by 5pm on the due date. Submissions will be made online, through Gradescope.
2. Collaboration policy: You may discuss the problem sets with other students in the class, but since the goal is to practice skills, the actual writing up of the solutions must be done separately. You can use AI agents to polish your writing, and for hints on how to solve the problem, but the first draft of the problem must be written by you.
3. Late Policy: No late assignments will be accepted.
4. Grading: The lowest problem set grade will be dropped, and the remaining problem sets will receive equal weight. Effectively the last two bullets mean that if you are unable to submit one problem set by the deadline, you will be “dropping” that problem set and graded on the remaining 4 problem sets. It’s not advisable to miss more than one deadline.
5. Exceptional circumstances: For medical/family emergencies, feel free to write to the course staff and we will try to accommodate if feasible.

WRITING BLOG POSTS
All students will be required to write two short blog posts during the quarter, posted to a course blog and taking the form of a miniature reaction paper and taking the form of a miniature reaction paper.

FORMAT: Each post should be centered around a recent (last 10 weeks) news article, academic paper, online essay, new company or organization, and contain at least one web link on that subject. The goal is to provide commentary that gives context around the subject, targeted at your peers in the course (or similarly informed outsiders). Why do you think it interesting or relevant? The post should be at least two paragraphs, at least 300 words, and have at least one illustration. It should also be connected to the class material.

TIMING: There will be a sign up sheet. You can sign up for any two weeks from week 3 to week 9, with at least one post during weeks 3-6. Posts are due by Tue of the week you signed up for.

AI AGENTS: Feel free to use AI agents to polish your language but not to come up with the original thesis or the first draft. Please retain a transcript of your AI agent session and your first draft.

PRIVACY: You can use a pseudonym or your real name — your call. You can refer to the class staff by name, but not your fellow students. Posts will be publicly accessible. Your pseudonym will only be for the outside world — the class staff and other students will know what pseudonym you are using.

TONE AND LANGUAGE: Keep your tone measured, professional, and polite. If you are expressing a strong opinion, it should come out in the substance of your argument, not in the vehemence of the language. You should keep in mind, as you write your posts, that if you refer to a company, organization, or research project in the outside world, the people you’re talking about may well end up reading what you write. Keep your comments on other posts civil and substantive.

EXAMPLE TOPICS: Has polarization gone down or increased from the 2020 elections to the 2024 elections in the US? Are high school kids segregating into Discord and Instagram by gender? How does Meta plan to use Community Notes?

ENGAGEMENT: Your audience is each other, not just the course staff. Engage each other! Posts that dialogue with earlier posts from the course are encouraged, though should add significantly to the previous points made (in part by referencing a new news article/paper/essay).