# General Information

Instructor: Charalampos E. Tsourakakis
Classroom: EPC 204
Time: Mondays, 2:30 pm-5:15 pm
Office hours: Fridays 2-3pm (upon appointment)
Email: tsourolampis at gmail dot com.

# Course description

How can we develop a better understanding of real-world networks? This course aims to introduce students to important topics in large-scale 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, graph-based 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.

# Piazza

• 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

1. HW1.pdf , due by March 16th
2. HW2.pdf, due by April 13th

# Schedule

### Module 1: Random graphs

Lecture 1 (Jan 27th, 2020): Introduction. Real-world 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 $G(n,p)$.

## Lecture 2, Scribe

Lecture 3 (Feb. 18, 2020): Chernoff bounds. Sudakov-Krivelevich proof for the emergence of the giant component. Power law degree distributions.

## Lecture 3, Scribe

Lecture 4 (Feb. 24, 2020): Small-world phenomenon.

## Lecture 4, ScribeLecture 4, Slides

### Module 2: Space-efficient graph mining

Lecture 5 (Feb. 24, 2020)Flajolet-Martin sketches. ANF algorithm for diameter estimation on massive graphs.