ECON 2040/INFO 2040/CS 2850 (Fall 2021): Course Outline

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.

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.

Readings

• Chapters 1-3 and Chapter 5.

Optional further reading:

• Mark Granovetter. The strength of weak ties. American Journal of Sociology, 78:1360--1380, 1973.
  (This is Granovetter's original paper describing his work covered in Chapter 3 of the Networks book.)
• Johan Ugander, Brian Karrer, Lars Backstrom, and Cameron Marlow. The Anatomy of the Facebook Social Graph. arXiv, 2011.
• Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed Networks in Social Media. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 1361--1370, 2010.

(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.

Readings

• Chapters 6, 8, and 9. (We will cover Chapter 7 later in the semester.)

Optional further reading:

• Ignacio Palacios-Huerta. Professionals Play Minimax. Review of Economic Studies, 70(2003), pp. 395-415,
  (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.

Readings

• Chapters 10-12.

(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.

Readings

• Chapters 13-15.

(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.

Readings

• Chapter 7, Chapters 16-18, and Chapter 22.

(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.

Readings

• Chapters 19-21.

Optional further reading:

• Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. Four Degrees of Separation. Proceedings of the fourth ACM International Conference on Web Science (WebSci), 2012.
• Michael Suk-Young Chwe. Structure and Strategy in Collective Action. American Journal of Sociology 105(1999), pp. 127--156.

(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.

Readings

• Chapters 23-24.