EPSRC logo

Details of Grant 

EPSRC Reference: EP/R022615/1
Title: Random walks on dynamic graphs
Principal Investigator: Sousi, Dr P
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Pure Maths and Mathematical Statistics
Organisation: University of Cambridge
Scheme: New Investigator Award
Starts: 01 October 2018 Ends: 30 September 2020 Value (£): 113,961
EPSRC Research Topic Classifications:
Mathematical Analysis Statistics & Appl. Probability
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
29 Nov 2017 EPSRC Mathematical Sciences Prioritisation Panel November 2017 Announced
Summary on Grant Application Form
Let us consider a simplified model of a communication network. Two people can communicate if they are within distance 1 from each other. A graph is a mathematical object that can be used to model such a network. We think of the people as the vertices of the graph and we connect two of them by a line segment of length 1 (that we call edge) if they can communicate. Is this graph connected? In other words, can a rumour spread to the whole network?

If the answer to this question is yes, then the natural next question is: how well-connected is the network? This is not a well-posed question. One way of interpreting this is by asking whether removing an edge of this graph can change the connectivity property. Another natural way to probe the geometry of the graph is to analyse the behaviour of a random walk. A random walk models a particle moving on the vertices of the graph, at each time step jumping to a random neighbour.

Mixing, hitting and cover times are fundamental quantities that reveal features of the underlying graph's geometry and connectivity. The mixing time represents how long it takes the random walk to reach equilibrium, the hitting time is the time it takes for a random walk starting from one vertex to hit another, and the cover time is the amount of time it takes for the random walk to visit every vertex in the graph.

Graphs serve to model many real-world situations. However, most networks are not static in nature, but change with time. So it is natural to introduce dynamics and study properties of graphs whose connectivity properties change with time. In this setting studying mixing, hitting and covering properties of a random walk can give insight on the geometry and connectivity properties of the dynamical graph.

A lot of the classical tools used to analyse processes on static graphs do not carry over to the time-inhomogeneous setting. So in order to study mixing, hitting and covering properties of the walks we will need to develop new tools and techniques.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.cam.ac.uk