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

Corporate E-Mail Communication (Adamic and Adar, 2005; image by the authors)

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 also the poster announcing the course.)

This is the third time the course is being offered; see the home pages for the Spring 2007 and Spring 2008 versions of the course to get more detailed coverage of course content, course material, and a link to the class blog with posts by students from last year.

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.

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

(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 and Cascading Behavior

Networks are powerful conduits for the flow of information, opinions, beliefs, innovations, and technologies. We discuss how models of interaction can give us ways of reasoning about processes that cascade through networks, as well as related problems such as the distribution of popularity, rich-get-richer phenomena, and the ``six degrees of separation''. Here too, we connect the models to recent empirical studies.

(6) Policy Considerations

Finally, a perspective based on networks can provide novel insights into basic policy questions in many areas. We illustrate this theme with examples based on voting theory, statistical discrimination, and intellectual property.