A framework for visual data mining of structures

ABSTRACT

Visual data mining has been established to effectively analyze large, complex numerical data sets. Especially, the extraction and visualization of inherent structures such as hierarchies and networks has made a signi ffcant leap forward. However, it is still a challenging task for users to explore explicitly given large structures. In this paper, we approach this task by tightly coupling visualization and graph-theoretical methods. Therefore, we investigate if and how visualization can benefft from common graph-theoretical methods - mainly developed for the investigation of social networks - and vice versa. To accomplish this close integration, we introduce a design of a general framework for visual data mining of complex structures. Especially, this design includes an appropriate processing order of different mining and visualization algorithms and their mining results. Furthermore, we discuss some important implementation details of our framework to ensure fast structure processing. Finally, we examine the applicability of the framework for a large real-world data set.

REFERENCES

• 1: James Abello , Jeffrey Korn , Irene Finocchi, Graph Sketches, Proceedings of the IEEE Symposium on Information Visualization 2001 (INFOVIS'01), p.67, October 22-23, 2001
• 2: James Abello , Frank van Ham, Matrix Zoom: A Visual Interface to Semi-External Graphs, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.183-190, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.46]
• 3: Christopher Ahlberg, Spotfire: an information exploration environment, ACM SIGMOD Record, v.25 n.4, p.25-29, Dec. 1996 [doi>10.1145/245882.245893]
• 4: Ankerst, M. (2001), Visual Data Mining with Pixel-oriented Visualization Techniques, in 'Proceedings of ACM SIGKDD Workshop on Visual Data Mining'01; San Francisco'.
• 5: Vladimir Batagelj , Andrej Mrvar , Matjaz Zaversnik, Partitioning Approach to Visualization of Large Graphs, Proceedings of the 7th International Symposium on Graph Drawing, p.90-97, September 01, 1999
• 6: Bertin, J. (1981), Graphics and Graphic Information-Processing , Walter de Gruyter.
• 7: Brandes, U. (2001), 'A Faster Algorithm for Betweenness Centrality', Journal of Mathematical Sociology pp. 163-177.
• 8: Ulrik Brandes , Steven R. Corman, Visual Unrolling of Network Evolution and the Analysis of Dynamic Discourse, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.145, October 28-29, 2002
• 9: Brandes, U. & Wagner, D. (2003), visone - Analysis and Visualization of Social Networks, in 'Graph Drawing Software', Springer, pp. 321-340.
• 10: Bunke, H. (2000), Graph matching: Theoretical foundations, algorithms, and applications, in 'Proc. Vision Interface 2000, Montreal', pp. 82-88.
• 11: Jubin Edachery , Arunabha Sen , Franz-Josef Brandenburg, Graph Clustering Using Distance-k Cliques, Proceedings of the 7th International Symposium on Graph Drawing, p.98-106, September 01, 1999
• 12: Fekete, J.-D., Wang, D., Dang, N., Aris, A. & Plaisant, C. (2003), Interactive Poster: Overlaying Graph Links on Treemaps, in 'IEEE Symposium on Information Visualization (InfoVis'03), Seattle'.
• 13: Jean-Daniel Fekete, The InfoVis Toolkit, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.167-174, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.64]
• 14: Yaniv Frishman , Ayellet Tal, Dynamic Drawing of Clustered Graphs, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.191-198, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.18]
• 15: Thomas M. J. Fruchterman , Edward M. Reingold, Graph drawing by force-directed placement, Software—Practice & Experience, v.21 n.11, p.1129-1164, Nov. 1991 [doi>10.1002/spe.4380211102]
• 16: Emden Gansner , Yehuda Koren , Stephen North, Topological Fisheye Views for Visualizing Large Graphs, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.175-182, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.66]
• 17: Girvan, M. & Newman, M. (2002), 'Community structure in social and biological networks', PNAS 99(12), 7821-7826.
• 18: Michael Granitzer , Wolfgang Kienreich , Vedran Sabol , Keith Andrews , Werner Klieber, Evaluating a System for Interactive Exploration of Large, Hierarchically Structured Document Repositories, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.127-134, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.19]
• 19: 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]
• 20: M. S Marshall , Ivan Herman , Guy Melancon, Automatic generation of interactive overview diagrams for the navigation of large graphs, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2000
• 21: Kiss G., Armstrong, C., Milroy, R. & Piper, J. (1973), An associative thesaurus of English and its computer analysis, in 'The Computer and Literary Studies', Edinburgh University Press.
• 22: M. Kreuseler , T. Nocke , H. Schumann, A History Mechanism for Visual Data Mining, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.49-56, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.2]
• 23: Matthias Kreuseler , Heidrun Schumann, A Flexible Approach for Visual Data Mining, IEEE Transactions on Visualization and Computer Graphics, v.8 n.1, p.39-51, January 2002 [doi>10.1109/2945.981850 ]
• 24: John Lamping , Ramana Rao , Peter Pirolli, A focus+context technique based on hyperbolic geometry for visualizing large hierarchies, Proceedings of the SIGCHI conference on Human factors in computing systems, p.401-408, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223956]
• 25: Nocke, T. & Schumann, H. (2004), Goals of Analysis for Visualization and Visual Data Mining Tasks, in 'CODATA Workshop Information, Presentation and Design (March 2004), Prague'.
• 26: George G. Robertson , Jock D. Mackinlay , Stuart K. Card, Cone Trees: animated 3D visualizations of hierarchical information, Proceedings of the SIGCHI conference on Human factors in computing systems: Reaching through technology, p.189-194, April 27-May 02, 1991, New Orleans, Louisiana, United States [doi>10.1145/108844.108883]
• 27: S. F. Roth , P. Lucas , J. A. Senn , C. C. Gomberg , M. B. Burks , P. J. Stroffolino , A. J. Kolojechick , C. Dunmire, Visage: a user interface environment for exploring information, Proceedings of the 1996 IEEE Symposium on Information Visualization (INFOVIS '96), p.3, October 28-29, 1996
• 28: Scharl, A. (2002), Adaptive Web Representation, in 'Human Computer Interaction Development & Management', pp. 255-260.
• 29: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.731, June 17-19, 1997
• 30: Ben Shneiderman, Tree visualization with tree-maps: 2-d space-filling approach, ACM Transactions on Graphics (TOG), v.11 n.1, p.92-99, Jan. 1992 [doi>10.1145/102377.115768]
• 31: Chris Stolte , Diane Tang , Pat Hanrahan, Polaris: A System for Query, Analysis, and Visualization of Multidimensional Relational Databases, IEEE Transactions on Visualization and Computer Graphics, v.8 n.1, p.52-65, January 2002 [doi>10.1109/2945.981851 ]
• 32: Tollis, I., Eades, P. & di Battista, G. (1999), Graph Drawing - Algorithms for the Visualization of Graphs, Prentice Hall.
• 33: Gabriel Valiente, Algorithms on Trees and Graphs, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 34: Frank van Ham , Jarke J. van Wijk, Interactive Visualization of Small World Graphs, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.199-206, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.43]
• 35: Voigt, D. (2001), WWW-based Representation of complex Information Structures (in German: WWW-basierte Darstellung komplexer Informationsstrukturen), Master's thesis, University of Rostock, Department of Computer Science.
• 36: Zhang, P. (1994), Method of Mapping DNA Fragments , United States Patent No. 5667970.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces

  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)

General Terms:
Algorithms, Design, Theory