Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorCalders, Toon-
dc.contributor.authorRamon, Jan-
dc.contributor.authorVAN DYCK, Dries-
dc.identifier.citationProceedings of 6th International Workshop on Mining and Learning with Graphs.-
dc.description.abstractIn 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 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. We also prove that the popular maximum independent set measure assigns the minimal possible meaningful frequency, introduce a new measure based on the minimum clique partition that assigns the maximum possible meaningful frequency and introduce a new measure sandwiched between the former two based on the poly-time computable Lovasz thetas-function.-
dc.subject.othergraph support measure, overlap graph, anti-monotinicity-
dc.titleMin, Max and PTIME Anti-Monotonic Overlap Graph Measures-
dc.typeProceedings Paper-
local.bibliographicCitation.conferencename6th International Workshop on Mining and Learning with Graphs-
local.bibliographicCitation.conferenceplaceHelsinki, Finland, July 2008-
local.type.specifiedProceedings Paper-
local.bibliographicCitation.btitleProceedings of 6th International Workshop on Mining and Learning with Graphs-
item.fulltextWith Fulltext-
item.accessRightsOpen Access-
item.contributorCalders, Toon-
item.contributorRamon, Jan-
item.contributorVAN DYCK, Dries-
item.fullcitationCalders, Toon; Ramon, Jan & VAN DYCK, Dries (2008) Min, Max and PTIME Anti-Monotonic Overlap Graph Measures. In: Proceedings of 6th International Workshop on Mining and Learning with Graphs..-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
amogm.mlg08.pdfPublished version69.11 kBAdobe PDFView/Open
Show simple item record

Page view(s)

checked on Jul 3, 2022


checked on Jul 3, 2022

Google ScholarTM


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