EPSRC Reference: 
EP/R022615/1 
Title: 
Random walks on dynamic graphs 
Principal Investigator: 
Sousi, Dr P 
Other Investigators: 

Researcher CoInvestigators: 

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: 

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 wellconnected is the network? This is not a wellposed 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 realworld 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 timeinhomogeneous 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 nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

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 