Quasi-Isometric Graph Simplification and Graph Centrality

Abstract

This thesis studies some theoretical aspects of graph simplifications. Graph simplifications are methods to transform a graph into a smaller representation such that computation on the simplified representation becomes more efficient while remaining reasonably accurate. The distance query is a common computation task on graphs, and we introduce the concept of quasi-isometries as a measure of the distance distortions of graph simplifications. We also introduce a generic graph simplification method called partition-graphs. This method constructs a new graph based on a partition of the original vertices into subsets that induce connected subgraphs. We establish that a partition-graph is quasi-isometric to the original graph, with the quasi-isometry’s parameters depending on the diameters of the subsets. In addition to studying quasi-isometries and distance distortions, we investigate the preservation of two centrality concepts: the centre and the median. Although we have found partition-graphs of trees that do not preserve the centres and medians, we show specific method of constructing partition-graphs of a tree that preserves the centre or the median. Finally, we focus on the set of all possible partition-graphs of a path, which are called partition-paths and can be viewed as integer compositions with restricted part-sizes. Under three specific settings, we use combinatorial techniques to derive a recurrence to count the total number of balanced partition-paths, and establish regular-language characterisations of the possible outcomes of two probabilistic path-partitioning algorithms.