Generating Graphs for Visual Analytics through Interactive Sketching
|
Abstract—We introduce an interactive graph generator, GreenSketch, designed to facilitate the creation of descriptive graphs required for different visual analytics tasks. The human-centric design approach of GreenSketch enables users to master the creation process without specific training or prior knowledge of graph model theory. The customized user interface encourages users to gain insight into the connection between the compact matrix representation and the topology of a graph layout when they sketch their graphs. Both the human-enforced and machine-generated randomnesses supported by GreenSketch provide the flexibility needed to address the uncertainty factor in many analytical tasks. This paper describes more than two dozen examples that cover a wide variety of graph creations from a single line of nodes to a real-life small-world network that describes a snapshot of telephone connections. While the discussion focuses mainly on the design of GreenSketch, we include a case study that applies the technology in a visual analytics environment and a usability study that evaluates the strengths and weaknesses of our design approach.
[1] 1386 W. Aiello, F. Chung, and L. Lu, “A Random Graph Model for Power Law Graphs,” Experimental Math., vol. 10, pp. 53-66, 2001.
[2] R. Albert and A.-L. Barabasi, “Topology of Evolving Networks: Local Events and Universality,” Physical Rev. Letters, vol. 85, no. 24, pp. 5234-5237, The Am. Physical Soc., 2000.
[3] C. Bailey-Kellogg, S. Chainraj, and G. Pandurangan, “A Random Graph Approach to NMR Sequential Assignment,” Proc. Eighth Ann. Int'l Conf. Computational Molecular Biology, pp. 58-67, 2004.
[4] B. Bela, Random Graphs, second ed. Cambridge Univ. Press, 2001.
[5] H. Blau, N. Immerman, and D. Jensen, “A Visual Language for Querying and Updating Graphs,” Technical Report, 2002-037, Univ. of Mass. Amherst Computer Science, 2002.
[6] K.L. Calvert, M.B. Doar, and E.W. Zegura, “Modeling Internet Topology,” IEEE Comm. Magazine, vol. 35, no. 6, 1997.
[7] W.S. Cleveland, Visualizing Data. Hobart Press, 1993.
[8] M. Consens and A. Mendelzon, “GraphLog: A Visual Formalism for Real Life Recursion,” Proc. ACM Symp. Principles on Database Systems (PODS), pp. 404-416, 1990.
[9] T.F. Cox and M.A.A. Cox, Multidimensional Scaling, second ed. Chapman & Hall/CRC, 2001.
[10] C.J. Date and H. Darwen, A Guide to the SQL Standard. Addison-Wesley, 1997.
[11] G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
[12] F.C. Eigler, “Translating GraphLog to SQL,” Proc. 1994 Conf. Centre for Advanced Studies on Collaborative Research, 1994.
[13] M. Faloutsos, P. Faloutsos, and C. Faloutsos, “On Power-Law Relationships of the Internet Topology,” Proc. ACM SIGCOMM, pp. 251-262, Sept. 1999.
[14] GD96 Contest, 2006, http://www.research.att.com/conf/gd96contest.html .
[15] M. Ghoniem, J.-D. Fekete, and P. Castagliola, “A Comparison of the Readability of Graphs Using Node-Link and Matrix-Based Representations,” Proc. IEEE Symp. Information Visualization, pp.17-24, Oct. 2004.
[16] T. Kamada and S. Kawai, “An Algorithm for Drawing General Undirected Graphs,” Information Processing Letters, vol. 31, no. 1, pp. 7-15, Apr. 1989.
[17] S. Milgram, “The Small World Problem,” Psychology Today, vol. 2, pp. 60-67, 1967.
[18] M.E.J. Newman, “Clustering and Preferential Attachment in Growing Networks,” Technical Report, Santa Fe Inst., Santa Fe, NM, 2006, http://www.santafe.edu/sfi/publications/ Working-Papers01-03-021.pdf.
[19] M.E.J. Newman, “Random Graphs as Models of Networks,” Handbook of Graphs and Networks, S. Bornholdt and H.G. Schuster, eds. Berlin: Wiley-VCH, 2002.
[20] M.E.J. Newman, D.J. Watts, and S.H. Strogatz, “Random Graph Models of Social Network,” Proc. Nat'l Academy of Sciences of the US, vol. 99, 2002.
[21] QGraph, http://kdl.cs.umass.edu/proximity/documentation qgraph/, 2006.
[22] O. Sheyner, S. Jha, J. Haines, R. Lippmann, and J.M. Wing, “Automated Generation and Analysis of Attack Graphs,” Proc. IEEE Symp. Security and Privacy, May 2002.
[23] B. Shneiderman, Leonardo's Laptop: Human Needs and the New Computing Technologies. MIT Press, 2002.
[24] H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, “Network Topologies, Power Laws, and Hierarchy,” Proc. ACM SIGCOMM Computer Comm. Rev., vol. 32, no. 1, Jan. 2002.
[25] Illuminating the Path: the Research and Development Agenda for Visual Analytics, J.J. Thomas and K.A. Cook, eds. CS Press, 2005.
[26] F. van Ham, “Using Multilevel Call Matrices in Large Software Projects,” Proc. IEEE Symp. Information Visualization, pp. 227-232, 2003.
[27] D.J. Watts and S.H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, pp. 440-442, Macmillan, 1998.
[28] D.J. Watts, Six Degrees: The Science of a Connected Age. W.W. Norton & Company, 2003.
[29] B.M. Waxman, “Routing of Multipoint Connections,” IEEE J.Selected Areas in Comm., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.
[30] P.C. Wong, H. Foote, G. Chin Jr., P. Mackey, and K. Perrine, “Graph Signatures for Visual Analytics,” IEEE Trans. Visualization and Computer Graphics, vol. 12, no. 6, 2006.
[31] M.-Y. Wu and W. Shu, “On Parallelization of Static Scheduling Algorithms,” IEEE Trans. Software Eng., vol. 23, no. 8, Aug. 1997.
[32] E.W. Zegura, K.L. Calvert, and S. Bhattcharjee, “How to Model an Internetwork,” Proc. IEEE INFOCOM, pp. 594-602, Mar. 1996.
Index Terms:
Data and knowledge visualization, information visualization, visualization techniques and methodologies, graphs and networks.
Citation:
Pak Chung Wong, Harlan Foote, Patrick Mackey, Ken Perrine, George Chin Jr., "Generating Graphs for Visual Analytics through Interactive Sketching," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 6, pp. 1386-1398, Nov./Dec. 2006, doi:10.1109/TVCG.2006.91
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb