Graphs have experienced an explosion in the number of applications and have proved high versatility in different domains, such as biology, social analysis, climatology. A graph is a network of nodes and relationships between them (edges) and can be used to model behaviours of individuals or objects interacting one another. Due to the large interest in graphs many methods have appeared to retrieve non trivial information from them. As a parallel with traditional data (text) graph mining studies ways to extract patterns, infer behaviours, retrieve rules, querying, predict links, finding communities and many other things.
The course is intended to provide an introduction to the broad topic of graph mining, with a focus on challenges, algorithmic solutions and new problems. Broadly speaking the course will touch the following topics:
- Background concepts: probability theory/statistics, basic linear algebra, basic graph concepts (morphisms, degrees, matrix representation, ...)
- Graph querying: exact and approximate - Reachability queries
- Frequent subgraph mining
- Graph indexing
- Random walks
- Graph clustering and anomaly detection
- Link prediction
- Summary of algorithms for different models (graph streams, evolving graphs, probabilistic graphs, colored graphs)
- Some practical graph mining framework
The course has no prerequisites, although a basic knowledge in data mining, statistics and linear algebra would be beneficial. All the basic and advanced aspects will be covered, with details on state of the art algorithms and fundamentals of the discipline.
In addition, the student will be able at the end of the course of identify a number of problems related to real world graphs and acquire specific skills in the solution of graph problems.