Abstract
Given a set of graphs, the median graph has been theoretically presented as a useful concept to infer a representative of the set. However, the computation of the median graph is a highly complex task and its practical application has been very limited up to now. In this work we present a new genetic algorithm for the median graph computation. A set of experiments on real data, where none of the existing algorithms for the median graph computation could be applied up to now due to their computational complexity, show that we obtain good approximations of the median graph. Finally, we use the median graph in a real nearest neighbour classification showing that it leaves the box of the only-theoretical concepts and demonstrating, from a practical point of view, that can be a useful tool to represent a set of graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Jiang, X., Münger, A., Bunke, H.: On median graphs: Properties, algorithms, and applications. IEEE Trans. Pattern Anal. Mach. Intell. 23(10), 1144–1151 (2001)
Hlaoui, A., Wang, S.: Median graph computation for graph clustering. Soft Comput. 10(1), 47–53 (2006)
Ferrer, M.: Theory and algorithms on the median graph. application to graph-based classification and clustering. PhD Thesis, Universitat Autònoma de Barcelona (2008)
Münger, A.: Synthesis of prototype graphs from sample graphs. Diploma Thesis, University of Bern (1998) (in German)
White, D., Wilson, R.C.: Mixing spectral representations of graphs. In: 18th International Conference on Pattern Recognition (ICPR 2006), Hong Kong, China, August 20-24, 2006, pp. 140–144. IEEE Computer Society, Los Alamitos (2006)
Bunke, H., Allerman, G.: Inexact graph matching for structural pattern recognition. Pattern Recognition Letters 1(4), 245–253 (1983)
Sanfeliu, A., Fu, K.: A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man and Cybernetics 13(3), 353–362 (1983)
Bunke, H.: On a relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters 18(8), 689–694 (1997)
Mitchel, M.: An Introduction to Genetic Algorithms. MIT Press, Cambridge (1996)
Kandel, A., Bunke, H., Last, M.: Applied Graph Theory in Computer Vision and Pattern Recognition. Series in Computational Intelligence. Springer, Berlin (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ferrer, M., Valveny, E., Serratosa, F. (2009). Median Graph Computation by Means of a Genetic Approach Based on Minimum Common Supergraph and Maximum Common Subgraph. In: Araujo, H., Mendonça, A.M., Pinho, A.J., Torres, M.I. (eds) Pattern Recognition and Image Analysis. IbPRIA 2009. Lecture Notes in Computer Science, vol 5524. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02172-5_45
Download citation
DOI: https://doi.org/10.1007/978-3-642-02172-5_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02171-8
Online ISBN: 978-3-642-02172-5
eBook Packages: Computer ScienceComputer Science (R0)