Graph Signatures for Visual Analytics
|
Abstract—We present a visual analytics technique to explore graphs using the concept of a data signature. A data signature, in our context, is a multidimensional vector that captures the local topology information surrounding each graph node. Signature vectors extracted from a graph are projected onto a low-dimensional scatterplot through the use of scaling. The resultant scatterplot, which reflects the similarities of the vectors, allows analysts to examine the graph structures and their corresponding real-life interpretations through repeated use of brushing and linking between the two visualizations. The interpretation of the graph structures is based on the outcomes of multiple participatory analysis sessions with intelligence analysts conducted by the authors at the Pacific Northwest National Laboratory. The paper first uses three public domain data sets with either well-known or obvious features to explain the rationale of our design and illustrate its results. More advanced examples are then used in a customized usability study to evaluate the effectiveness and efficiency of our approach. The study results reveal not only the limitations and weaknesses of the traditional approach based solely on graph visualization, but also the advantages and strengths of our signature-guided approach presented in the paper.
[1] 1399 S.K. Card, J.D. Mackinlay, and B. Shneiderman, Readings in Information Visualization, Using Vision to Think. Morgan Kaufmann, 1999.
[2] C. Chen, Information Visualization beyond the Horizon, second ed. Springer, 2004.
[3] C. Chen and S. Morris, “Visualizing Evolving Networks: Minimum Spanning Trees versus Pathfinder Networks,” Proc. IEEE Symp. Information Visualization 2003, pp. 67-74, Oct. 2003.
[4] Y. Chiricota, F. Jourdan, and G. Melancon, “Metric-Based Network Exploration and Multiscale Scatterplot,” Proc. IEEE Symp. Information Visualization 2004, pp. 135-142, Oct. 2004.
[5] W.S. Cleveland, Visualizing Data. Hobart Press, 1993.
[6] T.F. Cox and M.A.A. Cox, Multidimensional Scaling, second ed. Chapman and Hall/CRC, 2001.
[7] G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
[8] M.R. Garey and D.S. Johnson, Computer and Intractability. A Guide to the Theory of NP-Completeness. WH Freeman and Company, 1979.
[9] GD2006 Graph Drawing, http:/www.gd2006.org, 2006.
[10] GD03 Graph Drawing Contest, http://www.infosun.fmi.uni-passau.de/br/ lehrstuhl/GraphDrawing/GD2003contest.html , 2006.
[11] GD96 Graph Drawing Contest, http://www.research.att.com/conf/gd96contest.html , 2006.
[12] Graphviz, http://www.research.att.com/sw/toolsgraphviz /, 2006.
[13] I. Herman, G. Melancon, and M.S. Marshall, “Graph Visualization and Navigation in Information Visualization: A Survey,” IEEE Trans. Visualization and Computer Graphics, vol. 6, no. 1, pp. 24-43, 2000.
[14] Proc. InfoVis 2006, IEEE Symp. Information Visualization 2006, http://www.infovis.org/infovis2006, 2006.
[15] JUNG—Java Universal Network/Graph Framework, http://jung.sourceforge.netfaq.html, 2006.
[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] J.B. Kruskal, “Nonmetric Multidimensional Scaling: A Numerical Method,” Psychometrika, vol. 29, no. 2, pp. 115-129, Mar. 1964.
[18] V. Loeb, “Clan, Family Ties Called Key to Army's Capture of Hussein: ‘Link Diagrams’ Showed Everyone Related by Blood or Tribe,” Washington Post, p. A27, Dec. 2003.
[19] S. Milgram, “The Small World Problem,” Psychology Today, vol. 2, pp. 60-67, 1967.
[20] Q.V. Nguyen and M.L. Huang, “A Space-Optimized Tree Visualization,” Proc. IEEE Symp. Information Visualization 2002, pp. 85-92, Oct. 2002.
[21] Pajek, http://vlado.fmf.uni-lj.si/pub/networkspajek /, 2006.
[22] G.A.F. Seber, Multivariate Observations. John Wiley and Sons, 1984.
[23] M. Sink, “An Electronic Cop that Plays Hunches,” New York Times, p. B9, Nov. 2002.
[24] M. Sparrow, “The Application of Network Analysis to Criminal Intelligence: An Assessment of the Prospects,” Social Networks, vol. 13, pp. 251-274, 1991.
[25] Subdue Knowledge Discovery System, http://cygnus.uta.edusubdue, 2006.
[26] K. Sugiyama, Graph Drawing and Applications. World Scientific Publishing, 2002.
[27] Tulip, http:/tulip-software.org/, 2006.
[28] F. van Ham and J.J. van Wijk, “Beamtrees: Compact Visualization of Large Hierarchies,” Proc. IEEE Symp. Information Visualization 2003, pp. 93-100, Oct. 2003.
[29] F. van Ham and J.J. van Wijk, “Interactive Visualization of Small World Graphs,” Proc. IEEE Symp. Information Visualization 2004, pp. 199-206, Oct. 2004.
[30] C. Walshaw, “A Multilevel Algorithm for Force-Directed Graph Drawing,” J. Graph Algorithm and Applications, vol. 7, no. 3, pp. 253-285, 2003.
[31] S. Wasserman and K. Faust, Social Network Analysis-Methods and Applications. Cambridge Univ. Press, 1999.
[32] D.J. Watts, Small Worlds. Princeton Univ. Press, 1999.
[33] D.J. Watts, Six Degrees: The Science of a Connected Age. W.W. Norton and Company, 2003.
[34] D.J. Watts and S.H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, pp. 440-442, June 1998.
[35] D.B. West, Introduction to Graph Theory, second ed. Prentice Hall, 2000.
[36] N. Wong, S. Carpendale, and S. GreenBerg, “EdgeLens: An Interactive Method for Managing Edge Congestion in Graphs,” Proc. IEEE Symp. Information Visualization, pp. 51-59, Oct. 2003.
[37] P.C. Wong, H. Foote, R. Leung, D. Adams, and J. Thomas, “Data Signatures and Visualization of Very Large Data Sets,” IEEE Computer Graphics and Applications, vol. 20, no. 2, Mar. 2000.
[38] P.C. Wong, H. Foote, P. Mackey, K. Perrine, and G. Chin Jr., “Generating Graphs for Visual Analytics through Interactive Sketching,” IEEE Trans. Visualization and Computer Graphics, vol. 12, no. 6, Nov./Dec. 2006.
Index Terms:
Data and knowledge visualization, information visualization, visualization techniques and methodologies, graphs and networks.
Citation:
Pak Chung Wong, Harlan Foote, George Chin Jr., Patrick Mackey, Ken Perrine, "Graph Signatures for Visual Analytics," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 6, pp. 1399-1413, Nov./Dec. 2006, doi:10.1109/TVCG.2006.92
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb