Korea Advanced Institute of Science and Technology
CS760 Big Graph Mining
Spring 2013 - U Kang

News and Announcements

Course Information

Big graphs are everywhere: examples include the World Wide Web, social network, mobile call network, biological network, and many more. Mining big graphs helps us find userful patterns and anomalies which lead to high impact applications including fraud detection, recommendation system, cyber security, etc.
The course covers advanced algorithms for mining and managing big graphs. Topics include MapReduce/Hadoop, approximation, graph compression, power laws, community detection, graph structure analysis, triangle counting, link analysis, spectral graph analysis, tensor analysis, and anomaly detection.

Schedule

Lecture Date Topic Due
1 Mar 5 Course Introduction
2 7 Graph-1: basics and diameter
(Optional Reading)
3 12 Graph-2: models
(Mandatory Reading) (Optional Reading)
4 14 Graph-3: power law
(Mandatory Reading) (Optional Reading)
5 19 Graph-4: structure analysis
(Mandatory Reading)
6 21 Spectral analysis-1: random walk
(Optional Reading)
7 26 Spectral analysis-2: link analysis
(Mandatory Reading) (Optional Reading)
8 28 Spectral analysis-3: link prediction
(Mandatory Reading) (Optional Reading)
9 Apr 2 Spectral Analysis-4: triangle counting
(Optional Reading)
Proposal due (12:55 pm)
10 4 MapReduce-1: architecture
(Mandatory Reading)
9 No class
11 11 MapReduce-2: basic techniques
(No Mandatory Reading)
12 16 MapReduce-3: graphs
(Optional Reading)
13 18 Guest Lecture: "Managing Skew in the Parallel Evaluation of User-Defined Operations" by Yongchul Kwon
(Optional Reading)
23 Midterm week
25 Midterm week
14 30 SVD-1: basic definition
(Optional Reading)
15 May 2 SVD-2: case studies
(Optional Reading)
Progress report due (12:55 pm)
16 7 SVD-3: properties
(Optional Reading)
17 9 Tensor Analysis
(Mandatory Reading) (Optional Reading)
18 14 Data analysis on Hadoop
(No Mandatory Reading)
Hadoop homework out
19 16 Approximation
(Mandatory Reading)
21 Project progress presentation
20 23 Graph compression
(Mandatory Reading) (Optional Reading)
21 28 Community detection
(Mandatory Reading)
Hadoop homework due
(12:55 pm)
22 30 Anomaly detection
(Optional Reading)
June 4 No class
6 No class (holiday)
23 11 Conclusions - Review lecture Final reports due (12:55 pm)
13 Poster session
18 Final exam week
20 Final exam week

Grading

Homework

  1. Paper critique. (20%) The homework is composed of paper critiques for the 'mandatory' assigned readings. Before each class, the assigned readings will be posted to the homepage. Your task is to create an ~1 page summary for each of the readings. The summary should include the following content: Submit: the hard copy of the report before class.
  2. Data analysis on Hadoop (10%)

Late policy - for all deliverables:

Project

Textbook

There is no textbook required.
Last modified Mar. 6, 2013, by U Kang