1.022 - Introduction to Network Models​

This is an undergraduate-level interdisciplinary course. It provides an introduction to complex networks, their structure, and function, with examples from engineering, applied mathematics and social sciences. Topics include spectral graph theory, notions of centrality, random graph models, Markov chains and random walks, gossip algorithms and graph conductance, contagion phenomena, cascades and diffusion, opinion dynamics, and congestion and potential games on networks.

​    Our course will make use of the python programming language for both the homework and the course project. Python is an easy to learn, powerful programming language that is often used for Data Science applications and has a large ecosystem of libraries for machine learning, optimization, etc. We have provided some information and a list of useful resources as a starting point to work with python here.

Bibliography: The course textbook is "Networks, Crowds, and Markets: Reasoning about a Highly Connected World'' (1st ed.) by David Easley and Jon Kleinberg. Other recommended references are listed at the end of the syllabus.

Network data repositories: Here is a list of public repositories of network data that you can use to play around and to test the concepts learned throughout the course.
  • SNAP: Stanford Large Network Dataset Collection, is a great repository for large networks with graphs ranging from a few thousand nodes to several millions.
  • KONECT: contains several hundred network datasets of various types, including directed, undirected, bipartite, weighted, unweighted, signed and rating networks.
  • ICON: does not host network datasets, but provides an "Index of Complex networks" with links to the orginal datasets. You can search for various categories of networks (just like in KONECT).

Course syllabus: Below, you can find the detailed breakdown of the topics I covered in Fall 2018 offering of the course.

Lecture 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.
Readings: Ch. 1, 2.1 [Easley-Kleinberg]

Lecture 2: Intro to graph theory
  • More on graph theory: Connectivity, components, giant components, distance, small-world phenomenon, adjacency and incidence matrices.
Readings: Ch. 2.2, 2.3 [Easley-Kleinberg], Ch. 6.1-6.4, 6.7, 6.9 [Newman]

Lecture 3: Strong and weak ties, triadic closure, and homophily.
  • Strength of weak ties.
  • Triadic closure, homophily.
Readings: Ch. 3.1-3.3, 4.1 [Easley-Kleinberg]

Lecture 4: Centrality measures
  • Detection and identification of important agents.
  • Degree, closeness, betweenness, eigenvector, and Katz centrality.
Readings: Ch. 7.1-7.3, 7.6, 7.7 [Newman]

Lecture 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.
Readings: Ch. 14.1-14.3 [Easley-Kleinberg], Ch. 6.13 [Newman]

Lecture  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.
Readings: Ch. 16 [Spielman], Ch. 11.5 [Newman]
 
Lecture 8-10: Network models
  • Graphs as realizations of stochastic processes: Introduce the general idea.
  • Friendship paradox.
  • Erdos-Renyi graphs, branching processes. Definition, examples, phase transition, connectivity, diameter, and giant component.
Readings: Ch. 12.1-12.3, 12.5, 12.7, 12.8 [Newman]

Lecture 11: Configuration model, and Small-world graphs
  • Configuration model, emergence of the giant component.
  • Small-world graphs: Definition from rewiring a regular graph, balance between clustering coefficient and network diameter.
Readings: Ch. 4.1.4, 4.2.1, 4.2.6, [Jackson], Ch. 20.1-20.2 [Easley-Kleinberg], Ch. 15.1 [Newman]

Lecture 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.
Readings: Ch. 18 [Easley-Kleinberg], Ch. 14.2 [Newman]

Lecture 13-14: Linear dynamical systems
  • Convergence to equilibrium.
  • Stability, eigenvalue decomposition, Lyapunov functions.
Readings: Ch. 18.1, 18.2 [Newman], Lecture notes.

Lecture 15: Markov chains
  • Perron-Frobenius theorem.
  • Random walk on graphs.
Readings: Ch. 6.14 [Newman], Lecture notes.

Lecture 16-17: Information spread and distributed computation
  • Conductance and information spread.
  • Distributed computation.
  • Markov chain convergence and Cheeger's inequality.
Readings: Ch. 2.1, 2.2, 3.1, 3.2, 5.1, 5.2 [Shah]

Lecture 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.
Readings:  Ch. 16.1 and 16.2 [Easley-Kleinberg], Ch. 8.3 and 9.1 [Jackson]

Lecture 20: Epidemics
  • Models of diffusion without network structure: Bass model
  • Models of diffusion with network structure
    • SIR Epidemic Model.
    • SIS Epidemic Model.
Readings: Ch. 21 [Easley-Kleinberg], Ch. 7.1 and 7.2 [Jackson]

Lecture 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.
Readings:  Ch. 6.1-6.4, 6.10 (A&B) [Easley-Kleinberg].

Lecture 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.
Readings:  Ch. 6.5, 6.6, 6.9 [Easley-Kleinberg], Lecture notes.

Lecture 23: Application of Game Theory to Networks
  • Traffic equilibrium: non-atomic traffic models.
  • Braess's Paradox.
  • Socially-Optimal routing and inefficiency of equilibrium.
Readings:  Ch. 8.1-8.3 [Easley-Kleinberg], Lecture notes.

Lecture 24: Congestion games, course review and discussion.
  • Congestion games and atomic traffic equilibria.
  • Potential functions and potential games.
  • Nash equilibria in potential games.
  • Application of potential games to congestion games.
 Readings:  Ch. 8.1-8.3 [Easley-Kleinberg], Lecture notes.

Lecture 25: Project presentation

- Course material available on MIT OpenCourseWare. 
- See 1.022 final project (Fall 2020) on adaptive modeling and simulation of COVID-19 spread in python. 

​References  

6.252 - Nonlinear Optimization

This is a graduate-level interdisciplinary course with audience mostly from electrical engineering, operations research, and civil engineering departments, and introduces students to the fundamentals of nonlinear optimization theory and methods. Topics include unconstrained and constrained optimization, linear and quadratic programming, Lagrange and conic duality theory, interior-point algorithms and theory, Lagrangian relaxation, generalized programming, and semidefinite programming. Algorithmic methods used in the class include steepest descent, Newton's method, conditional gradient and subgradient optimization, interior-point methods and penalty and barrier methods.
 
Bibliography: The course textbook is "Nonlinear Programming'' (3rd ed.) by Dimitri P. Bertsekas. Other recommended references are listed at the end of the syllabus below.
 
Lecture 1: Introduction / Applications 
Lecture 2: Unconstrained Optimization and Optimality Conditions 
Lecture 3: Gradient Methods - Convergence
Lecture 4: Rate of convergence. Heavy ball method.  
Lecture 5: Newton's method and variants 
Lecture 6: Conjugate direction methods 
Lecture 7: Quasi-Newton methods, coordinate descent 
Lecture 8: Optimization over a convex set, projection
Lecture 9: Feasible directions and gradient projection
Lecture 10: Lagrange multipliers - KKT conditions 
Lecture 11: Sufficient conditions and sensitivity analysis. Inequalities. 
Lecture 12: Convex Analysis (convex sets, convex functions, etc)
Lecture 13: Convex duality, separation, applications 
Lecture 14: Penalty and multiplier methods
Lecture 15: Interior point I  (logarithmic barrier)
Lecture 16: Interior point II (primal-dual)
Lecture 17: Conic and semidefinite programming 
Lecture 18: Relaxations of hard problems 
Lecture 19: Branch and bound, Lagrangian relaxation
Lecture 20: Nondifferentiable optimization, subgradients
Lecture 21: Subgradients and cutting planes
Lecture 22: Bundle methods (convex, nonconvex), gradient sampling
Lecture 23: Variational inequalities
Lecture 24: Review / Additional topics
Lecture 25: Final exam (take home)

***You can find all the course material (as taught in Spring 2017) here.***
​
References