Materials from Fall 2022 Networks class
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, Stochastic Block Model [EK:Ch 18 and notes]
- 11/29
- Comparing Erdos-Renyi, Barabasi-Albert and Watts-Strogatz models; configuration model [Barabasi:from Ch 3,4]
- 12/01
- Guest lecture by J. Klusowski
Supplementary notes:
- -
- On betweenness centrality
- -
- On the friendship paradox
- -
- On best response dynamic and potential functions
- -
- On computing pure and mixed Nash equilibria