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

ABSTRACT

Graphs are powerful and versatile data structures that can be used to represent a wide range of different types of information. In this article, 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 a 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. Supplementary materials for this article are available online.

KEYWORDS:

• Data depth
• Descriptive statistics
• Ensemble
• Graph
• Paths

Supplementary Materials

Python code for path boxplot: All code and datasets are included in the PathBoxplot.zip file. The root folder contains scripts to perform analysis and generate visualizations for synthetic, AS network, and road network for all examples in the manuscript. Instructions for running the experiments are included in readme.txt located in the root folder.

Acknowledgments

This material is based upon work supported by the National Science Foundation under grants IIS-1212806 and CNS-1302688.