Fast Algorithms for Huge Dynamic Graphs

Description

The project will be aligned with the EPSRC Centre for Doctoral Training CDT in Distributed Algorithms:The What, How and where of Next-Generation Data Science.

The student will benefit from the cohort-based training associated with the CDT as well as access to the CDT’s dedicated supercomputing facilities at the University of Liverpool.

The CDT is part of the wider Signal Processing Group where the student will benefit from collaborating with experts in Bayesian computational methodology, autonomy, decision support, data fusion, tracking, image processing, radar processing, acoustic analysis, text analytics, machine learning, behavioural analytics, simulation and energy-efficient hardware implementation.

Description: Analysing internet-scale data routinely involves graphs with millions of nodes and graphs that change over time. Protecting the UK’s interests necessarily involves processing data related to such dynamic graphs to extract important information pertinent to activities that could pose a threat to the UK.

Therefore, it is important to have scalable algorithms that can extract such information in dynamic contexts. While scalable algorithms do exist in the context of detecting specific known patterns of behaviour in (static and dynamic) graphs, there is also a need for scalable algorithms for detecting anomalous nodes, edges and subgraphs, and anomalous changes to these elements of the graph: anomalies might be indicative of malicious behaviours that have not been seen previously. For example, by detecting these anomalies, we could alert a human analyst that something needs to be investigated.

Many algorithms (and associated approximations), some of which are already scalable in certain contexts, do exist to calculate specific features of nodes, edges, and subgraphs. These algorithms could be used for detecting the anomalies of interest. For example, “betweenness centrality” can be used to identify interesting nodes and scalable algorithms (so long as the average number of edges per node is below a threshold).

This PhD will begin by developing an understanding of the relevance and performance of these existing algorithms at the scales and the dynamic contexts of interest. It will be particularly important to understand how these algorithms can be applied in the context of dynamic graphs and, more specifically, whether the dynamic nature of the problem can be capitalised upon with respect to the development of efficient algorithmic solutions.

The PhD will then proceed to devise techniques for extending the state-of-the-art with a focus on developing novel algorithms that can identify the anomalous dynamic behaviours of interest. This will involve both the mathematical development of novel techniques that respect the challenges posed in the context of both shared and distributed memory systems as well as implementation using, for example OpenMP and MPI.

Every project aligned to the CDT is offered in collaboration with an industrial partner who as well as providing co-supervision will also offer the unique opportunity for students to access state of the art computing platforms, work on real world problems, benchmarking, and data. Our graduates will gain unparalleled experiences working across academic disciplines in highly sought-after topic areas, answering industry need.

This project is kindly co-funded by GCHQ with the remainder of the funding being provided by the University of Liverpool. GCHQ will co-supervise the project with the aim of helping to specify aspects of the problem. The PhD will include a placement which will involve working with GCHQ to understand the applicability of the algorithms being developed to specific dynamic graphs of interest.

The project is suited to a candidate with an undergraduate or master’s degree in a numerate subject, with an interest in next generation data science, computing, and working with partners to solve real-world problems.

The successful student will be based at the University of Liverpool and be aligned to the CDT and Signal Processing Group .

The studentship is open to NATO nationals only.

Apply now: https://www.liverpool.ac.uk/distributed-algorithms-cdt/apply/

Applicants please note: You must not submit a research proposal. The PhD project is defined. You must provide a supporting statement (no more than 700 words) that explains why you are interested in undertaking a PhD, this specific topic and joining the research group. More application guidance can be found on the apply link above.