Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9440
Full metadata record
DC FieldValueLanguage
dc.contributor.authorCalders, Toon-
dc.contributor.authorRamon, Jan-
dc.contributor.authorVAN DYCK, Dries-
dc.date.accessioned2009-04-08T14:41:30Z-
dc.date.issued2008-
dc.identifier.citationProceedings of 6th International Workshop on Mining and Learning with Graphs.-
dc.identifier.urihttp://hdl.handle.net/1942/9440-
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.language.isoen-
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.format.pages3-
local.bibliographicCitation.jcatC2-
local.type.refereedRefereed-
local.type.specifiedProceedings Paper-
dc.bibliographicCitation.oldjcat-
dc.identifier.urlhttp://www.cis.hut.fi/MLG08/papers/session1/paper20.pdf-
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)

16
checked on Jul 3, 2022

Download(s)

6
checked on Jul 3, 2022

Google ScholarTM

Check


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