Masterproef T801 : Snelle berekening van meest centrale knopen in grote grafen
|
Begeleiding:
|
||||||
|
Onderzoeksgroep:
Numerieke Approximatie en Lineaire Algebra Groep
|
||||||
|
Context:
Grafen komen in zeer verscheidene toepassingen voor, vaak is men geïeresseerd in het berekenen van de belangrijke knopen (volgens een of andere maat). In dit onderwerp wordt een nieuw algoritme getest om de meest centrale knopen in grafen te berekenen. Dit wordt dan toegepast op verschillende applicaties en verder verfijnd. De meest rekenintensieve stap in de berekening van centrale knopen is het herhaaldelijk berekenen van matrix exponentiën en hun product met vectoren. De berekening van deze exponentiële zou sterk versneld kunnen worden door het gebruik van rationale Krylov methoden. Een nieuw algoritme, ontwikkeld door de promotor en Thomas Mach, wordt geïmplementeerd en getest op verscheidene applicaties, waarvan een deel door de student zelf aangebracht kan worden, zoals het berekenen van het aantal driehoeken in een graaf, onderzoeken van 'quantum walks' in een graaf en de analyse van de elektriciteitsnetwerken. De student onderzoekt dan verder hoe dit algoritme verder verfijnd kan worden naar verscheidene applicaties toe. |
||||||
|
Doel:
Het doel van de thesis is theoretisch onderzoek voeren naar nieuwe methoden en toepassingen maar ook praktisch gericht op implementeeraspecten. De bestaande nieuwe algoritmen worden geïlementeerd en vergeleken met de beste bestaande methoden. |
||||||
|
Uitwerking:
|
||||||
|
Profiel:
De student is vertrouwd met de basis van numeriek lineaire algebra. De student is geïeresseerd in implementeren en vergelijkingen van algoritmen. Deze masterproef is voor 1 student. |