Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/9441
Title: | Anti-Monotonic Overlap-Graph Support Measures | Authors: | Calders, Toon Ramon, Jan VAN DYCK, Dries |
Issue Date: | 2008 | Publisher: | IEEE COMPUTER SOC | Source: | Giannotti, F. (Ed.) ICDM 2008: EIGHTH IEEE INTERNATIONAL CONFERENCE ON DATA MINING, PROCEEDINGS. p. 73-82. | Series/Report: | IEEE International Conference on Data Mining | Abstract: | In graph mining, a frequency measure is anti-monotonic if the frequency of a pattern never exceeds the frequency of a subpattern. The efficiency and correctness of most graph pattern miners relies critically on this property. We study the case where the dataset is a single graph. Vanetik, Gudes and Shimony already gave sufficient and necessary conditions for anti-monotonicity of measures depending only on the edge-overlaps between the intances of the pattern in a labeled graph. We extend these results to homomorphisms, isomorphisms and homeomorphisms on both labeled and unlabeled, directed and undirected graphs, for vertex and edge overlap. We show a set of reductions between the different morphisms that preserve overlap. | Keywords: | graph support measure, overlap graph, anti-monotinicity | Document URI: | http://hdl.handle.net/1942/9441 | Link to publication/dataset: | http://doi.ieeecomputersociety.org/10.1109/ICDM.2008.114 | ISBN: | 978-0-7695-3502-9 | DOI: | 10.1109/ICDM.2008.114 | ISI #: | 000264173600008 | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2010 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
icdm08.pdf | 259.4 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.