Materials to get started:

Syllabus
What the rules are
Calendar
When everything happens
Project description
About class project
Textbook link
David Easley, Jon Kleinberg, Networks, Crowds, and Markets: reasoning about highly connected world, Cambridge Univ. Press, 2010

Office hours:

Rajiv
9-10:30 @ 107 on Monday
Liza
9:15-10:45 @ 123 Tuesday
Jackie
3-4:30 @ 107 Wednesday
Shambhavi
4-5:30 @ 003 Thursday
Aaradhya
9:30-11:00 @ 122 Friday
We will also use Canvas website (a) to access Gradescope and Ed discussion, (b) for course announcements (make sure you are subscribed, the first announcement will be sent before the first class), (c) for posting all the assignments and class notes.

Course description:

This course showcases how networks are widespread in society, technology, and nature, via a mix of theory and applications. It demonstrates the importance of understanding network effects when making decisions in an increasingly connected world. Topics include an introduction to graph theory, game theory, social networks, information networks, strategic interactions on networks, network models, network dynamics, information diffusion, and more. General topics include
-
Graph theory: graph partioning, strong and weak ties and triadic closure, homophily and spatial models
-
Game theory: dominant strategies, equilibria, optimality
-
Applications: modeling traffic and auctions, markets in networks, internet and information networks
-
Network dynamics: population models
-
Network dynamics: structural models

Topics and materials:

Textbook and other references are not substitutions for your class notes!

09/06
Introduction (diversity of networks) and first definitions [EK:Ch 1-2]
09/08
Six degrees of separation & the power of weak ties [EK:Ch 2-3]
09/13
Centrality (degree, distance-based, betweenness) and partitioning in networks [note (on betweenness), EK: 3.6]
09/15
Friendship paradox & balance in signed networks [note (on the friendship paradox), EK:Chapter 5]
09/20
Shelling segregation model & game theory, dominant and dominated strategies [EK: 4.5, 6.1-6.3, 6.10]
09/22
Game theory continued: Nash equilibrium [EK:6.4-6.6, 6.10]
09/27
Mixed strategies, existence of mixed NE, potential functions [EK:6.5-6.8,note 1 (on potential functions), note 2 (on computing mixed NE)]
09/29
Traffic networks: Braess paradox, optimal cost and cost at equilibrium [EK:8.1-8.3, 6.9 ]
10/04
One-sided matching markets and valuations [EK:Ch 10]
10/06
Matching market continued: existence of market-clearing prices [EK:Ch 10]
10/11
Stable matchings and Gale-Shapley algorithm [Karlin&Peres textbook(10.1-10.3), a nice presentation]
10/13
---------------------No class, midterm--------------------------
10/25
Structure of the Web and basics of ranking [EK:Ch 13,14]
10/27
4 algorithms for webpage ranking (degree-based, Hubs&Authorities, basic PageRank, Smoothed PageRank) [EK:Ch 14]
11/1
Intro to the dynamic on networks: information cascades [EK:Ch 16]
11/3
Diffusion of innovations: model description and the importance of dense clusters for (non-)cascading [EK:Ch 19]
11/8
Diffusion of innovations continued: global coordination, cascade capacity, bilingual stage of adoption [EK:Ch 19]
11/10
Dynamic on networks continued: epidemic modelling [EK:Ch 21]
11/15
Probabilistic (generative) network modelling: Watts-Strogatz small-world model [EK:Ch 20, 21.6]
11/17
Probabilistic network modelling: Erdos-Renyi, Barabasi-Albert (preferential attachment), Stochastic Block Model [EK:Ch 18 and lecture notes]

Supplementary notes:
-
On betweenness centrality
-
On the friendship paradox
-
On best response dynamic and potential functions
-
On computing pure and mixed Nash equilibria