A search-set model of path tracing in graphs

---

Abstract | Paper | Figures | Supplemental Material

---

Abstract

We present a predictive model of human behaviour when tracing paths through a node-link graph, a low-level abstract task that feeds into many other visual data analysis tasks that require understanding topological structure. We introduce the idea of a search set, namely, the set of paths that users are most likely to search, as a useful intermediate level for analysis that lies between the global level of the full graph and the local level of the shortest path between two nodes. We present potential practical applications of a predicted search set in the design of visual encoding and interaction techniques for graphs. Our predictive model is based on extensive qualitative analysis from an observational study, resulting in a detailed characterization of common path-tracing behaviours. These include the conditions under which people stop following paths, the likely directions for the first hop people follow, the tendency to revisit previously followed paths and the ten- dency to mistakenly follow apparent paths in addition to true topological paths. The algorithmic implementa- tion of our predictive model is robust to a broad range of parameter settings. We provide a preliminary validation of the model through a hierarchical multiple regression analysis comparing graph readability fac- tors computed on the predicted search set to factors computed at the global level and the local shortest path solution. The tested factors included edge-edge crossings, node-edge crossings, path continuity and path length. Our approach provides modest improvements for predictions of response time and error using search-set factors.

Paper

Supplemental Material

Detailed description of Search Set model implementation and parameter selection, additional visualizations created for preliminary analysis:
→ PDF (4.0 MB)

---

Jessica Dawson

Last modified: Oct 1, 2014.