EPSRC Reference: 
EP/S027920/1 
Title: 
Assessing spatial heterogeneity through random walks on graphs 
Principal Investigator: 
Nicosia, Dr V 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

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: 

Summary on Grant Application Form 
This proposal addresses the problem of studying the heterogeneity of a variable of interest in spatiallydistributed 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 longstanding 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 subclones, due to the occurrence of genetic mutations, and some of those subclones often develop resistance to chemotherapy, accelerating the growth of the tumor. Recent research suggested that the number of distinct subclones 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 subclone 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 interclass 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 interclass 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 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: 
