Large Graph-Mining: Power Tools and a Practitioner's Guide

author: Christos Faloutsos, Computer Science Department, Carnegie Mellon University
author: Gary L Miller, School of Computer Science, Carnegie Mellon University
author: Charalampos E. Tsourakakis, School of Computer Science, Carnegie Mellon University
published: Sept. 14, 2009,   recorded: June 2009,   views: 8843

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.

 Watch videos:   (click on thumbnail to launch)

Watch Part 1
Part 1 1:14:32
Watch Part 2
Part 2 1:12:36


Numerous real-world datasets are in matrix form, thus matrix algebra, linear and multilinear, provides important algorithmic tools for analyzing them. The main type of datasets of interest in this tutorial are graphs. Important datasets modeled as graphs include the Internet, the Web, social networks (e,g Facebook, LinkedIn), computer networks, biological networks and many more.

We will discuss how we represent a graph as a matrix (adjacency matrix, Laplacian) and the important properties of those representations. We will then show how these properties are used in several important problems, including node importance via random walks (Pagerank), community detection (METIS, Cheeger inequality), graph isomorphism and graph similarity. Important dimensionality reduction techniques (SVD and random projections) will be discussed in the context of graph mining problems.

Furthermore, we provide a survey of the work on the epidemic threshold, node proximity and center-piece subgraphs. State-of-art graph mining tools for analyzing time evolving graphs will also be presented. Throughout the tutorial, patterns in static and time evolving, weighted and unweighted real-world graphs will be presented.

The target audience are data mining professionals who wish to know the most important matrix algebra tools, their applications in large graph mining and the theory behind them.

Prerequisites: Computer science background (B.Sc or equivalent); familiarity with undergraduate linear algebra.

Demos will be presented.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Joanne1982, October 5, 2009 at 1:35 a.m.:

part 2 is not worth seeing, embarrassing I would rather say. Where were the other two presenters?

Write your own review or comment:

make sure you have javascript enabled or clear this field: