GraphAbility

VIP ChallENG research goals

A graph is an abstraction of a network and the efficient treatment and analysis of graphs is core to many applications including neural networks, transportation and telecommunication networks, electrical grids, Google’s PageRank and social networks. 

In this project, we’ll examine a variety of application areas in order to prioritise which algorithms to implement. One such area is an organ exchange network where patients have willing but incompatible donors. This network is able to give information about compatible transplants along cycles to save lives. 

Our project would seek to:

• Fill in information gaps in the network
• Calculate the probability of success of individual transplants
• Optimise donor transfer in the network, taking the dynamics of the network into account.

Another application we might explore is deep learning. Recent advances in deep learning require the processing, optimisation and analysis of large directed graphs that are highly symmetric. In order to help design new neural nets, graph parameters give insights about what kind of neural nets work well (the “depth” of networks has led to the well-known term “deep learning”). This project would seek to provide implementations to compute a variety of parameters.
 

Research, design or technical ChallENG

We will: 

• Precisely formalise the exact tasks our algorithms should solve 
• Study existing algorithms 
• Design our own algorithms 
• Implement the algorithms 
• Design user interfaces to visualise graphs and their properties 
• Design user interfaces targeted to the application areas 
• Design an automated test environment 
• Critically compare algorithms and their implementations 

We aim to incorporate a selection of our algorithms into the open-source Python-based software system called SageMath. 

Desired Background

All degrees are welcome however, students specialising in the below areas are encouraged to apply.