T-79.7003

Graphs and Networks

Graphs and Networks

- Lecture 1 (Sep 13, 2013): introduction

- Lecture 2 (Sep 20, 2013): thresholds for K4s and graph connectivity
- 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
- Simulation video, the evolution of the G(n,p) random graph

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

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

- 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
- 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

- 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
- 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