Masterproef T704 : Most important locations on a large road map

Begeleiding:

Informatie:	Raf Vandebril	Wannes Meert
Promotoren:	Raf Vandebril	Wannes Meert
Begeleider:	Daan Camps

Onderzoeksgroep:

Numerieke Approximatie en Lineaire Algebra Groep

Context:

Data linked to applications can often be modeled by networks and graphs, e.g., gene interactions, the internet, traffic flows, human interactions, electricity networks. Often, the information about the network, however, is generated by indirect and noisy observations. For example, traffic flows are measured by collecting GPS measurements and mapping them to a road map.

Often one is not interested in quantitative information about traffic flows but is the desired goal to detect qualitative patterns. For example, the most important or most central nodes in such networks. Deriving such patterns from noisy observations requires techniques from both advanced linear algebra and artificial intelligence.

First, mapping GPS measurements to a set of possible roads can be expressed as a probabilistic graphical model, also called a map-matching problem. In this thesis, we will extend an existing model that allows us to compute the likelihood that following a certain road resulted in the given set of measurements.

Second, computing these central nodes relates to computing a matrix function of the adjacency matrix. In this thesis, we will focus on computing the matrix exponential of the adjacency matrix. Unfortunately, the networks are typically very large, and the computing time can become extremely large.

In this thesis we will construct and test a new algorithm based on approximate rational Krylov methods to retrieve the most important nodes in such a graph. Experiments will be carried out on GPS traces.

Doel:

We aim at developing a new algorithm, faster than the currently available methods. Depending on the student’s interest the topic can become more theoretical, more tailored towards high performance computing, more application oriented,…

Mogelijke Onderzoeksvragen:

What is the performance gain by using state-of-the-art linear algebra techniques for large graphs?
How are weighted graphs handled efficiently?

Uitwerking:

The student will first study the map matching application and the importance of centralizers. The link between graph theory and numerical linear algebra needs to be established, after which it will become clear that functions of matrices are an important ingredient in computing the centralizers. Also the link with approximate matrix functions via Krylov methods plays an important role.

Relevante literatuur:

Will be provided by the supervisors.

Profiel:

The student should have a basic knowledge of probabilistic graphical models, numerical linear algebra,
The student should be aware of the important aspects in scientific computing, such as accuracy, memory, and computing time.
The student should also be able to implement the algorithms in, e.g., Matlab, Python.

Deze masterproef is voor 1 student.