Networks (Econ/Soc/CS/Info , Jon Kleinberg and Eva Tardos)

High School Dating

(Bearman, Moody, and Stovel, 2004)
(Image by Mark Newman)

Corporate E-Mail Communication

(Adamic and Adar, 2005)

Note: This is not the current semester's course Web page. For current course information, handouts, and homework assignments, please visit theĀ present semester's version of the course.


Economics 2040 / Sociology 2090 / Computer Science 2850 / Information Science 2040
Cornell University, Fall 2012

Mon-Wed-Fri 11:15-12:05 in Kennedy Hall 116

Jon Kleinberg and Eva Tardos

A course on how the social, technological, and natural worlds are connected, and how the study of networks sheds light on these connections. Topics include: how opinions, fads, and political movements spread through society; the robustness and fragility of food webs and financial markets; and the technology, economics, and politics of Web information and on-line communities.

The course is designed at the introductory undergraduate level with no formal prerequisites; it satisfies the Arts & Sciences Social and Behavioral Analysis (SBA) distribution and the Engineering Liberal Studies (SBA group) distribution.

See below for more information, including the outline of topics, the schedule of office hours, and the CMS site (which you can log into using this CMS link) and Piazza site.

Problem set 4 is posted here

Course Staff

Class Discussion on Piazza

We will be using Piazza as a discussion forum for the class. Feel free to post any questions you have about class. Only students and instructors in the class will be allowed to post to it, and students and instructors and TAs can all answer questions.  To get started, please add yourself to the class piazza page as a student using your email address.

Office hours till the final week (Nov 29 - Dec-6): in Upson 328B, except where noted

Nov 29, Thursday 1-2 Kemal and Suahard
Nov 29, Thursday 5-6 Constandino and James
Nov 29, Thursday 6-7 Taylor and Rad
Dec 3, Monday 12:15-1:15 Julie and Jaya
Dec 3, Monday 3-4 Jon Kleinberg in 5134 Upson
Dec 4, Tuesday 10-11 Jon Kleinberg in 4141 Upson
Dec 4, Tuesday 5-6 Nicole and Hedyeh
Dec 4, Tuesday 6-7 Matt and Max

Dec 5, Wednesday 3pm Review session with Professors Kleinberg and Tardos, Kennedy Hall 116

Dec 5, Wednesday 5:30-6:30 Aleks
Dec 6, Thursday 1-2 Kemal and Suahard
Dec 6, Thursday 5-6 Constandino and James
Dec 6, Thursday 6-7 Taylor and Rad

Class Blog

There will be a class weblog that we will be maintaining as part of the course, and posting to the blog will be part of the graded coursework, as described in the accompanying.handout You may also want to look at Blog posts from previous years. Information about the mechanics of posting will be found in the.opening blog post

CMS Site

At the CMS site, you can log in with your Cornell NetID to find information about your course grades and also to upload solutions to homework.

All handouts will be available at the CMS site, and ssolutions to all problem sets, as well as the final paper, must be submitted through the CMS site in pdf format, by the start of class on the days they are due. This means that you should write these up in an electronic format (such as using Word) then convert it to PDFto be uploaded to CMS. Also, you should check the CMS site at the start of the semester to make sure that you are able to log in. Please let us know if you experience any difficulties with this.


Outline of Topics

(1) Graph Theory and Social Networks

The course begins with a discussion of some of the general properties of networks. It develops this through examples from social network analysis, including the famous ``strength of weak ties'' hypothesis in sociology, and it connects these themes to recent large-scale empirical studies of on-line social networks.


Optional further reading:

(This is Granovetter's original paper describing his work covered in Chapter 3.)

(2) Game Theory

Since most network studies require us to consider not only the structure of a network but also the behavior of the agents that inhabit it, a second important set of techniques comes from game theory. This too is introduced in the context of examples, including the design of auctions and some ``paradoxical'' phenomena surrounding network traffic congestion.


Optional further reading:

(This is the paper that studies penalty kicks in soccer, as discussed in Section 6.8.)

(3) Markets and Strategic Interaction on Networks

The interactions among participants in a market can naturally be viewed as a phenomenon taking place in a network, and in fact network models provide valuable insights into how an individual's position in the network structure can translate into economic outcomes. This provides a natural illustration of how graph theory and game theory can come together in the development of models for network behavior. Our discussion in this part of the course also builds on a large body of sociological work using human-subject experiments to study negotiation and power in networked settings.


(4) Information Networks and the World-Wide Web

The Internet and the Web of course are central to the argument that computing and information is becoming increasingly networked. Building on the earlier course topics, we describe why it is useful to model the Web as a network, discussing how search engines make use of link information for ranking, how they use ideas related to power and centrality in social networks, and how they have implemented network-based matching markets for sellling advertising.


(5) Network Dynamics: Population Models

Networks are powerful conduits for the flow of information, opinions, beliefs, innovations, and technologies. We begin by considering how these processes operate at the level of populations, when we can't necessarily observe the network itself, but only its effects on aggregate behavior. As part of this, we consider phenomena including information cascades, "tipping points" in the success of products with network effects, and the distribution of popularity.


(6) Network Dynamics: Structural Models

We continue our exploration of how things flow through networks, focusing on what we can learn from details of the network structure itself. Here we study how both behaviors and diseases can spread through a social network, and also some of the network phenomena that underpin the "six degrees of separation" effect.


Optional further reading:

(This is the paper that discusses the role of knowledge in facilitating collective action in social networks, as described in Section 19.6.)

(7) Institutions and Aggregate Behavior

Finally, a perspective based on networks can provide novel insights into the structure of social institutions, and into basic policy questions in many areas. We illustrate this theme with examples based on markets, voting theory, and property rights.



Almost no knowledge of specific mathematical content is assumed, other than some basic probability (random variables, expectation, independence, and conditional probability), which we will briefly review when it first arises.

However, the main goal of the course will be to build mathematical models of the processes that take place in networks. As such, students will be expected to interpret and work with mathematical models as they come up the course; at the same time, students should also think about how to relate these models to phenomena at a qualitative level.


Grades on homework, the paper, blog posts, the midterm, and the final will be weighted as follows:

Academic Integrity

You are expected to maintain the utmost level of academic integrity in the course. Any violation of the code of academic integrity will be penalized severely.

You are allowed to collaborate on the homework to the extent of formulating ideas as a group. However, you must write up the solutions to each problem set completely on your own, and understand what you are writing. You must also list the names of everyone that you discussed the problem set with.

Collaboration is not allowed on the other parts of the coursework.

Finally, plagiarism deserves special mention here. Including text from other sources in written assignments without quoting it and providing a proper citation constitutes plagiarism, and it is a serious form of academic misconduct. This includes cases in which no full sentence has been copied from the original source, but large amounts of text have been closely paraphrased without proper attribution. To get a better sense for what is allowed, it is highly recommended that you consult the guidelines maintained by Cornell on this topic. It is also worth noting that search engines have made plagiarism much easier to detect. This is a very serious issue; instances of plagiarism will very likely result in failing the course.