General Information
Instructor: Charalampos E. Tsourakakis
Classroom: EPC 204
Time: Mondays, 2:30 pm5:15 pm
Office hours: Fridays 23pm (upon appointment)
Email: tsourolampis at gmail dot com.
Course description
How can we develop a better understanding of realworld networks? This course aims to introduce students to important topics in largescale graph mining ranging from graph models to scalable algorithm design, and learning applications. Topics include random graph theory, algorithm design for key graph algorithmic problems, graphbased learning algorithms and applications.
Textbooks
The class does not a textbook. However, the following books that are also available in a draft form online will be useful during this course.
 Introduction to random graphs by Frieze and Karonski [FK]
 Networks, Crowds, and Markets by Easley and Kleinberg [EK]
 Spectral and algebraic graph theory by Spielman [S]
 Graph theory by Diestel [D]
Piazza
Grading
 Class Project 50%
 Two homeworks 25% (12.5%+12.5%)

Homework policy: You may collaborate on each homework with at most one other person. The name of your collaborator must be written down. You must write your solutions on your own. You may change collaborator from homework to homework. You may consult outside materials, but you must cite your sources in your solutions. You may not search the Web for solutions.
Violation of the policy may result in receiving a zero grade for the question or the assignment or even the whole course. The penalty will be assessed at the instructor’s discretion.
 Advice: Start early!

 Midterm Exam 15%
 Class scribe 10%
Problem sets
 HW1.pdf , due by March 16th
 HW2.pdf, due by April 13th
Schedule
Module 1: Random graphs
Lecture 1 (Jan 27th, 2020): Introduction. Realworld networks and their properties. Random graph models.
Lecture 1, Slides
Lecture 2 (Feb 2nd, 2020): Probabilistic tools. First and second moment method. Fundamental properties of .
Lecture 2, Scribe
Lecture 3 (Feb. 18, 2020): Chernoff bounds. SudakovKrivelevich proof for the emergence of the giant component. Power law degree distributions.
Lecture 3, Scribe
Lecture 4 (Feb. 24, 2020): Smallworld phenomenon.
Lecture 4, Scribe
Lecture 4, Slides
Module 2: Spaceefficient graph mining
Lecture 5 (Feb. 24, 2020): FlajoletMartin sketches. ANF algorithm for diameter estimation on massive graphs.
Lecture 5, Slides
Readings
 The phase transition in random graphs – a simple proof, by Krivelevich, Sudakov
 The degree sequence of a scale‐free random graph process, by Bollobás, Riordan, Spencer, Tusnády
 The smallworld phenomenon: an algorithmic perspective, by Kleinberg
 An elementary proof of a theorem of Johnson and Lindenstrauss, by Dasgupta, Gupta
 Optimality of the JohnsonLindenstrauss Lemma, by Green Larsen, Nelson
 Analyzing Graph Structure via Linear Measurements, by Ahn, Guha, McGregor
 ANF: A fast and scalable tool for data mining in massive graphs, by Palmer, Gibbons, Faloutsos