Large Graph-Mining: Power Tools and a Practitioner's Guide
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: 1013
Report a problem or upload filesIf 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.
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 pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !