Pierre-Yves Koenig
ABSTRACT
Searching for patterns in graphs and visualizing the search results is an active area of research with numerous applications. With the continual growth of database size, querying these databases often results in multiple solutions. Text-based systems present search results as a list, and going over all solutions can be tedious. In this paper, we present an interactive visualization system that helps users find patterns in graphs and visualizes the search results. The user draws a source pattern and labels it with attributes. Based on these attributes and connectivity constraints, simplified subgraphs are generated, containing all the possible solutions. The system is quite generic and capable of searching patterns and approximate solutions in a variety of data sets.
- D. Auber. Tulip - a huge graph visualization framework. In P. Mutzel and M. Jnger, editors, Graph Drawing Software, Mathematics and Visualization Series. Springer Verlag, 2003.Google Scholar
- M. Baur and U. Brandes. Multi-circular layout of micro/macro graphs. In S.-H. Hong, T. Nishizeki, and W. Quan, editors, Graph Drawing, volume 4875 of Lecture Notes in Computer Science, pages 255--267. Springer, 2007. Google ScholarDigital Library
- F. J. Brandenburg, U. Brandes, P. Eades, and J. Marks. Graph drawing contest report. In Proc. of Graph Drawing (GD '03), volume 2912 of LNCS, pages 504--508, 2003.Google Scholar
- D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. Int. J. Patt. Recog. and A. I., Volume: 18, Issue: 3:265--298, 2004.Google Scholar
- S. A. Cook. The complexity of theorem-proving procedures. In Proc. of the 3rd Annual ACM Symp. on Th. of Comp., pages 151--158, 1971. Google ScholarDigital Library
- T. Dwyer, K. Marriott, and P. J. Stuckey. Fast node overlap removal. In Proc. Graph Drawing (GD'05), volume 3843 of LNCS, pages 153--164. Springer-Verlag, 2005. Google ScholarDigital Library
- E. C. Freuder. Backtrack-free and backtrack-bounded search. Search in Artificial Intelligence, pages 343--369, 1988. Google ScholarDigital Library
- X. Gao, B. Xiao, D. Tao, and X. Li. A survey of graph edit distance. volume Volume 13, Number 1, pages 113--129, 2009. Google ScholarDigital Library
- G. Grinstein, C. Plaisant, J. Scholtz, and M. Whiting. The 2009 VAST challenge. In IEEE Proc. on Visual Analytics Science and Technology, 2009.Google Scholar
- P. Holleis, T. Zimmermann, and D. Gmach. Drawing graphs within graphs: A contribution to the graph drawing contest 2003. Journal of Graph Algorithms and Applications, 9(1):7--18, 2005.Google ScholarCross Ref
- H. Jeong, B. Tomber, R. Albert, Z. Oltvai, and A.-L. Barabási. Large-scale organization of metabolic networks. Nature, 407:651--654, 2000.Google ScholarCross Ref
- C. Klukas, D. Koschützki, and F. Schreiber. Graph pattern analysis with PatternGravisto. J. of Graph Algo. and App., 9(1):19--29, 2005.Google ScholarCross Ref
- R. Kosara, T. J. Jankun-Kelly, and E. Chlan, editors. IEEE InfoVis 2007 Contest: InfoVis goes to the movies, 2007. www.apl.jhu.edu/Misc/Visualization/index.html (visited 04/03/2010).Google Scholar
- V. Kumar. Algorithms for constraint-satisfaction problems: A survey. Artificial Intelligence Magazine, 13(1):32--44, Spring 1992. Google ScholarDigital Library
- J. Larrosa and G. Valiente. Constraint satisfaction algorithms for graph pattern matching. Math. Struct. in Comp. Sci., 12(4):403--422, 2002. Google ScholarDigital Library
- W.-S. Li, K. S. Candan, K. Hirata, and Y. Hara. IFQ: A visual query interface for object-based image retrieval. In CHI '97: Extended abstracts on Human Factors in Computing Systems, pages 32--33, New York, NY, USA, 1997. ACM. Google ScholarDigital Library
- Y. Lin, G. Rawlins, and M. Vanheyningen. Pic1: A visual database interface. volume 8, pages 237--245, 1995.Google Scholar
- A. K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99--118, 1977.Google ScholarDigital Library
- A. Madurapperuma, W. Gray, and N. Fiddian. A visual query interface for a customisable schema visualisation system. Database Engineering and Applications Symposium, International, 0:23, 1997. Google ScholarDigital Library
- A. P. Madurapperuma, W. A. Gray, and N. J. Fiddian. Customisable visual query interface to a heterogeneous database environment: A meta-programming based approach (abstract). In BNCOD 15: Proceedings of the 15th British National Conferenc on Databases, pages 129--130, London, UK, 1997. Springer-Verlag. Google ScholarDigital Library
- M. M. North and S. M. North. An information exploration and visualization approach for direct manipulation of databases. In VCHCI '93: Proceedings of the Vienna Conference on Human Computer Interaction, pages 417--418, London, UK, 1993. Springer-Verlag. Google ScholarDigital Library
- J. F. Rodrigues, H. Tong, A. J. M. Traina, C. Faloutsos, and J. Leskovec. GMine: A system for scalable, interactive graph visualization and mining. In VLDB'2006: Proceedings of the 32nd International Conference on Very Large Data Bases, pages 1195--1198. VLDB Endowment, 2006. Google ScholarDigital Library
- C. Rozenblat, G. Melançon, and P.-Y. Koenig. Continental integration in multilevel approach of world air transportation (2000--2004). Networks and Spatial Economics, 2008.Google Scholar
- M. Rudolf. Utilizing constraint satisfaction techniques for efficient graph pattern matching. In Selected papers from the 6th International Workshop on Th. and App. of Graph Transformations, pages 238--251, London, UK, 2000. Springer-Verlag. Google ScholarDigital Library
- L. G. Shapiro and R. M. Haralick. Structural descriptions and inexact matching. IEEE Trans. on Pattern Analysis and Matching Intelligence, PAMI-3(5):504--519, 1981.Google ScholarDigital Library
- S. C. Shapiro. Encyclopedia of Artificial Intelligence. John Wiley & Sons, Inc., New York, NY, USA, 1992. Google ScholarDigital Library
- S. J. Simoff, M. H. Böhlen, and A. Mazeika, editors. Visual Data Mining - Theory, Techniques and Tools for Visual Analytics, volume 4404 of LNCS. Springer, 2008. Google ScholarDigital Library
- P. Simonetto, P. Y. Koenig, F. Zaidi, D. Archambault, F. Gilbert, T. T. Phan-Quang, M. Mathiaut, A. Lambert, J. Dubois, R. Sicre, M. Brulin, R. Vieux, and G. Melançon. Solving the traffic and flitter challenges with tulip. In IEEE Proc. on Visual Analytics Science and Technology, pages 247--248, 2009.Google ScholarCross Ref
- L. Singh, M. Beard, L. Getoor, and M. Blake. Visual mining of multimodal social networks at different abstraction levels. In IV '07. 11th International Conference, pages 672--679, 2007. Google ScholarDigital Library
- C. Ware. Information Visualization: Perception for Design. Morgan Kaufmann, 2004. Google ScholarDigital Library
- S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994.Google ScholarCross Ref
Index Terms
- Interactive searching and visualization of patterns in attributed graphs
Recommendations
Fast edge searching and fast searching on graphs
Given a graph G=(V,E) in which a fugitive hides on vertices or along edges, graph searching problems are usually to find the minimum number of searchers required to capture the fugitive. In this paper, we consider the problem of finding the minimum ...
Supporting the Discovery of Relevant Topological Patterns in Attributed Graphs
ICDMW '12: Proceedings of the 2012 IEEE 12th International Conference on Data Mining WorkshopsWe propose TopGraphVisualizer, a tool to support the discovery of relevant topological patterns in attributed graphs. It relies on a new pattern detection method that crucially needs for sophisticated post processing and visualization. A topological ...
Connected graph searching in chordal graphs
Graph searching was introduced by Parson [T. Parson, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426-441]: given a ''contaminated'' graph G (e.g., a network containing a ...
Comments