Syllabus

Course Number: CS 134

Time and Location: Mondays and Wednesdays, 2:30–4:00 pm @ Science Center C

Instructor: Professor Yaron Singer  ( yaron@seas.harvard.edu )

Teaching Fellows

  • Jason Goodman (jgoodman “at” college.harvard.edu)
  • Raynor Kuang (raynorkuang “at” college.harvard.edu)
  • Graham Lustiber (grahamlustiber “at” college.harvard.edu)
  • Emily Wang (emilyluwang “at” college.harvard.edu)
  • Alex Wang (alexwang “at” college.harvard.edu)
  • Jimmy Jiang (jiang01 “at” college.harvard.edu)
  • Ben Zheng (benjaminzheng”at”college.harvard.edu)
  • Larry Zhang (larryzhang  “at” college.harvard.edu)

A full list of staff contact details and office hours can be found at the Resources page.

Course Description

Networks—of social relationships, economic interdependencies, and digital interactions—are critical in shaping our lives. This course introduces models and algorithms that help us understand networks. Fundamental concepts from applied mathematics, microeconomics, and computer science will be presented through the lens of network science, in order to equip students to usefully analyze the “big data” generated by online networks. Applications discussed include the viral spread of ideas, maximizing influence, and the contagion of economic downturns. Concepts and tools covered include game theory, graph theory, data mining, and machine learning.

Requirements Fulfilled/Credit

This course counts for concentration credit in Applied Math and as an upper-level elective in Computer Science. For Economics concentrators, it counts as one of the three electives required. This course offers an optional writing requirement which, if completed, will satisfy the Economics concentration writing requirement. For Statistics concentrators, it counts as a related fields course.

Learning Objectives

At a high level, our goal is to help students with modeling and analyzing complex phenomena in the real world.  Throughout the course we will use tools from applied math, economics, theoretical computer science, and machine learning to analyze networks.

Students who successfully complete the course will be able to communicate and collaborate productively with network scientists, as researchers, members of teams in industry, and as policymakers.

In more detail, students will walk away with three sorts of things, which are detailed on the Learning Objectives page.

  • Vocabulary, central concepts, and basic facts about networks from mathematics, computer science, economics, and sociology.
  • Between five and ten great ideas of networks that can be told in a short story: the friendship paradox, network centrality, why social networks feel small and are easy to navigate.
  • An ability to write simple and powerful models and algorithms to estimate how far a viral marketing campaign is likely to go, or how much bias there will be in a social survey.
Prerequisites

To enjoy and succeed in this course, you will need to be comfortable with some basic math and programming, as well as with some essential ideas from economics. We will make available self-quizzes to help you gauge where you stand.

  • Math: calculus at the level of Math 1. Basic probability at the level of a good high school class (definitions and basic properties of distributions, expectation, variance).
  • Programming: CS50 taken previously or concurrently, or you should have equivalent programming ability. Programming assignments will be part of the homework, and you will be expected to get help on basic coding outside the class if you need it.
  • Economics: optimal choice in the presence of randomness; notion of a utility function; definition and basic use of expected utility.
Textbooks

David Easley and Jon Kleinberg, Networks, Crowds and Markets. Cambridge University Press, 2010. There is a full-text version available online.
Matthew O. Jackson Social and Economic Networks. Princeton University Press, 2008.

Grading

The grading for the course consists of three differently-weighted pieces:

  • 5% class participation;
  • 45% weekly problem sets (sometimes replaced with writing assignments): out Wednesday, due the next Wednesday at noon, no late submissions accepted. Lowest two scores dropped. This component includes the writing assignment;
  • 20% first midterm (February 15);
  • 30% second midterm (April 26).
Course Outline
  • Preliminaries
  • Small world networks
  • Structure of networks
  • The friendship paradox
  • Strategic interactions
  • Influence in networks
  • Diffusion of information
  • Ranking webpages
  • Clustering
  • Networked markets
Collaboration and Academic Integrity
  • Students are encouraged to discuss the problem sets with each other.
  • Each student must indicate on his or her solution the names of all students with whom he or she worked on the problems.
  • Each student’s homework solutions must reflect his or her own understanding of the problem and not be copied in substance (i.e., with or without changes of phrasing).
  • On all written assignments, Harvard’s standard guidelines regarding plagiarism apply. They are relevant to the problem sets and especially the extended writing assignment. The highlights:
    • You may not submit the same work to two different courses without permission.
    • If you use something, cite it.
    • Beware of the extended paraphrase, which is the easiest kind of plagiarism to commit accidentally. If you are reasonably close to quoting something, it’s better to just quote it exactly. (A block quote is a convenient typographical device for this.) You are committing plagiarism if you take a passage and copy it out, changing the phrasing and some of the order but keeping much of the substance and flow of ideas. The guidelines have good examples. If you must paraphrase, explicitly say (for example, in a footnote) that you are writing a close paraphrase of someone else’s passage, and say where the paraphrase begins and ends. A standard parenthetical citation will not suffice.
Accommodations for Students with Disabilities

Students needing academic adjustments or accommodations because of a documented disability must contact Prof. Singer by the end of the second week of the term, and present their Faculty Letter from the Accessible Education Office (AEO). Failure to do so may result in the Course Head’s inability to respond in a timely manner. All discussions will remain confidential.