Level: MSci, MSc
Title: Correlation dimension of complex networks using random walks
Supervisor:

Dr Lucas Lacasa
Research Area: Complex Systems and Networks
Description:

The so called Grassberger-Procaccia algorithm is a canonical numerical method used in chaos theory to numerically compute the fractal dimension of the attractor of chaotic dynamical systems from a sufficiently long time series of the trajectory. Recently, this idea has been extended to the realm of network science, in an attempt to define a fractal dimension in graphs analogous to the correlation dimension, whose computation is solely based on local information. This network-version of the Grassberger-Procaccia algorithm makes use of the trajectory of random walkers diffusing on a spatial network to infer an estimate of the network's dimensionality.

In this project the student could explore one of two possible avenues.

Avenue 1: The first one aims to improve the numerical convergence of the generalized algorithm (see [1]) by using the concept of non-backtracking random walks (random walks that are not allowed to come back to the previous position).
Avenue 2: The second focuses on how to extend this formalism to non-spatial networks (networks whose nodes do not have a natural spatial embedding).

Note: this is an advanced research project which could ultimately turn into a publication, so the candidate should be especially strong and motivated.

  1. L. Lacasa and J. Gómez-Gardeñes, Correlation dimension of complex networks, Physical Review Letters 110 168703 (2013). 
Further Reading:
Key Modules:

MTH6142 Complex Networks

MTH744U/MTH744P Dynamical Systems

MTH6107 Chaos and Fractals (desirable)

MTH6141 Random Processes (desirable)
Other Information:

Very good management of a programming language is required.
Current Availability: Yes