Sublinear-time Algorithms and Faithfulness Metrics for Big Complex Graph Visualisation

Abstract

With the continuing ability to gather and store increasingly larger amounts of data, so has grown the size of network data being collected. The networks, which can be represented as graphs, are not only big in scale, but also complex, introducing issues of scalability and complexity in visualising and analysing them. With the rate of growth in the size of these graphs, traditional graph drawing algorithms have failed to scale when visualising big, complex graphs. Furthermore, evaluation of graph drawing algorithms is important to ensure that the algorithms are not only efficient, but also effective. Yet, traditional quality metrics have been shown to be not as effective in evaluating drawings of big complex graphs.

In this thesis, we first present new sublinear-time graph drawing algorithms to efficiently visualise and analyse big complex graphs. More precisely, we present the following algorithms for drawing big graphs: topological spectral sparsification for fast, good quality graph sampling, as well as sublinear-time force-directed algorithms and sublinear-time stress-based algorithms for graph drawing. Our algorithms run faster than the current state-of-the-art linear-time graph drawing algorithms, while obtaining similar or even better quality drawings.

We then present new faithfulness metrics for the evaluation of complex graph drawing,where faithfulness measures how well the drawing depicts the ground truth information of the underlying graph. Specifically, we present the cluster faithfulness metric, symmetry quality metric, and change faithfulness metrics. Our metrics have been validated to effectively evaluate the quality of drawings of complex graphs, based on how well they depict the ground truth information of the graphs.