Networks: Structure & Economics

The course meets TR 10:30-12 in Annenberg 105. **The first lecture will be on Jan 7, 2020. **

The course will be managed using Piazza. All communication will happen and all materials will be posted through https://piazza.com/caltech/winter2020/cseecms144. Email Adam if you have problems enrolling yourself at the site.

Social networks, the web, and the internet are essential parts of our lives and we all depend on them every day, but do you really know what makes them work? This course studies the "big" ideas behind our networked lives. Things like, what do networks actually look like (and why do they all look seemingly look so similar)? How do search engines work? Why do memes spread the way they do? How does computational advertising work? For all these questions and more, the course will provide a mixture of both mathematical analysis and hands-on projects.

This course can be combined with a second networks course (CS 142 or CS/EE 143) and a networking project course (CS/EE 141,145, or 147) in order to satisfy the project requirement for CS undergraduate degree, but CS/EE 142 and CS 143 are not required prerequisites. The course assumes students are comfortable with graph theory, probability, and basic programming.

Adam Wierman, adamw@caltech.edu

Networks, Crowds, and Markets: Reasoning About a Highly Connected World,

by David Easley and Jon Kleinberg.

This book is quite reasonably priced, but there is also a pre-publication pdf available here. I think the book is excellent, so I highly recommend you buy a copy and read it cover-to-cover. We will not be going through it in order, but I will point to the relevant parts of the book for each lecture. Additionally, I will post course notes and supplementary papers on this site at the end of each class.

This is only a tentative outline of the topics we will discuss and will likely change as the term goes by. But, I put it up to give you an idea of where we're going. The course is basically organized as a collection of topics that I think are important and interesting and which provide a modern perspective on our networked lives.

**Introduction to the class**

- What is this course about?
- Bonus lecture: A probability refresher

**Part I: Understanding Network structure**

- The web graph & beyond -- universal properties of networks
- Why do we see a giant component?
- Are heavy-tails actually "normal"?
- Why is it a small world (after all)?

**Part II. The impact of network structure**

- How search works
- Data centers: What's in them and how to program them
- Cascading behavior in networks
- Communities & clusters: Can you hear the shape of a network?

**Part III. Network economics**

- Bonus lecture: An introduction to game theory
- Load Balancing & Routing games
- Computational advertising
- Strategic network formation

**Course Summary**

- Course wrapup

Homeworks will be assigned every 1-2 weeks. Many of the problems will be challenging, so please start immediately and please come to office hours to discuss the problems! The assignments will represent a mixture of theory (proofs) and practice (coding). I assume that you can code and use Matlab/Mathematica and Python.

- Homework 1: Warming up
- Homework 2: Starting with a crawl
- Homework 3: Heavy tails & small worlds
- Homework 4: PageRank & MapReduce
- Miniproject 1: Rankmaniac
- Homework 5: Game theory warmup
- Minproject 2: Pandemaniac
- Homework 6: Load balancing & routing games