×

Visual similarity perception of directed acyclic graphs: a study on influencing factors and similarity judgment strategies. (English) Zbl 1398.05192

Summary: Visual comparison of directed acyclic graphs (DAGs) is commonly encountered in various disciplines (e.g., finance, biology). Still, knowledge about humans’ perception of their similarity is currently quite limited. By similarity perception, we mean how humans perceive commonalities and differences of DAGs and herewith come to a similarity judgment. To fill this gap, we strive to identify factors influencing the DAG similarity perception. Therefore, we conducted a card sorting study employing a quantitative and qualitative analysis approach to identify (1) groups of DAGs the participants perceived as similar and (2) the reasons behind their groupings. We also did an extended analysis of our collected data to (1) reveal specifics of the influencing factors and (2) investigate which strategies are employed to come to a similarity judgment.
Our results suggest that DAG similarity perception is mainly influenced by the number of levels, the number of nodes on a level, and the overall shape of the DAG. We also identified three strategies used by the participants to form groups of similar DAGs: divide and conquer, respecting the entire dataset and considering the factors one after the other, and considering a single factor. Factor specifics are, e.g., that humans on average consider four factors while judging the similarity of DAGs. Building an understanding of these processes may inform the design of comparative visualizations and strategies for interacting with them. The interaction strategies must allow the user to apply her similarity judgment strategy to the data. The considered factors bear information on, e.g., which factors are overlooked by humans and thus need to be highlighted by the visualization.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C38 Paths and cycles
05C90 Applications of graph theory

Software:

SimRank
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Archambault. Structural differences between two graphs through hierarchies. In Proc. GI, pages 87–94. Canadian Information Processing Society, 2009.
[2] D. Archambault, H. C. Purchase, and B. Pinaud. Difference map readability for dynamic graphs. In U. Brandes and S. Cornelsen, editors, Graph Drawing: 18th International Symposium, GD 2010, pages 50–61. Springer, 2011. · Zbl 1314.68213
[3] B. Bach, E. Pietriga, and J.-D. Fekete. Graphdiaries: Animated transitions and temporal navigation for dynamic networks. IEEE Trans. Vis. Comput. Graphics, 20(5):740–754, 2014.
[4] F. Beck, M. Burch, S. Diehl, and D. Weiskopf. The state of the art in visualizing dynamic graphs. In Proc. EuroVis - STARs, 2014.
[5] J. Bertin. Semiology of Graphics. University of Wisconsin Press, 1983.
[6] S. Bremm, T. Von Landesberger, M. Heß, T. Schreck, P. Weil, and K. Hamacher. Interactive visual comparison of multiple trees. In Proc. IEEE VAST, pages 31–40, 2011.
[7] S. Bridgeman and R. Tamassia. Difference metrics for interactive orthogonal graph drawing algorithms. In S. H. Whitesides, editor, Graph Drawing, pages 57–71, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg. · Zbl 0953.68110
[8] M. Burch, N. Konevtsova, J. Heinrich, M. Hoeferlin, and D. Weiskopf. Evaluation of traditional, orthogonal, and radial tree diagrams by an eye tracking study. IEEE Transactions on Visualization and Computer Graphics, 17(12):2440–2448, Dec 2011.
[9] B. S. Chaparro, V. D. Hinkle, and S. K. Riley. The usability of computerized card sorting: A comparison of three applications by researchers and end users. J. Usability Stud., 4(1):31–48, 2008.
[10] C. M. Collins and S. Carpendale. VisLink: Revealing relationships amongst visualizations. IEEE Trans. Vis. Comput. Graphics, 13(6):1192–1199, 2007.
[11] T. Dwyer, B. Lee, D. Fisher, K. I. Quinn, P. Isenberg, G. Robertson, and C. North. A comparison of user-generated and automatic graph layouts. IEEE Trans. Vis. Comput. Graphics, 15(6):961–968, 2009.
[12] S. N. Friel, F. R. Curcio, and G. W. Bright. Making sense of graphs: Critical factors influencing comprehension and instructional implications. Journal for Research in mathematics Education, 32(2):124–158, 2001.
[13] J. Fuchs, P. Isenberg, A. Bezerianos, F. Fischer, and E. Bertini. The influence of contour on similarity perception of star glyphs. IEEE Trans. Vis. Comput. Graphics, 20(12):2251–2260, 2014.
[14] X. Gao, B. Xiao, D. Tao, and X. Li. A survey of graph edit distance. Pattern Anal. Appl., 13(1):113–129, 2010.
[15] S. Ghani, N. Elmqvist, and J. S. Yi. Perception of animated node-link diagrams for dynamic graphs. Comput. Graph. Forum, 31(3pt3):1205–1214, 2012.
[16] M. Gleicher. Considerations for visualizing comparison. IEEE Transactions on Visualization and Computer Graphics, 24(1):413–423, 2018.
[17] M. Gleicher, D. Albers, R. Walker, I. Jusufi, C. D. Hansen, and J. C. Roberts.Visual comparison for information visualization.Inf. Vis., 10(4):289–309, 2011.
[18] G. Greve. Different or alike? Comparing computer-based and paper-based card sorting. International J. of Strategic Innovative Marketing, 1(1):27–36, 2014.
[19] S. Hadlak, H. Schumann, and H.-J. Schulz. A survey of multi-faceted graph visualization. In Proc. EuroVis - STARs, 2015.
[20] M. Hess, S. Bremm, S. Weissgraeber, K. Hamacher, M. Goesele, J. Wiemeyer, and T. von Landesberger. Visual exploration of parameter influence on phylogenetic trees. IEEE Computer Graphics and Applications, 34(2):48–56, 2014.
[21] D. Holten and J. J. Van Wijk. Visual comparison of hierarchically organized data. Comput. Graph. Forum, 27(3):759–766, 2008.
[22] D. Holten and J. J. van Wijk. A user study on visualizing directed edges in graphs. In Proc. CHI, pages 2299–2308, 2009.
[23] W. Huang, S.-H. Hong, and P. Eades. Layout effects on sociogram perception. In P. Healy and N. S. Nikolov, editors, Graph Drawing: 13th International Symposium, GD 2005, pages 262–273. Springer, 2006. · Zbl 1171.68624
[24] G. Jeh and J. Widom. SimRank: A measure of structural-context similarity. In Proc. KDD, pages 538–543, 2002.
[25] S. Kieffer, T. Dwyer, K. Marriott, and M. Wybrow. HOLA: Human-like orthogonal network layout. IEEE Trans. Vis. Comput. Graphics, 22(1):349– 358, 2016.
[26] J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46(5):604–632, 1999. · Zbl 1065.68660
[27] A. Klippel, F. Hardisty, and C. Weaver. Star plots: How shape characteristics influence classification tasks. Cartogr. Geogr. Inf. Sci., 36(2):149–163, 2009.
[28] S. G. Kobourov, S. Pupyrev, and B. Saket.Are crossings important for drawing large graphs?In C. Duncan and A. Symvonis, editors, Graph Drawing: 22nd International Symposium, GD 2014, pages 234–245. Springer, 2014. · Zbl 1426.68219
[29] C. K¨orner.Concepts and misconceptions in comprehension of hierarchical graphs.Learn. Instr., 15(4):281–296, 2005.
[30] R. l. Goldstone and J. Y. Son. Similarity. In K. J. Holyoak and R. G. Morrison, editors, The Cambridge Handbook of Thinking and Reasoning. Cambridge University Press, 2005.
[31] P. Lemaire and L. Fabre. Strategic aspects of human cognition: Implications for understanding human reasoning. In M. Roberts and E. Newton, editors, Methods of though: Individual differences in reasoning strategies, pages 11–56. Psychology Press, New York, 2005.
[32] O. Lenz, F. Keul, S. Bremm, K. Hamacher, and T. von Landesberger. Visual analysis of patterns in multiple amino acid mutation graphs. In Proc. IEEE VAST, pages 93–102, 2014.
[33] F. McGee and J. Dingliana. An empirical study on the impact of edge bundling on user comprehension of graphs. In Proc. AVI, pages 620–627, 2012.
[34] C. McGrath, J. Blythe, and D. Krackhardt.The effect of spatial arrangement on judgments and errors in interpreting graphs. Soc. Networks, 19(3):223–242, 1997.
[35] S. Melnik, H. Garcia-Molina, and E. Rahm. Similarity flooding: A versatile graph matching algorithm and its application to schema matching. In Proc. ICDE, pages 117–128, 2002.
[36] B. Mirel. Interaction Design for Complex Problem Solving: Developing Useful and Usable Software. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2004.
[37] B. J. Morris and C. D. Schunn. Rethinking logical reasoning skills from a strategy perspective. In E. Newton and M. Roberts, editors, Methods of thought. Individual differences in reasoning strategies, pages 2–38. Psychology Press, New York, 2005.
[38] A. Newell and H. A. Simon. Human Problem Solving. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972.
[39] L. R. Novick.The importance of both diagrammatic conventions and domain-specific knowledge for diagram literacy in science: The hierarchy as an illustrative case. In D. Barker-Plummer, R. Cox, and N. Swoboda, editors, Diagrammatic Representation and Inference, pages 1–11. Springer, 2006.
[40] A. V. Pandey, J. Krause, C. Felix, J. Boy, and E. Bertini. Towards understanding human similarity perception in the analysis of large sets of scatter plots. In Proc. CHI, pages 3659–3669, 2016.
[41] E. Pekalska and R. P. W. Duin. The dissimilarity representation for pattern recognition: Foundations and applications. World Scientific Publishing Co., Inc., River Edge, NJ, USA, 2005. · Zbl 1095.68105
[42] M. Pohl, G. Wallner, and S. Kriglstein. Using lag-sequential analysis for understanding interaction sequences in visualizations. International Journal of Human-Computer Studies, 96(Supplement C):54–66, 2016.
[43] H. Purchase. Which aesthetic has the greatest effect on human understanding?In G. DiBattista, editor, Graph Drawing: 5th International Symposium, GD 1997, pages 248–261. Springer, 1997.
[44] H. C. Purchase. Metrics for graph drawing aesthetics. Journal of Vis. Languages & Computing, 13(5):501–516, 2002.
[45] H. C. Purchase, E. Hoggan, and C. G¨org. How important is the “mental map”?– an empirical investigation of a dynamic graph layout algorithm.In M. Kaufmann and D. Wagner, editors, Graph Drawing: 14th International Symposium, GD 2006, pages 184–195. Springer, 2007. · Zbl 1185.68494
[46] H. C. Purchase, M. McGill, L. Colpoys, and D. Carrington. Graph drawing aesthetics and the comprehension of UML class diagrams: An empirical study. In Proceedings of the 2001 Asia-Pacific Symposium on Information Visualisation, pages 129–137, 2001.
[47] H. C. Purchase, C. Pilcher, and B. Plimmer. Graph drawing aesthetics – created by users, not algorithms. IEEE Trans. Vis. Comput. Graphics, 18(1):81–92, 2012.
[48] J. Salda˜na. The Coding Manual for Qualitative Researchers. SAGE Publications, 2 edition, 2012.
[49] M. Schreier. Qualitative Content Analysis in Practice. SAGE Publications, 2012.
[50] K. Sedig, P. Parsons, H.-N. Liang, and J. Morey.Supporting sensemaking of complex objects with visualizations: Visibility and complementarity of interactions.Informatics, 3(4):20, 2016.
[51] M. Tennekes and E. de Jonge. Tree colors: color schemes for tree-structured data. IEEE Trans. Vis. Comput. Graphics, 20(12):2072–2081, 2014.
[52] S. Thornley, R. Marshall, S. Wells, and R. Jackson. Using directed acyclic graphs for investigating causal paths for cardiovascular disease. J. Biometrics Biostatistics, 4:182, 2013.
[53] R. Tibshirani, G. Walther, and T. Hastie. Estimating the number of clusters in a data set via the gap statistic. J. R. Stat. Soc. Series B. Stat. Methodol., 63(2):411–423, 2001. · Zbl 0979.62046
[54] C. Tominski, C. Forsell, and J. Johansson.Interaction support for visual comparison inspired by natural behavior. IEEE Trans. Vis. Comput. Graphics, 18(12):2719–2728, 2012.
[55] S. B. Trickett and J. G. Trafton. Toward a comprehensive model of graph comprehension: Making the case for spatial cognition.In D. BarkerPlummer, R. Cox, and N. Swoboda, editors, Diagrammatic Representation and Inference, pages 286–300. Springer Berlin Heidelberg, 2006.
[56] C. Vehlow, F. Beck, and D. Weiskopf. The state of the art in visualizing group structures in graphs. In Proc. EuroVis - STARs, 2015.
[57] T. von Landesberger, S. Diel, S. Bremm, and D. W. Fellner. Visual analysis of contagion in networks. Inf. Vis., 14(2):93–110, 2015.
[58] T. von Landesberger, A. Kuijper, T. Schreck, J. Kohlhammer, J. van Wijk, J.-D. Fekete, and D. Fellner. Visual analysis of large graphs: State-of-theart and future research challenges. Comput. Graph. Forum, 30(6):1719– 1749, 2011.
[59] T. von Landesberger, M. Pohl, G. Wallner, M. Distler, and K. Ballweg. Investigating graph similarity perception: A preliminary study and methodological challenges. In Proc. VISIGRAPP, pages 241–250, 2017.
[60] E. Welch and S. Kobourov. Measuring symmetry in drawings of graphs. Comput. Graph. Forum, 36(3):341–351, 2017.
[61] J. R. Wood and L. E. Wood. Card sorting: Current practices and beyond. J. Usability Stud., 4(1):1–6, 2008.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.