On the Scalability of Large Graph Visualization

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "On the Scalability of Large Graph Visualization"

By

Mr. Yanhong WU


Abstract

As a natural representation of data, graph structures exist in many domains 
such as finance, sociology, biology, and software engineering. Visualization 
techniques have been widely utilized to facilitate graph analysis by taking 
advantages of human’s strong ability in visual perception. One of the most 
critical problems in graph visualization is scalability. Common graph 
visualization techniques do not scale well when the graph size increases to a 
certain degree, which prevents people from gaining insights into graphs. In 
this proposal, we aim to better understand and to solve the scalability problem 
in visualizing both static and dynamic graphs.

Our first work investigates the performance of different graph sampling 
algorithms in the perspective of visualization. We first conduct a pilot study 
to identify the important visual factors that need to be preserved after 
sampling from a visualization perspective. Then we conduct three controlled 
within-subject experiments to evaluate the performance of five common graph 
sampling algorithms in preserving these visual factors. After comparing and 
discussing our results with previous metric evaluation results, we propose 
several recommendations for selecting sampling algorithms in graph 
visualization.

The second work studies the evolution process of dynamic egocentric networks. 
More specifically, we propose egoSlider, an interactive visual analytics system 
that helps people explore, compare, and analyze dynamic egocentric network 
evolution in three hierarchical levels. The proposed technique is evaluated by 
two usage scenarios using an academic collaboration network and an e-mail 
communication network. Also, a controlled user study indicates that egoSlider 
outperforms a baseline visualization of dynamic networks for completing 
egocentric analytical tasks.

In the third work, we focus on network motifs, which are defined as small 
connected and induced subgraph patterns that serve as the simple building 
blocks of networks. We introduce an interactive visualization system that 
enables users to uncover the formation and evolution processes of network 
motifs. A usage scenario and a qualitative user study have also been conducted 
to demonstrate the effectiveness of the proposed method.


Date:			Wednesday, 16 August 2017

Time:			10:00am - 12:00noon

Venue:			Room 2610
 			Lifts 31/32

Chairman:		Prof. Jianfeng Cai (MATH)

Committee Members:	Prof. Huamin Qu (Supervisor)
 			Prof. Cunsheng Ding
 			Prof. Pedro Sander
 			Prof. Kai Tang (MAE)
 			Prof. Min Chen (Oxford U)


**** ALL are Welcome ****