| 1 |
Course specifics, motivation, and intro to graph theory - Course specifics: times, office hours, homework, exams, bibliography, etc.
- General motivation: What are networks? What is network science? Impacts, ubiquity, historical background, examples.
- Course description and contents: A quick overview of the things that we are going to learn.
- Basic graph theory: vertices, edges, directed graphs, simple graphs, weighted graphs, neighborhoods, degree, path, cycle.
| |
| 2 |
Introduction to graph theory - More on graph theory: Connectivity, components, giant components, distance, small-world phenomenon, adjacency and incidence matrices.
| |
| 3 |
Strong and weak ties, triadic closure, and homophily Homework 1 distributed
| |
| 4 |
Centrality measures - Detection and identication of important agents.
- Degree, closeness, betweenness, eigenvector, and Katz centrality.
| |
| 5 |
Centrality and web search, spectral graph theory - Page rank and web search.
- Eigenvalues and eigenvectors of graph matrices and their properties.
- Quadratic forms on graphs and Laplacian.
| |
| 6–7 |
Spectral graph theory, spectral clustering, and community detection - Properties of graph Laplacian.
- Derive spectral clustering formulation as a relaxation of modularity maximization.
- Community detection using ratio cut criterion.
Homework 2 distributed during Lecture 6
| Homework 1 due by Lecture 6 |
| 8–10 |
Network models - Graphs as realizations of stochastic processes: Introduce the general idea.
- Friendship paradox.
- Erdős-Rényi graphs, branching processes. Denition, examples, phase transition, connectivity, diameter, and giant component.
Homework 3 distributed during Lecture 10
| Homework 2 due by Lecture 9 |
| 11 |
Configuration model and small-world graphs - Conguration model, emergence of the giant component.
- Small-world graphs: Denition from rewiring a regular graph, balance between clustering coefficient and network diameter.
| |
| 12 |
Growing networks - Growing networks.
- Preferential attachment and power laws: the rich get richer effect. Degree distribution observed in real life, example of a dynamic generative process leading to this distribution, mean field analysis.
| Homework 3 due |
|
Midterm exam Homework 4 distributed
|
| 13–14 |
Linear dynamical systems - Convergence to equilibrium.
- Stability, eigenvalue decomposition, Lyapunov functions.
Homework 5 distributed during Lecture 14
| Homework 4 due by Lecture 14 |
| 15 |
Markov chains - Perron-Frobenius theorem.
- Random walk on graphs.
| |
| 16–17 |
Information spread and distributed computation - Conductance and information spread.
- Distributed computation.
- Markov chain convergence and Cheeger's inequality.
Homework 6 distributed during Lecture 17
| Homework 5 due by Lecture 16 |
| 18–19 |
Learning and herding - Simple Herding Experience.
- Aggregate Beliefs and the "Wisdom of Crowds."
- The DeGroot Model: The seminal network interaction model of information transmission, opinion formation, and consensus formation.
| |
| 20 |
Epidemics - Models of diffusion without network structure: Bass model
-
Models of diffusion with network structure
- The SIR Epidemic Model
- The SIS Epidemic Model
| Homework 6 due |
| 21 |
Introduction to game theory I - Game theory motivation: Decision-making with many agents, utility maximization.
- Basic ingredients of a game: Strategic or normal form games.
- Strategies: Finite / Infinite strategy spaces.
- Best responses, dominant, and dominated strategies.
- Iterated elimination of dominated strategies and dominant solvable games.
- Nash equilibrium.
Homework 7 distributed
| Part I descriptive write-up of final project (non-default version) due |
| 22 |
Introduction to game theory II - Nash equilibrium: more examples.
- Multiplicity of equilibria.
- Pareto-Optimality and social optimality: Price of anarchy.
- Nonexistence of pure strategy Nash equilibria with a touch of mixed strategies.
- Fixed point theorems and existence of Nash equilibrium in infinite games.
| Get familiar with the data and hand in your results for Part I of the final project (default version) |
| 23 |
Application of game theory to networks - Traffic equilibrium: non-atomic traffic models.
- Braess's Paradox.
- Socially-Optimal routing and inefficiency of equilibrium.
Homework 8 distributed
| Homework 7 due |
| 24 | Course review and discussion | |
| 25 | Project presentations |
Homework 8 due Final project report due one week after final class
|
