www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
URI: http://hdl.handle.net/1942/9441
Link to publication: http://doi.ieeecomputersociety.org/10.1109/ICDM.2008.114
DOI: 10.1109/ICDM.2008.114
ISI #: 000264173600008
ISBN: 978-0-7695-3502-9
ISSN: 1550-4786
Category: C1
Type: Proceedings Paper
Validation: ecoom, 2010
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A259.4 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.