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 <i>band depth</i> 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 <i>path boxplot</i>, 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.

图（Graph）是一类功能强大且通用性优异的数据结构，可用于表征多种不同类型的信息。本文提出一种方法，用于分析并可视化一类基于图结构描述的重要数据——即路径集合（path ensembles）。此类路径集合的分析方法在交通、计算机网络、分子动力学等多个领域的诸多应用中均具有实用价值。所提方法将带深度（band depth）的概念推广至图结构上的路径集合，由此可生成路径的中心向外排序结果；该排序可进一步用于构建适用于图结构路径的常规箱线图（boxplot）与须状图（whisker plot）的推广形式，即路径箱线图（path boxplot）。本文通过计算机网络与道路场景下的路径集合实例，验证了路径箱线图的实用价值。