• Lecture 1 (Sep 13, 2013): introduction
• Lecture notes (pdf)
• Slides
• Readings
• Statistical Mechanics of Complex Networks
• Graph structure in the Web
• Graph Evolution: Densification and Shrinking Diameter

• Lecture 2 (Sep 20, 2013): thresholds for K4s and graph connectivity
• Lecture notes (pdf)
• Matlab scripts
• Optional readings
• Colorful Triangle Counting and a MapReduce Implementation
  This paper contains the analysis of a randomized triangle counting algorithm
  which is based on the second moment method.
• Cayley's formula (ch. 26)
  We used Cayley's formula to upper bound the expected number of components of order k
  in G(n,p). This book contains four beautiful proofs of the formula.

• Lecture 3 (Sep 27, 2013): Phase transition
• HW1 is out
• Suggested papers are out
• Lecture slides (pdf)
• Readings
• The phase transition in random graphs-a simple proof
• Amin Saberi's notes
• Simulation video, the evolution of the G(n,p) random graph
  

• Lecture 4 (Oct 4, 2013): Probabilistic tools and random graph applications I
• Lecture notes (pdf)
• Readings
• Concentration (read Sections 1,2, pages 1-10)

• Lecture 5 (Oct 11, 2013): Probabilistic tools and random graph applications II
• Lecture notes (pdf)
• Readings
• Concentration (read Section 3, pages 10-26)
• Sharp concentration of the chromatic number on random graphs G(n,p)
• Optional Readings
• Chernoff applications
• Azuma-Hoeffding applications

• Midterm exam (Oct. 18, 2013)

• Fall midterm break (Oct. 25, 2013)

• Lecture 6 (Nov 1, 2013): Properties and models of real-world networks. Degree sequence of preferential attachment
• Lecture slides (pdf)
• Matlab scripts
• Readings
• The degree sequence of a scale-free random graph process
• For a quick proof sketch check 4.1 from this book chapter.
• Navigation in a small world
• Collective dynamics of 'small-world' networks
• Suggested Readings
• CHKNS model
• For more on the compressibility of the Web graph, read the paper Models for the Compressible Web and slides by Ravi Kumar on the above paper
• For an alternative way of obtaining degree sequences which follow a power law, read the paper Heuristically optimized trade-offs: A new paradigm for power laws in the Internet

• Lecture 7 (Nov 8, 2013): Random Walks on Graphs
• HW2 is out
• Lecture notes, Chapter 1 from Grimmett's book (pdf)
• Readings
• Random Walks and Electric Networks (pages 3-10)
• Effective resistance (Dan Spielman's notes)

• Lecture 8 (Nov 15, 2013): Spectral Clustering, Cheeger's inequality
• Lecture notes, Chapter 1 from Grimmett's book (pdf) (cont.)
• KDD'13 Tutorial (slides 133-176)
• Readings
• Cheeger's inequality I, Cheeger's inequality II (Dan Spielman's notes)

• Lecture 9 (Nov 22, 2013): One hour guest lecture on boostrap percolation by Dr. Thomas Vallier + project presentations
• Bootstrap percolation on G(n,p)
• Slides by Thomas Vallier
• Project Presentations
• Orestis
• Hristo
• Miquel
• Abdulmelik

• Lecture 10 (Nov 29, 2013): Project presentations
• Geraud, Louiza, Sanja
• Eric, Emanuelle
• Ehsan
• Polina
• HW3 is out

• Finland's Independence Day (Dec 6, 2013)

• Lecture 11 (Dec 13, 2013): Various topics
• Slides
• Dan Spielman's notes (pdf)
• Readings
• Chapters 3,6 and 8 from Mathematical and Algorithmic Analysis of Network and Biological Data
• Spectral Sparsification of Graphs by Nikhil Srivastava
  
• Spectral Sparsification of Graphs and Approximations of Matrices I by Daniel Spielman
  
• Spectral Sparsification of Graphs and Approximations of Matrices II by Daniel Spielman
  

---

Copyright (c) 2013 Charalampos E. Tsourakakis