Algorithmic methods for mining large graphs

Aristides Gionis

Bertinoro International Spring School 2016

Networks, or graphs, provide a powerful abstraction for modeling a wide variety of real-world data. Graph mining is the discipline of analyzing data represented as graphs. In this course we will provide an overview of some major problems in graph mining. We will then present fundamental algorithmic principles for solving those graph mining problems and discovering structure in large graphs; emphasis will be given in obtaining algorithms with provable guarantees and in the efficiency of the developed method.

Some of the algorithmic principles that will be discussed during the course are the following:
- combinatorial and graph-theoretic algorithms
- optimization of submodular functions
- sampling methods
- methods for graph sketching and sparsification

The list of topics that will be covered includes:
- efficient computation of motifs and graph statistics
- finding dense subgraphs
- inferrence of network structure
- mining time-evolving networks and graph streams.

Slides

Lecture 1: Introduction to graph mining
Lecture 2: Computing basic graph statistics
Lecture 3: Finding dense subgraphs
Lecture 4: Maximizing submodular functions
Lecture 5: Spectral graph analysis

Homework. Deadline: April 10, 2016.