CSE 291-F

Course Overview

General Info: Graduate-level course, CSE Dept., UC San Diego, Spring quarter 2017

Lecture hours: Tuesday and Thursday, 18:30 - 19:50
Lecture room: PCYNH 106

Instructor: Fragkiskos Malliaros
Email: fmalliaros [at] eng.ucsd.edu
Office hours: TBA

TA: Mohammad Motiei
Email: mmotiei [at] eng.ucsd.edu
Office hours: TBA

Piazza: piazza.com/ucsd/spring2017/cse291f/home

Networks (or graphs) have become ubiquitous as data from diverse disciplines can naturally be mapped to graph structures. Social networks, such as academic collaboration networks and interaction networks over online social networking applications are used to represent and model the social ties among individuals. Information networks, including the hyperlink structure of the Web and blog networks, have become crucial mediums for information dissemination, offering an effective way to represent content and navigate through it. A plethora of technological networks, including the Internet, power grids, telephone networks and road networks are an important part of everyday life. The problem of extracting meaningful information from large scale graph data in an efficient and effective way has become crucial and challenging with several important applications and towards this end, graph mining and analysis methods constitute prominent tools. The goal of this course is to present recent and state-of-the-art methods and algorithms for exploring, analyzing and mining large-scale networks, as well as their practical applications in various domains (e.g., social science, the web, biology).

Schedule and Lectures

The topics of the lectures are subject to change (the following schedule outlines the topics that will be covered in the course). The slides for each lecture will be posted on piazza just before the start of the class.

Week	Date	Topic	Material	Assignments/Project
1	April 4	Introduction	Lecture 1
	April 6	Graph theory, linear algebra and ML basics recap	Lecture 2
2	April 11	Network properties and the random graph model
	April 13	Network generative models
3	April 18	Random walks and centrality criteria		Assignment 1 out
	April 20	Link analysis algorithms (PageRank and HITS)
4	April 25	Project proposal short presentations (all teams)		Project proposal slides due on April 24
	April 27	No class. Traveling to SDM 2017		Project proposal due
5	May 2	Graph clustering and community detection (Part I)		Assignment 1 due
	May 4	Graph clustering and community detection (Part II)
6	May 9	Node similarity and link prediction		Assignment 2 out
	May 11	Graph similarity, graph kernels and graph classification
7	May 16	Representation learning in graphs
	May 18	Influential spreaders and influence maximization
8	May 23	Anomaly detection		Project progress report due
	May 25	Graph sampling and summarization
9	May 30	Dense subgraph detection and applications		Assignment 2 due
	June 1	Rich network structures: signed, uncertain, multilayer graphs, geo-social and textual networks
10	June 6	Core decomposition in graphs
	June 8	Project presentations or poster session. The date is subject to change based on student's availability		Project final report due on June 10

Lecture 1: Introduction

Introduction to graph mining and network analysis, administrivia, course structure and overview of the topics that will be covered in the course.

Reading:

Networks, crowds, and markets (chapter 1)
The structure and function of complex networks (sections I and II)
Network science (chapter 1)

Lecture 2: Graph theory, linear algebra and ML basics recap

Presentation of basic concepts in graph theory, linear algebra and machine learning that will be used throughout the course.

Reading:

Networks, crowds, and markets (chapter 2)
Social media mining (chapters 2 and 5)
Notes in linear algebra, probability, and proof techniques
Lecture 3, Lecture 4 and Lecture 5 from CSE 258 (Julian's course)

Course Structure

Learning objectives

The course aims to introduce students to the field of graph mining and network analysis by:

Covering a wide range of topics, methodologies and related applications.
Giving the students the opportunity to obtain hands-on experience on dealing with graph data and graph mining tasks.

We expect that by the end of the course, the students will have a thorough understanding of various graph mining and learning tasks, will be able to analyze large-scale graph data as well as to formulate and solve problems that involve graph structures.

Prerequisites

There is no official prerequisite for this course. However, the students are expected to:

Have basic knowledge of graph theory and linear algebra.
Be familiar with fundamental data mining and machine learning tasks (e.g., CSE 258).
Be familiar with at least one programming language (e.g., Python or any language of their preference).

In the second lecture, we will review basic concepts in graph theory, linear algebra and machine learning.

Reading material

Most of the material of the course is based on research articles. Some of the topics are also covered by the following books:

David Easley and Jon Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.
Deepayan Chakrabarti and Christos Faloutsos. Graph Mining: Laws, Tools, and Case Studies. Synthesis Lectures on Data Mining and Knowledge Discovery, Morgan and Claypool Publishers, 2012.
Reza Zafarani, Mohammad Ali Abbasi and Huan Liu. Social Media Mining. Cambridge University Press, 2014.
Albert-Laszlo Barabasi. Network Science. Cambridge University Press, 2016.

Evaluation

The evaluation of the course will be based on the following:

Two hands-on practical assignments: the hands-on assignments will familiarize the students with basic graph mining and analysis tasks.
Project: this will be the main component for the evaluation of the course. The students are expected to form groups of 3-4 people, propose a topic for their project, and submit a final project report (it would also be interesting to organize a poster session at the end of the quarter). Please, read the project section for more details.

The grading will be as follows:

Assignment 1 (individual):	10%
Assignment 2 (groups of 3-4 students):	30%
Project (groups of 3-4 students):	60%

Academic integrity

UCSD and CSE's policies on academic integrity will be strictly enforced (please see here and here). In particular, all of your work must be your own. Some relevant excerpts from UCSD's policies are:

Don't copy another student's assignment, in part or in total, and submit it as your own work.
Acknowledge and cite source material in your papers or assignments.

Project

Details about the project will be posted here soon.

Resources

Datasets

Stanford Network Analysis Project (SNAP)
The Koblenz Network Collection (KONECT)
The Colorado Index of Complex Networks (ICON)
The Network Data Repository with interactive graph analytics and visualization.
Social Computing Data Repository at Arizona State University
Datasets from the Social Computing Research group at MPI-SWS.
Datasets from the AMiner academic social network.
Datasets from papers published in the International AAAI Conference on Web and Social Media (ICWSM). Also, check the previous ICWSM conferences.
Datasets from Jure Leskovec's class at Stanford.
Datasets of online social networks by Athina Markopoulou (UC Irvine).
Social media (Instagram and Facebook) datasets by Emilio Ferrara (USC).
KDD cup archives, uncluding a competition about Tencent Weibo (KDD is one of the premier data mining conferences). For this year (2017), the competition is currenty active and the topic is highway tollgates traffic flow prediction (using also the road network topology in the target area, among other data sources).
Graph datasets by Yibo Yao (WSU).
Sina Weibo dataset by Weiboscope (University of Hong Kong). Another Sina Weibo dataset by Tianchi can be found here.
Foursquare dataset by Dingqi Yang (University of Fribourg).
Datasets from the Spatial and Urban Networks group at CEA (Paris).
Yelp dataset challenge
Quora question pairs competition in Kaggle (currently active).
IlliMine repository from the Data Mining Research Group at UIUC (some network datasets are also included).

Software tools

NetworkX: Python software package for graph analytics
igraph: collection of software packages for graph theory and network analysis (Python, C++ and R)
SNAP: high performance system for the analysis of large network (C++ and Python)
Gephi: graph visualization and exploration software

CSE 291-F: Graph Mining and Network Analysis