Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/9440
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Calders, Toon | - |
dc.contributor.author | Ramon, Jan | - |
dc.contributor.author | VAN DYCK, Dries | - |
dc.date.accessioned | 2009-04-08T14:41:30Z | - |
dc.date.issued | 2008 | - |
dc.identifier.citation | Proceedings of 6th International Workshop on Mining and Learning with Graphs. | - |
dc.identifier.uri | http://hdl.handle.net/1942/9440 | - |
dc.description.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 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.iso | en | - |
dc.subject.other | graph support measure, overlap graph, anti-monotinicity | - |
dc.title | Min, Max and PTIME Anti-Monotonic Overlap Graph Measures | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.conferencename | 6th International Workshop on Mining and Learning with Graphs | - |
local.bibliographicCitation.conferenceplace | Helsinki, Finland, July 2008 | - |
local.format.pages | 3 | - |
local.bibliographicCitation.jcat | C2 | - |
local.type.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
dc.bibliographicCitation.oldjcat | - | |
dc.identifier.url | http://www.cis.hut.fi/MLG08/papers/session1/paper20.pdf | - |
local.bibliographicCitation.btitle | Proceedings of 6th International Workshop on Mining and Learning with Graphs | - |
item.fullcitation | Calders, 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.. | - |
item.fulltext | With Fulltext | - |
item.contributor | Calders, Toon | - |
item.contributor | Ramon, Jan | - |
item.contributor | VAN DYCK, Dries | - |
item.accessRights | Open Access | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
amogm.mlg08.pdf | Published version | 69.11 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.