NETS 112: Networked Life

What science underlies Facebook, Netflix, Twitter, Intrade, and Google? What are the economics of email spam? Why do some social networking services take off, and others die? What do game theory and the Paris subway have to do with Internet routing? How does Google find what you're looking for... and exactly how do they make money doing so? What structural properties might we expect any social network to have? How might a social network influence election outcomes? What problems can be solved by crowdsourcing? How does your position in a social network (dis)advantage you?

NETS 112 looks at how our world is connected –socially, strategically and technologically– and why it matters. The answers to the questions above are related. They have been the subject of a fascinating intersection of disciplines, including computer science, physics, psychology, sociology, mathematics, economics and finance. Researchers from these areas all strive to quantify and explain the growing complexity and connectivity of the world around us, and they have begun to develop a rich new science along the way.

What Will You Learn about?

Networked Life will explore recent scientific efforts to explain social, economic and technological structures -- and the way these structures interact -- on many different scales, from the behavior of individuals or small groups to that of complex networks such as the Internet and the global economy.
This course covers computer science topics and other material that is mathematical, but all material will be presented in a way that is accessible to an educated audience with or without a strong technical background. The course is open to all majors and all levels, and is taught accordingly. There will be ample opportunities for those of a quantitative bent to dig deeper into the topics we examine. The majority of the course is grounded in scientific and mathematical findings of the past two decades or less (often much less).

Offered: 
Fall

NETS 150: Market and Social Systems on the Internet

Want to understand the sociological and algorithmic aspects of friend recommendation? Want to know how Google decides what 10 answers to return, out of the 10 million matching results? Want to understand how search engines have revolutionized advertising? Then this is the course for you!

NETS 150 provides an overview of the issues, theoretical foundations, and existing techniques in networks (social, information, communication) and markets on the Internet. Subsequent NETS courses are available for students wishing to explore any of these topics in greater detail.

What Will You Learn about?

This course gives you an overview of the mathematical and engineering aspects of Market and Social Systems Engineering. We start with a brief overview of graph theory, which helps us abstract networks. Then we look at how sociology and algorithms interact to create online social networks, with a particular emphasis on preferences, recommendations, and connectivity. You'll get a good sense for how Facebook and Google+ do their recommendations.

We move on to information networks, where we look at the internals of a search engine like Google or Bing, and discuss how documents are ranked based on their internal properties and the structure of links on the Web. Then we talk about the notions of incentives in network-based interactions, which lead to notions like game theory, markets, auctions, and search keyword pricing (the main source of revenue at Google). Our fourth major topic is the construction of the Internet itself, including how messages are routed. We wrap up with a discussion of the issues in building global-scale systems and services on the Internet.

Offered: 
Spring

NETS 212: Scalable and Cloud Computing

How do Google, Facebook, and others handle millions of concurrent users across the world? How do Internet companies analyze the vast volumes of data they collect each day, to make recommendations? How are governmental and educational organizations, as well as large businesses like Netflix, architecting their Internet services to take advantage of “cloud computing” platforms offered by Amazon, Microsoft, and other providers? How does one build interactive applications like Gmail and Google Maps that only require a browser?

NETS 212 explains the motivations, pros and cons, and architecture of cloud computing. It also gives an understanding of data-centric or "big data" programming on cloud or cluster machines, using MapReduce, SQL, Pig Latin, and other languages -- and explains how to do algorithm design for these models. Finally we cover "software as a service" and building AJAX Web applications. You will get real "hands-on" time with cloud computing services (Amazon AWS or Microsoft Azure).

What Will You Learn about?

NETS 212 focuses on a variety of topics relating to data-centric and service-oriented computing. We discuss different types of cloud services; programming models and languages for exploiting thousands of machines to do data processing; AJAX-based “software-as-a-service” platforms such as Google Web Toolkit; and issues relating to security and privacy in the data-centric computing arena. Students do a variety of hands-on programming and design exercises and a project, running their applications on a commercial cloud provider.

Offered: 
Fall

NETS 312: Theory of Networks

Want to understand how memes spread across the Internet? How organisms exhibit flocking behavior? How the structure of a network can help predict behavior among the nodes?

This course is a rigorous study of the structure and function of complex networks. From World Wide Web to networks of banks and lenders that form the financial sector, to friendship networks that influence our opinion and everyday decision-making, networks have become an integral part of our daily lives.

What Will You Learn?

This course provides a mathematically rigorous introduction to the study of networks, their structure, function and formation.

  • Networks. History and motivation for studying networks and networked phenomena. Social networks, small worlds, social science experiments. Central questions in network science, basics of graph theory (Jackson chapter 1)
  • Graph theory definitions, adjacency matrix, walks and paths, Laplacian, adjacency and incidence matrix, connectivity
  • Perron Frobenius theory, Spectral properties , drawing graphs
  • Random graphs, Erdos Renyi model Spectral properties
  • Threshold phenomena, branching processes, connectivity in Erdos-Renyi models. Giant components; contagion and diffusion
  • Degree distributions, small world model
  • Growing random graphs with various degree distributions: power law distributions, preferential attachment, Chung Lu Model
  • Network topology identification: Are degree distributions enough?
  • Diffusion and contagion models
  • PageRank, Poisson equations, effective resistance and random walks
  • Gossip and flocking, Krause’s opinion dynamics model
  • Game theory and learning in games
  • Social learning and distributed parameter estimation in social networks
Offered: 
Spring

NETS 412: Algorithmic Game Theory.

How should an auction for scarce goods be structured if the sellers wish to maximize their revenue? How badly will traffic be snarled if drivers each selfishly try to minimize their commute time, compared to if a benevolent dictator directed traffic? How can couples be paired so that no two couples wish to swap partners in hindsight? How can you be as successful as the best horse-racing expert at betting on horse races, without knowing anything about horse racing?

In this course, we will take an algorithmic perspective on problems in game theory, to solve problems such as the ones listed above. Game theory has applications in a wide variety of settings in which multiple participants with different incentives are placed in the same environment, must interact, and each "player"'s actions affect the others.

What Will You Learn about?

The list of topics is as follows:

Part 1: Game Theory and Game Dynamics

  • Quick introduction to game theory: Zero sum and general sum games, repeated games, Minmax strategies, Nash equilibrium, correlated equilibrium
  • Game Dynamics: Sequential best response, weighted majority algorithm, fictitious play, perturbed follow the leader
  • Game Dynamics converging to Nash equilibrium in zero sum games; Game dynamics converging to correlated equilibrium in general sum games
  • Price of anarchy: Definition, routing games, hoteling games
  • Smooth games and "Price of Total Anarchy"

Part 2: Auctions and Mechanism Design

  • Auction basics: First price auctions, second price auctions, truthfulness
  • Maximizing welfare: The VCG Mechanism
  • Ad Auctions on Google/Yahoo/Bing
  • Maximizing revenue: Bayesian optimal auctions: How to set a reserve price
  • Maximizing revenue: Prior Free Mechanism Design
  • Online auctions for digital goods
  • Stable Marriages and the Deferred Acceptance Algorithm
Offered: 
Spring