B027492 - ADVANCED ALGORITHMS AND GRAPH MINING

Italian.

Graphs are present in a large number of applications, and the analysis of their properties makes it possible to understand their structure. In this course, we study algorithms for facing the following two problems: the analysis and comparison of a collection of many relatively small graphs, and the analysis of the properties of a single very large graph.

Lecture notes.

The purpose of this course is to introduce students to the design, the analysis and the experimentation of graph mining algorithms. By the end of the course, the students will have a thorough understanding of the graph mining foundations, and will be able to critique graph mining methods, to formulate and solve graph-related problems, and to analyse large-scale graphs.

Students are expected to (1) have basic knowledge of algorithms and data structures, (2) have basic knowledge of linear algebra, (3) be familiar with basic probability theory and statistics, and (4) have good programming skills (e.g. in Java).

Traditional lessons.

The course marks will be distributed among an oral exam at the end, a paper presentation and a small pratical project with the following scheme: 25% practical project and report,
25% paper presentation, 50% oral exam.

Matching and distance computation. Transformation-based distance computation. Frequent substructure mining. Clustering. Classification. Social networks: preliminaries and properties. Community detection. Collective classification. Link prediction. Social influence analysis.