Course Description
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”.
Instructors
Professor: Johan Ugander (jugander)
TAs: Cole Crichton (colehc), Roberto Lobato Lopez (rlobato), Sophia Love (sophialove), Nirali Parekh (nirali25)
Schedule
Lectures: Tuesdays & Thursdays @ 9:00 AM – 10:20 AM, Bldg 420 Room 041
Office Hours:
- Monday 7p-9p, Cole, Spilker 317
- Tues 1p-3p, Nirali, Spilker 218
- Weds 11p-1p, Roberto, Main Quad 200-030
- Weds 4p-6p, Sophia, Main Quad 200-305
- Prof. Ugander: Thurs 10:30a-noon PT (MS&E135 and advising), Huang 357
Important Links
Lecture schedule
- All chapters reference Easley & Kleinberg (PDF)
- Slides are posted to Canvas by the start of lectures
Week | Topic | Reading | Assignments | |
---|---|---|---|---|
Week 1 | Tu | Course overview; Introduction to graph theory | Ch 1, 2.1-2.3 | Visit Canvas |
Th | Strong and weak ties | Ch 3.1-3.3 | PS1 Out | |
Week 2 | Tu | Homophily, Affiliation; Friendship paradox | Ch 4.1-4.3 | |
Th | Structural balance | Ch 5.1-5.4 | PS1 Due; PS2 Out | |
Week 3 | Tu | Game theory | Ch 6.1-6.9 | |
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 | |
Th | Bargaining & power | Ch 12.1-12.3, 12.5-12.8 | PS2 Due; PS3 Out | |
Week 5 | Tu | The web as a network | Ch 13.1-13.5 | |
Th | Link analysis | Ch 14.1-14.3 | ||
Week 6 | Tu | Web search | Ch 14.4-14.5 | |
Th | Sponsored search as a market | Ch 15.1-15.5 | PS3 Due; PS4 Out | |
Week 7 | Tu | Information cascades | Ch 16.1-16.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 | |
Th | Small worlds | Ch 20.1-20.6 | PS4 Due; PS5 Out | |
Week 9 | Tu | Guest lecture (Dr. Kirsten Altenburger) | ||
Th | Epidemics | Ch 21.1-21.4, 21.6 | ||
Week 10 | Tu | Course review | PS5 Due | |
Th | Practice exam | |||
Final | Weds | March 20, 8:30-11:30 |
Problem Sets
Problem sets are posted on Canvas and submitted via Gradescope. Solutions will be posted to Canvas soon after the submission deadline. See the syllabus details (below) for detailed information about submission, grading, late, and collaboration policy.
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.
Format: Each post should be centered around an recent 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.
One of the purposes of these writing assignments is to practice communicating your thoughts in a public forum (albeit anonymously, see the privacy discussion below). 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).
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. Finally, adding inappropriate, rude, or disruptive content to the blog will result in a 0 for this part of the course grade, and (depending on the nature of the content) potentially stronger actions. Plagiarism is also not acceptable; the Honor Code applies.
Grading: Posts will be graded on a 10 point scale based on their relevance to the class, novelty, and quality of the insights and writing. For blog posts (and blog posts only; the following policy does not apply to problem sets) late submissions (after Friday 11:59pm of the assigned week) will have 2 points deducted. Late submissions after Friday of Week 10 will not be considered and therefore given a 0/10 grade. Some posts will be mentioned and discussed in lectures. You are encouraged but not required to read the posts by your classmates.
Account creation and privacy: No student will be required to make their identity public as part of these assignments. During the first week each student will be randomly assigned to an ID number between 100 and 499. You will be emailed instructions for how to log in to your account. If you have any problems with your blog account, please email Monte.
The course staff will keep a private record of the user names and the corresponding real names for purposes of grading. Nothing prevents you from including your real names in the text of a post, if you choose to do so, but please do not mention other students by name as a blanket policy. You are free to mention the instructor or TAs (e.g.: “Professor Ugander mentioned that…”).
If you join the class late, please email Monte to obtain an account ID.
Scheduling: To space out the post traffic, students are assigned “deadline weeks” at random, based on the ID number they are assigned for the class. You are responsible for submitting a blog post before Friday 11:59pm of the weeks you are assigned. If your number is 127, your ID falls in the range 100-199 and your deadlines are week 2 and week 6. You may of course submit your blog posts before the week they are due.
ID range | Deadline Weeks |
---|---|
100-199 | Fridays Week 2, 6 |
200-299 | Fidaays Week 3, 7 |
300-399 | Fridays Week 4, 8 |
400-499 | Fridays Week 5, 9 |
Inspiration: Feel free to browse posts from previous years for inspiration, though the central stories for your commentaries should not come from this blog or any other similar course blog.
Syllabus Details
Learning goals:
- 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.
Prerequisites: Almost no prior mathematical knowledge is assumed other than some basic probability (random variables, expectation, independence), which we will briefly review when it first arises. There are no programming assignments in this course. The course focuses on building intuitions. Many of the concepts covered in the course are given a more formal treatment in higher-level classes at Stanford. I will try to connect to those classes when applicable.
Material:
- Easley and Kleinberg, Networks, Crowds, and Markets, Cambridge University Press, 2010
The complete textbook is available online as a free PDF, but can also be ordered as a reasonably priced hardcover.
Problem Set Rules All problem sets are to be submitted during the corresponding lecture day. Submissions will be made online, through Gradescope, as linked to from Canvas.
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. In particular, this means that your solution should not word-for-word resemble another student’s. In short, students are expected to abide by Stanford’s honor code.
Late Policy: No late assignments will be accepted.
Grading: The lowest problem set grade will be dropped, and the remaining problem sets will recieve 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.
Extreme circumstances: please email me, I am a reasonable human being.
Final exam The exam will be a 3 hour in-person exam given Wednesday, March 20, 8:30-11:30 am PT.
Evaluation
- Problem sets (50%)
- Blog posts (10%)
- Collegiality (5%)
- Final (35%)
Honor code violations In the event that a student is found to have violated the honor code (including through Early Resolution), the penality may include a full denial of credit for the course (not just the assignment). See the Student Conduct Penalty Code, Section J.
Students with Documented Disabilities 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). Professional staff will evaluate the request with required documentation, recommend reasonable accommodations, and prepare an Accommodation Letter for faculty dated in the current quarter in which the request is made. Students should contact the OAE as soon as possible since timely notice is needed to coordinate accommodations. For more information: http://studentaffairs.stanford.edu/oae