Material Detail

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

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

This video was recorded at 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Paris 2009. 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.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.