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 tendency to mistakenly follow apparent paths in addition to true topological paths. The algorithmic implementation 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 factors 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 RT and error using search-set factors.
TamassiaR.On embedding a graph in the grid with the minimum number of bends. SIAM J Comput1987; 16(3): 421–444.
2.
BattistaGDEadesPTamassiaR. Graph drawing: algorithms for the visualization of graphs. Upper Saddle River, NJ: Prentice Hall, 1998.
3.
FerrariDMezzaliraL. On drawing a graph with the minimum number of crossings. Technical report. Report no. 69-11, 1969. Milano: Istituto di Elettrotecnica ed Elettronica, Politecnico di Milano.
4.
EadesP.A heuristic for graph drawing. Congr Numer1984; 42: 149–160.
5.
BurchMHeinrichJKonevtsovaN. Evaluation of traditional, orthogonal, and radial tree diagrams by an eye tracking study. IEEE T Vis Comput Gr2011; 17(12): 2440–2448.
6.
PohlMSchmittMDiehlS. Comparing the readability of graph layouts using eyetracking and task-oriented analysis. In: Proceedings of the fifth Eurographics conference on computational aesthetics in graphics, visualization and imaging, Victoria, Canada, 28–30 May 2009 pp. 49–56. Aire-la-Ville: Eurographics Association.
7.
HuangWEadesPHongS. A graph reading behavior: geodesic-path tendency. In: Proceedings of IEEE Pacific visualization symposium, Beijing, China, 20–23 April 2009, pp. 137–144. Washington, DC: IEEE Computer Society.
8.
HuangWHuangM.Exploring the relative importance of number of edge crossings and size of crossing angle: a quantitative perspective. Int J Adv Intell2011; 3(1): 25–42.
9.
KörnerC.Sequential processing in comprehension of hierarchical graphs. Appl Cognitive Psych2004; 18(4): 467–480.
10.
DunneCShneidermanB. Improving graph drawing readability by incorporating readability metrics: a software tool for network analysts. HCIL technical report. Report no. HCIL200913, 2009. College Park, MD: University of Maryland.
11.
DwyerTLeeBFisherD. A comparison of user-generated and automatic graph layouts. IEEE T Vis Comput Gr (Proc InfoVis) 2009; 15(6): 961–968.
12.
Van HamFRogowitzB. Perceptual organization in user-generated graph layouts. IEEE T Vis Comput Gr (Proc InfoVis) 2008; 14(6): 1333–1339.
13.
ClevelandWSMcGillR.Graphical perception: theory, experimentation, and application to the development of graphical methods. J Am Stat Assoc1984; 79(387): 531–554.
14.
HeerJKongNAgrawalaM. Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations. In: Proceedings of the SIGCHI conference on human factors in computing systems, Boston, MA, 4–9 April 2009, pp. 1303–1312. New York: ACM Press.
15.
KornaropoulosEMTollisIG. DAGView: an approach for visualizing large graphs. In: Proceedings of the 20th international conference on graph drawing, Redmond, WA, 19–21 September 2012, pp. 499–510. Berlin, Heidelberg: Springer-Verlag.
16.
YuanXCheLHuY. Intelligent graph layout using many users’ input. IEEE T Vis Comput Gr (Proc InfoVis) 2012; 18(12): 2699–2708.
17.
SedlmairMTatuAMunznerT. A taxonomy of visual cluster separation factors. Comput Graph Forum (Proc EuroVis) 2012; 31(3): 1335–1344.
18.
BrehmerMMunznerT.A multi-level typology of abstract visualization tasks. IEEE T Vis Comput Gr (Proc InfoVis) 2013; 19(12): 2376–2385.
19.
LeeBPlaisantCParrCS. Task taxonomy for graph visualization. In: Proceedings of the 2006 AVI workshop on BEyond time and errors: novel evaluation methods for information visualization, Venezia, 23–26 May 2006, pp. 1–5. New York: ACM Press.
20.
PurchaseHCCohenRFJamesMI. Validating graph drawing aesthetics. In: Proceedings of the symposium on graph drawing, Passau, 20–22 September 1995, pp. 435–446. London: Springer-Verlag.
21.
PurchaseH.Which aesthetic has the greatest effect on human understanding? In:Proceedings of the 5th international symposium on graph drawing, Rome, 18–20 September 1997, pp. 248–261. London: Springer-Verlag.
22.
PurchaseH.Performance of layout algorithms: comprehension, not computation. J Visual Lang Comput1998; 9(6): 647–657.
23.
WareCPurchaseHColpoysL. Cognitive measurements of graph aesthetics. Inform Visual2002; 1(2): 103–110.
24.
KörnerC.Eye movements reveal distinct search and reasoning processes in comprehension of complex graphs. Appl Cognitive Psych2011; 25(6): 893–905.
25.
HuangW.Establishing aesthetics based on human graph reading behavior: two eye tracking studies. Pers Ubiquit Comput2013; 17(1): 93–105.
26.
GhoniemMFeketeJ-DCastagliolaP. A comparison of the readability of graphs using node-link and matrix-based representations. In: Proceedings of the IEEE symposium on information visualization, Austin, TX, 10–12 October 2004, pp. 17–24. Washington, DC: IEEE Computer Society.
27.
WareC.Information visualization: perception for design. 3rd ed.San Francisco, CA: Morgan Kaufmann, 2000.
28.
HeerJBostockM. Crowdsourcing graphical perception: using mechanical turk to assess visualization design. In: Proceedings of the SIGCHI conference on human factors in computing systems, Atlanta, GA, 10–15 April 2010, pp. 203–212. New York: ACM Press.
29.
RensinkRABaldridgeG.The perception of correlation in scatterplots. Comput Graph Forum2010; 29(3): 1203–1210.
30.
JänickeHChenM. A salience-based quality metric for visualization. In: Proceedings of the 12th Eurographics/IEEE – VGTC conference on visualization, Bordeaux, 9–11 June 2010, pp. 1183–1192. Aire-la-Ville: Eurographics Association.
31.
MoscovichTChevalierFHenryN. Topology-aware navigation in large networks. In: Proceedings of the SIGCHI conference on human factors in computing systems, Boston, MA, 4–9 April 2009, pp. 2319–2328. New York: ACM Press.
32.
MarksJAndalmanBBeardsleyPA. Design galleries: a general approach to setting parameters for computer graphics and animation. In: Proceedings of the 24th annual conference on computer graphics and interactive techniques, Los Angeles, CA, 5–7August1997, pp. 389–400. New York: ACM Press.
33.
ArchambaultDMunznerTAuberD.TopoLayout: multilevel graph layout by topological features. IEEE T Vis Comput Gr2007; 13(2): 305–317.
34.
DwyerTMarriottKStuckeyPJ. Fast node overlap removal. In: Proceedings of the 13th international conference on graph drawing, Limerick, 12–15 September 2005, pp. 153–164. Berlin, Heidelberg: Springer-Verlag.
35.
BorgattiSP.Centrality and network flow. Soc Networks2005; 27: 55–71.
36.
CorreaCCrnovrsaninTMaK-L.Visual reasoning about social networks using centrality sensitivity. IEEE T Vis Comput Gr2012; 18(1): 106–120.
37.
HuangWHongSEadesP. Layout effects on sociogram perception. In: Proceedings of the 13th international symposium on graph drawing, Limerick, 12–14 September 2005, pp. 262–273. Berlin, Heidelberg: Springer-Verlag.
38.
HimsoltM.Comparing and evaluating layout algorithms within GraphEd. J Visual Lang Comput1995; 6: 255–273.
39.
PurchaseHCAllderJCarringtonD.Graph layout aesthetics in UML diagrams: user preferences. J Graph Algorithm Appl2002; 6(3): 255–279.
40.
VicenteKTorenvlietGL.The earth is spherical (p < 0.05): alternative methods of statistical inference. Theor Issues Ergon Sci2000; 1(3): 248–271.
41.
HaynesSNLenchHC.Incremental validity of new clinical assessment measures. Psychol Assessment2003; 15(4): 456–466.
42.
HunsleyJMeyerGJ.The incremental validity of psychological testing and assessment: conceptual, methodological, and statistical issues. Psychol Assessment2003; 15(4): 446–455.
43.
PurchaseHCPilcherCPlimmerB.Graph drawing aesthetics: created by users not algorithms. IEEE T Vis Comput Gr (Proc InfoVis) 2012; 18(1): 81–92.
44.
PurchaseHCPlimmerBBakerR. Graph drawing aesthetics in user-sketched graph layouts. In: Proceedings of the Australasian conference on user interface, Brisbane, QLD, Australia, 18–22 January 2010, pp. 80–88. Darlinghurst, NSW, Australia: Australian Computer Society, Inc.
45.
HuangWHongSEadesP. Effects of crossing angles. In: Proceedings of IEEE Pacific visualization symposium, Kyoto, Japan, 5–7 March 2008, pp. 41–46. Washington, DC: IEEE Computer Society.
46.
MarriottKPurchaseHWybrowM. Memorability of visual features in network diagrams. IEEE T Vis Comput Gr (Proc InfoVis) 2012; 18(12): 2477–2485.
47.
PurchaseHHogganEGörgC. How important is the ‘mental map’? – an empirical investigation of a dynamic graph layout algorithm. In: Proceedings of 14th international symposium on graph drawing, Karlsruhe, 18–20 September 2006, pp. 184–195. Berlin, Heidelberg: Springer-Verlag.
48.
HuangWHongSEadesP. Predicting graph reading performance: a cognitive approach. In: Proceedings of Asia-Pacific symposium on information visualisation, Tokyo, Japan, 1–3 February 2006, pp. 207–216. Darlinghurst, NSW, Australia: Australian Computer Society, Inc.
49.
AndrienkoGLAndrienkoNVBurchMDW. Visual analytics methodology for eye movement studies. IEEE T Vis Comput Gr (Proc InfoVis) 2012; 18(12): 2889–2898.
50.
KimS-HDongZXianH. Does an eye tracker tell the truth about visualizations?: findings while investigating visualizations for decision making. IEEE T Vis Comput Gr (Proc InfoVis) 2012; 18(12): 2421–2430.
BarskyAMunznerTGardyJ. Cerebral: visualizing multiple experimental conditions on a graph with biological context. IEEE T Vis Comput Gr (Proc InfoVis) 2008; 14(6): 1253–1260.
53.
BishopCM.Pattern recognition and machine learning (information science and statistics). New York: Springer-Verlag, 2006.
54.
WattsDJStrogatzSH.Collective dynamics of ‘small-world’ networks. Nature1998; 393(6684): 440–442.
55.
AuberDChiricotaYJourdanF. Multiscale visualization of small world networks. In: Proceedings of information visualization, Seattle, WA, 19–21 October 2003, pp. 75–84. Washington, DC: IEEE Computer Society.
56.
MelançonG.Just how dense are dense graphs in the real world? In: Proceedings of the 2006 AVI workshop on BEyond time and errors: novel evaluation methods for information visualization, Venezia, 23–26 May 2006, pp. 1–7. New York: ACM Press.
57.
HeerJCardSLandayJ. Prefuse: a toolkit for interactive information visualization. In: Proceedings of the SIGCHI conference on human factors in computing systems, Portland, OR, 2–7 April 2005, pp. 421–430. New York: ACM Press.
58.
CohenJ.Statistical power analysis for the behavioral sciences. Hillsdale, NJ: Lawrence Erlbaum Associates, 1988.
59.
FieldA.Discovering statistics using SPSS. 3rd ed.London: SAGE, 2009.
60.
HachulSJüngerM. Drawing large graphs with a potential-field-based multilevel algorithm. In: Proceedings of the 12th international conference on graph drawing, New York, 29 September–2 October 2004, pp. 285–295. Berlin, Heidelberg: Springer-Verlag.
61.
ArchambaultDMunznerTAuberD.GrouseFlocks: steerable exploration of graph hierarchy space. IEEE T Vis Comput Gr, 2008; 14(4): 900–913.
62.
DwyerT.Scalable, versatile and simple constrained graph layout. Comput Graph Forum (Proc EuroVis 09) 2009; 28(3): 991–998.
63.
BrandesU. Keynote address: why everyone seems to be using spring embedders for network visualization, and should not. In: Proceedings of the 2011 IEEE Pacific visualization symposium, Hong Kong, China, 1–4 March 2011, p. xii. Washington, DC: IEEE Computer Society.
64.
HoltenDIsenbergPvan WijkJJ. An extended evaluation of the readability of tapered, animated, and textured directed-edge representations in node-link graphs. In: Proceedings of the 2011 IEEE Pacific visualization symposium, Hong Kong, China, 1–4 March 2011, pp. 195–202. Washington, DC: IEEE Computer Society.
65.
RicheNHDwyerTLeeB. Exploring the design space of interactive link curvature in network diagrams. In: Proceedings of the international working conference on advanced visual interfaces, Capri, 22–25 May 2012, pp. 506–513. New York: ACM Press.
MeyerMSedlmairMQuinanPS. The nested blocks and guidelines model. Inform Visual2015; 14(3): 234–249.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
