EPSRC logo

Details of Grant 

EPSRC Reference: EP/S027920/1
Title: Assessing spatial heterogeneity through random walks on graphs
Principal Investigator: Nicosia, Dr V
Other Investigators:
Researcher Co-Investigators:
Project Partners:
CEA - Atomic Energy Commission University of Birmingham
Department: Sch of Mathematical Sciences
Organisation: Queen Mary University of London
Scheme: New Investigator Award
Starts: 01 September 2019 Ends: 31 August 2021 Value (£): 162,887
EPSRC Research Topic Classifications:
Mathematical Analysis Mathematical Aspects of OR
Statistics & Appl. Probability
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
27 Feb 2019 EPSRC Mathematical Sciences Prioritisation Panel February 2019 Announced
Summary on Grant Application Form
This proposal addresses the problem of studying the heterogeneity of a variable of interest in spatially-distributed structures. Quite often the spatial domain under study can be coarsened and represented as a graph, and the variable of interest can take a discrete number of different values, indicated by labels or colours. Hence, the quantification of the spatial heterogeneity of a variable can be mapped onto the study of the distribution of labels in a graph with coloured nodes.

A typical example is the problem of identifying the social, economic, or ethnic segregation of an urban area. We say that the population of a city is segregated with respect to ethnicity or income level if people prefer to live in areas where other people of the same ethnicity or income level already live, avoiding areas that are inhabited by people of other ethnic groups or income levels. In this case, the system consists of a discrete set of regions (neighbourhoods, boroughs, etc), and can thus be represented by a planar graph of adjacency among regions, where each region (node) is assigned a label or colour according to the income level or most abundant ethnicity of its inhabitants. To determine the level of segregation of a city, one needs to quantify the heterogeneity of the distribution of those labels, under the assumption that higher heterogeneity usually corresponds to higher segregation. In general, the presence of high levels of segregation is the cause of economic and social tension. Consequently, assessing the level of segregation of a urban area is fundamental for policy makers, with potential repercussions on millions of lives. Despite being a long-standing question in urbanism and economics, there is currently no universal agreement about how segregation should be quantified, or on how to compare the levels of segregation measured in different areas.

A very different but relevant example is that of tumor growth. The cells of a tumor normally belong to several strains or sub-clones, due to the occurrence of genetic mutations, and some of those sub-clones often develop resistance to chemotherapy, accelerating the growth of the tumor. Recent research suggested that the number of distinct sub-clones of a tumor and the irregularity of their spatial distribution correlate with the speed at which the tumor grows. Also this system can be represented as a spatial graph, where each region of the tumor (node) is associated to a label or colour corresponding to the most abundant cancer sub-clone in that region. And also in this case, the quantification of the spatial heterogeneity of the distribution of labels on a graph can have important repercussions on the life of thousands of people.

This project proposes a novel way of quantifying heterogeneity in spatial systems, based on the trajectories of random walks over the associated adjacency graphs with coloured nodes. A random walk is the simplest way to explore a graph -if you are on a node, you jump to one if its neighbours chosen at random- yet its trajectories retain a lot of information about the correlations among node properties. The main aim of this project is to study the statistical properties of trajectories of random walks on graphs with coloured nodes, focusing in particular on inter-class first passage times (the number of jumps needed to a random walk to get from a node of a certain colour to a node of another colour) and cover times (the number of jumps needed to visit at least one node of each colour). The Principal Investigator will provide analytical expressions for inter-class passage and cover times in different real and synthetic spatial graphs with coloured nodes, will use those expressions to quantify the heterogeneity of a given colour distribution, and, thanks to the collaboration with several research groups in the UK and abroad, will apply those measures to urban segregation, plant biology, and cancer research.
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: