Path Boxplots: A Method for Characterizing Uncertainty in Path Ensembles on a Graph

Graphs are powerful and versatile data structures that can be used to represent a wide range of different types of information. In this paper, we introduce a method to analyze and then visualize an important class of data described over a graph—namely, ensembles of paths. Analysis of such path ensembles is useful in a variety of applications, in diverse fields such as transportation, computer networks, and molecular dynamics. The proposed method generalizes the concept of band depth to an ensemble of paths on a graph, which provides an center-outward ordering on the paths. This ordering is, in turn, used to construct a generalization of the conventional boxplot or whisker plot, called a path boxplot, which applies to paths on a graph. The utility of path boxplot is demonstrated for several examples of path ensembles including paths defined over computer networks and roads.