Processing massive graphs under limited visibility

Trehan, Chhaya (2023) Processing massive graphs under limited visibility. PhD thesis, London School of Economics and Political Science.

Text - Submitted Version Download (689kB)

Abstract

Graphs are one of the most important and widely used combinatorial structures in mathematics. Their ability to model many real world scenarios which involve a large network of related entities make them useful across disciplines. They are useful as an abstraction in the analysis of networked structures such as the Internet, social networks, road networks, biological networks and many more. The graphs arising out of many real world phenomenon can be very large and they keep evolving over time. For example, Facebook reported over 2:9 billion monthly active users in 2022. Another very large and dynamic network is the human brain consisting of around 1011 nodes and many more edges. These large and evolving graphs present new challenges for algorithm designers. Traditional graph algorithms designed to work with centralised and sequential computing models are rendered useless due to their prohibitively high resource usage. In fact one needs huge amounts of resources just to read the entire graph. A number of new theoretical models have been devised over the years to keep up with the trends in the modern computing systems capable of handing massive input datasets. Some of these models such as streaming model and the query model allow the algorithm to view the graph piecemeal. In some cases, the model allows the graph to be processed by a set of interconnected computing elements such as in distributed computing. In this thesis we address some graph problems in these non-centralised, non-sequential models of computing with a limited access to the input graph. Specifically, we address three different graph problems, each in a different computing model. The first problem we look at is the computation of approximate shortest paths in dynamic streams. The second problem deals with finding kings in tournament graphs, given query access to the arcs of the tournament. The third and the final problem we investigate is a local test criteria for testing the expansion of a graph in the distributed CONGEST model.

Item Type:	Thesis (PhD)
Additional Information:	© 2023 Chhaya Trehan
Library of Congress subject classification:	Q Science > QA Mathematics
Sets:	Departments > Mathematics
Supervisor:	Batu, Tugkan
URI:	http://etheses.lse.ac.uk/id/eprint/4519

Actions (login required)

Record administration - authorised staff only