Topology-aware navigation in large networks

ABSTRACT

Applications supporting navigation in large networks are used every days by millions of people. They include road map navigators, flight route visualization systems, and network visualization systems using node-link diagrams. These applications currently provide generic interaction methods for navigation: pan-and-zoom and sometimes bird's eye views.

This article explores the idea of exploiting the connection information provided by the network to help navigate these large spaces. We visually augment two traditional navigation methods, and develop two special-purpose techniques. The first new technique, called "Link Sliding", provides guided panning when continuously dragging along a visible link. The second technique, called "Bring & Go", brings adjacent nodes nearby when pointing to a node. We compare the performance of these techniques in both an adjacency exploration task and a node revisiting task. This comparison illustrates the various advantages of content-aware network navigation techniques. A significant speed advantage is found for the Bring & Go technique over other methods.

REFERENCES

• 1: Eytan Adar, GUESS: a language and interface for graph exploration, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124889]
• 2: A. L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 3: P. Baudisch, E. Cutrell, D. Robbins, M. Czerwinski, P. Tandler, B. Bederson, and A. Zierlinger. Drag-and-pop and drag-and-pick: Techniques for accessing remote screen content on touch and pen-operated systems. In Proc. Interact '03, 57--64, 2003.
• 4: Benjamin B. Bederson , Jesse Grosjean , Jon Meyer, Toolkit Design for Interactive Structured Graphics, IEEE Transactions on Software Engineering, v.30 n.8, p.535-546, August 2004 [doi>10.1109/TSE.2004.44]
• 5: Anastasia Bezerianos , Ravin Balakrishnan, The vacuum: facilitating the manipulation of distant objects, Proceedings of the SIGCHI conference on Human factors in computing systems, April 02-07, 2005, Portland, Oregon, USA [doi>10.1145/1054972.1055023]
• 6: Delta Air Lines. Delta air lines route map, 2008. http://delta.innosked.com/.
• 7: Niklas Elmqvist , Nathalie Henry , Yann Riche , Jean-Daniel Fekete, Melange: space folding for multi-focus interaction, Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, April 05-10, 2008, Florence, Italy [doi>10.1145/1357054.1357263]
• 8: G. W. Furnas, Generalized fisheye views, ACM SIGCHI Bulletin, v.17 n.4, p.16-23, April 1986
• 9: Emden R. Gansner , Yehuda Koren , Stephen C. North, Topological Fisheye Views for Visualizing Large Graphs, IEEE Transactions on Visualization and Computer Graphics, v.11 n.4, p.457-468, July 2005 [doi>10.1109/TVCG.2005.66]
• 10: Google. Google maps, 2008. http://maps.google.com.
• 11: Y. Guiard, F. Bourgeois, D. Mottet, and M. Beaudouin-Lafon. Beyond the 10-bit barrier: Fitts' law in multiscale electronic worlds. In HCI '01, 573--588. Springer, 2001.
• 12: Sean Gustafson , Patrick Baudisch , Carl Gutwin , Pourang Irani, Wedge: clutter-free visualization of off-screen locations, Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, April 05-10, 2008, Florence, Italy [doi>10.1145/1357054.1357179]
• 13: Jeffrey Heer , Stuart K. Card , James A. Landay, prefuse: a toolkit for interactive information visualization, Proceedings of the SIGCHI conference on Human factors in computing systems, April 02-07, 2005, Portland, Oregon, USA [doi>10.1145/1054972.1055031]
• 14: Ivan Herman , Guy Melançon , M. Scott Marshall, Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.24-43, January 2000 [doi>10.1109/2945.841119]
• 15: Danny Holten, Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.741-748, September 2006 [doi>10.1109/TVCG.2006.147]
• 16: Kasper Hornbæk , Benjamin B. Bederson , Catherine Plaisant, Navigation patterns and usability of zoomable user interfaces with and without an overview, ACM Transactions on Computer-Human Interaction (TOCHI), v.9 n.4, p.362-389, December 2002 [doi>10.1145/586081.586086]
• 17: Takeo Igarashi , Ken Hinckley, Speed-dependent automatic zooming for browsing large documents, Proceedings of the 13th annual ACM symposium on User interface software and technology, p.139-148, November 06-08, 2000, San Diego, California, United States [doi>10.1145/354401.354435]
• 18: Pourang Irani , Carl Gutwin , Xing Dong Yang, Improving selection of off-screen targets with hopping, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124818]
• 19: Edward W. Ishak , Steven K. Feiner, Content-aware scrolling, Proceedings of the 19th annual ACM symposium on User interface software and technology, October 15-18, 2006, Montreux, Switzerland [doi>10.1145/1166253.1166277]
• 20: Victor Kaptelinin, A comparison of four navigation techniques in a 2D browsing task, Conference companion on Human factors in computing systems, p.282-283, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223355.223675]
• 21: Heidi Lam , Ronald A. Rensink , Tamara Munzner, Effects of 2D geometric transformations on visual memory, Proceedings of the 3rd symposium on Applied perception in graphics and visualization, July 28-29, 2006, Boston, Massachusetts [doi>10.1145/1140491.1140515]
• 22: Bongshin Lee , Catherine Plaisant , Cynthia Sims Parr , Jean-Daniel Fekete , Nathalie Henry, Task taxonomy for graph visualization, Proceedings of the 2006 AVI workshop on BEyond time and errors: novel evaluation methods for information visualization, May 23-23, 2006, Venice, Italy [doi>10.1145/1168149.1168168]
• 23: Y. K. Leung , M. D. Apperley, A review and taxonomy of distortion-oriented presentation techniques, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.2, p.126-160, June 1994 [doi>10.1145/180171.180173]
• 24: Ken Perlin , David Fox, Pad: an alternative approach to the computer interface, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.57-64, August 02-06, 1993, Anaheim, CA [doi>10.1145/166117.166125]
• 25: Emmanuel Pietriga, A Toolkit for Addressing HCI Issues in Visual Language Environments, Proceedings of the 2005 IEEE Symposium on Visual Languages and Human-Centric Computing, p.145-152, September 20-24, 2005 [doi>10.1109/VLHCC.2005.11]
• 26: Emmanuel Pietriga , Caroline Appert, Sigma lenses: focus-context transitions combining space, time and translucence, Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, April 05-10, 2008, Florence, Italy [doi>10.1145/1357054.1357264]
• 27: Emmanuel Pietriga , Caroline Appert , Michel Beaudouin-Lafon, Pointing and beyond: an operationalization and preliminary evaluation of multi-scale searching, Proceedings of the SIGCHI conference on Human factors in computing systems, April 28-May 03, 2007, San Jose, California, USA [doi>10.1145/1240624.1240808]
• 28: Catherine Plaisant , Jesse Grosjean , Benjamin B. Bederson, SpaceTree: Supporting Exploration in Large Node Link Tree, Design Evolution and Empirical Evaluation, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.57, October 28-29, 2002
• 29: George G. Robertson , Stuart K. Card , Jack D. Mackinlay, Information visualization using 3D interactive animation, Communications of the ACM, v.36 n.4, p.57-71, April 1993 [doi>10.1145/255950.153577]
• 30: Manojit Sarkar , Scott S. Snibbe , Oren J. Tversky , Steven P. Reiss, Stretching the rubber sheet: a metaphor for viewing large layouts on small screens, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.81-91, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168650]
• 31: Christian Tominski , James Abello , Frank van Ham , Heidrun Schumann, Fisheye Tree Views and Lenses for Graph Visualization, Proceedings of the conference on Information Visualization, p.17-24, July 05-07, 2006 [doi>10.1109/IV.2006.54]
• 32: J. J. van Wijk and W. A. Nuij. A model for smooth viewing and navigation of large 2d information spaces. IEEE Trans. on Visualization and Computer Graphics, 10(4):447--458, 2004.
• 33: N. Wong, S. Carpendale, and S. Greenberg. Edgelens: An interactive method for managing edge congestion in graphs. In InfoVis'03, 51--58. IEEE Computer Society, 2003.
• 34: Ka-Ping Yee , Danyel Fisher , Rachna Dhamija , Marti Hearst, Animated Exploration of Dynamic Graphs with Radial Layout, Proceedings of the IEEE Symposium on Information Visualization 2001 (INFOVIS'01), p.43, October 22-23, 2001
• 35: Shumin Zhai, User performance in relation to 3D input device design, ACM SIGGRAPH Computer Graphics, v.32 n.4, p.50-54, Nov. 1998 [doi>10.1145/307710.307728]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems

General Terms:
Design, Human Factors

Keywords:
content-aware, document navigation, graph visualization, interaction techniques