Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/14370
Title: All normalized anti-monotonic overlap graph measures are bounded
Authors: Calders, Toon
Ramon, Jan
VAN DYCK, Dries 
Issue Date: 2011
Publisher: SPRINGER
Source: DATA MINING AND KNOWLEDGE DISCOVERY, 23 (3), p. 503-548
Abstract: In graph mining, a frequency measure for graphs 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 frequent subgraphs have to be found in one graph. Vanetik et al. (Data Min Knowl Disc 13(2):243-260, 2006) already gave sufficient and necessary conditions for anti-monotonicity of graph measures depending only on the edge-overlaps between the instances 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. As a secondary contribution, we prove that the popular maximum independent set measure assigns the minimal possible normalized frequency and we introduce a new measure based on the minimum clique partition that assigns the maximum possible normalized frequency. In that way, we obtain that all normalized anti-monotonic overlap graph measures are bounded from above and below. We also introduce a new measure sandwiched between the former two based on the polynomial time computable Lovasz theta-function.
Notes: [Ramon, Jan] Katholieke Univ Leuven, Kortrijk, Belgium. [Calders, Toon] Eindhoven Univ Technol, NL-5600 MB Eindhoven, Netherlands. [Van Dyck, Dries] Transnatl Univ Limburg, Hasselt Univ, Diepenbeek, Belgium.
Keywords: Computer Science, Artificial Intelligence; Computer Science, Information Systems;Graph mining; Large network setting; Support measure; Anti-monotonicity; Morphism reductions
Document URI: http://hdl.handle.net/1942/14370
ISSN: 1384-5810
e-ISSN: 1573-756X
DOI: 10.1007/s10618-011-0217-y
ISI #: 000293711000005
Category: A1
Type: Journal Contribution
Validations: ecoom 2012
Appears in Collections:Research publications

Show full item record

SCOPUSTM   
Citations

12
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

7
checked on May 21, 2022

Page view(s)

46
checked on May 20, 2022

Google ScholarTM

Check

Altmetric


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