Graph Mining (Wintersemester 2016/2017)

Lecturer:
Course Website: https://hpi.de/en/mueller/lehre/aktuelle-vorlesung/ws-1617/graph-mining.html

General Information

• Weekly Hours: 2
• Credits: 3
• Graded: yes
• Enrolment Deadline:
• Teaching Form: Lecture
• Enrolment Type: Compulsory Elective Module
• Maximum number of participants: 20

Programs, Module Groups & Modules

Description

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.

Requirements

Students are expected to have the following background:

• Basic computer science and programming.
• Data-mining knowledge is a plus but is not strictly required.
• Basic probability theory and linear algebra are beneficial, although a small recap of the main concepts will be done at the beginning of the required lectures.

Literature

For this course there is no official book. All the material, including slides, references, and videos, will be posted in the official page or in the intranet. However, the following, incomplete, list, can be used as complementary material: 

• Aggarwal, C.C. and Wang, H. eds., 2010.Managing and mining graph data (Vol. 40). New York: Springer.
• Chakrabarti, D. and Faloutsos, C., 2012. Graph mining: laws, tools, and case studies. Synthesis Lectures on Data Mining and Knowledge Discovery, 7(1), pp.1-207.
• Easley, D. and Kleinberg, J., 2010. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press.
• Rehman, S.U., Khan, A.U. and Fong, S., 2012, August. Graph mining: A survey of graph mining techniques. In Digital Information Management (ICDIM), 2012 Seventh International Conference on (pp. 88-92). IEEE.

Examination

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. 

• 10% Practical project and report
• 20% Paper presentation during lecture time
• 70% Oral exam

Zurück