Support measures for graph data

The concept of support is central to data mining. While the definition of support in transaction databases is intuitive and simple, that is not the case in graph datasets and databases. Most mining algorithms require the support of a pattern to be no greater than that of its subpatterns, a property...

Full description

Saved in:
Bibliographic Details
Published in:Data mining and knowledge discovery 2006-09, Vol.13 (2), p.243-260
Main Authors: Vanetik, N., Shimony, S. E., Gudes, E.
Format: Article
Language:English
Subjects:
Algorithms
Data mining
Datasets
Graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c272t-81b451256060adc8fe9761f6b6e1b28375683cc6d8d5fb4ee48930976c0073b93
cites cdi_FETCH-LOGICAL-c272t-81b451256060adc8fe9761f6b6e1b28375683cc6d8d5fb4ee48930976c0073b93
container_end_page 260
container_issue 2
container_start_page 243
container_title Data mining and knowledge discovery
container_volume 13
creator Vanetik, N.
Shimony, S. E.
Gudes, E.
description The concept of support is central to data mining. While the definition of support in transaction databases is intuitive and simple, that is not the case in graph datasets and databases. Most mining algorithms require the support of a pattern to be no greater than that of its subpatterns, a property called anti-monotonicity, or admissibility. This paper examines the requirements for admissibility of a support measure. Support measures for mining graphs are usually based on the notion of an instance graph---a graph representing all the instances of the pattern in a database and their intersection properties. Necessary and sufficient conditions for support measure admissibility, based on operations on instance graphs, are developed and proved. The sufficient conditions are used to prove admissibility of one support measure--the size of the independent set in the instance graph. Conversely, the necessary conditions are used to quickly show that some other support measures, such as weighted count of instances, are not admissible.
doi_str_mv 10.1007/s10618-006-0044-8
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_230103676</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1124428231</sourcerecordid><originalsourceid>FETCH-LOGICAL-c272t-81b451256060adc8fe9761f6b6e1b28375683cc6d8d5fb4ee48930976c0073b93</originalsourceid><addsrcrecordid>eNotkE1LxDAQhoMouK7-AE8W79GZJpmkR1n8ggUPu4K3kKaJuri2Ju3Bf2-WehhmDg_vvDyMXSLcIIC-zQiEhgNQGSm5OWILVFpwrejtuNzCSK4Mwik7y3kHAKoWsGBXm2kY-jRW--DylEKuYp-q9-SGj6pzoztnJ9F95XDxv5fs9eF-u3ri65fH59Xdmvta1yM32EqFtSIgcJ03MTSaMFJLAdvaiNLCCO-pM52KrQxBmkZAYXwpL9pGLNn1nDuk_mcKebS7fkrf5aUtPREEaSoQzpBPfc4pRDukz71LvxbBHjTYWYMtGuxBgzXiD2r9TXg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>230103676</pqid></control><display><type>article</type><title>Support measures for graph data</title><source>ABI/INFORM global</source><source>Springer Nature</source><creator>Vanetik, N. ; Shimony, S. E. ; Gudes, E.</creator><creatorcontrib>Vanetik, N. ; Shimony, S. E. ; Gudes, E.</creatorcontrib><description>The concept of support is central to data mining. While the definition of support in transaction databases is intuitive and simple, that is not the case in graph datasets and databases. Most mining algorithms require the support of a pattern to be no greater than that of its subpatterns, a property called anti-monotonicity, or admissibility. This paper examines the requirements for admissibility of a support measure. Support measures for mining graphs are usually based on the notion of an instance graph---a graph representing all the instances of the pattern in a database and their intersection properties. Necessary and sufficient conditions for support measure admissibility, based on operations on instance graphs, are developed and proved. The sufficient conditions are used to prove admissibility of one support measure--the size of the independent set in the instance graph. Conversely, the necessary conditions are used to quickly show that some other support measures, such as weighted count of instances, are not admissible.</description><identifier>ISSN: 1384-5810</identifier><identifier>EISSN: 1573-756X</identifier><identifier>DOI: 10.1007/s10618-006-0044-8</identifier><language>eng</language><publisher>New York: Springer Nature B.V</publisher><subject>Algorithms ; Data mining ; Datasets ; Graphs</subject><ispartof>Data mining and knowledge discovery, 2006-09, Vol.13 (2), p.243-260</ispartof><rights>Springer Science+Business Media, LLC 2006</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c272t-81b451256060adc8fe9761f6b6e1b28375683cc6d8d5fb4ee48930976c0073b93</citedby><cites>FETCH-LOGICAL-c272t-81b451256060adc8fe9761f6b6e1b28375683cc6d8d5fb4ee48930976c0073b93</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/230103676/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/230103676?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11688,27924,27925,36060,44363,74895</link.rule.ids></links><search><creatorcontrib>Vanetik, N.</creatorcontrib><creatorcontrib>Shimony, S. E.</creatorcontrib><creatorcontrib>Gudes, E.</creatorcontrib><title>Support measures for graph data</title><title>Data mining and knowledge discovery</title><description>The concept of support is central to data mining. While the definition of support in transaction databases is intuitive and simple, that is not the case in graph datasets and databases. Most mining algorithms require the support of a pattern to be no greater than that of its subpatterns, a property called anti-monotonicity, or admissibility. This paper examines the requirements for admissibility of a support measure. Support measures for mining graphs are usually based on the notion of an instance graph---a graph representing all the instances of the pattern in a database and their intersection properties. Necessary and sufficient conditions for support measure admissibility, based on operations on instance graphs, are developed and proved. The sufficient conditions are used to prove admissibility of one support measure--the size of the independent set in the instance graph. Conversely, the necessary conditions are used to quickly show that some other support measures, such as weighted count of instances, are not admissible.</description><subject>Algorithms</subject><subject>Data mining</subject><subject>Datasets</subject><subject>Graphs</subject><issn>1384-5810</issn><issn>1573-756X</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2006</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNotkE1LxDAQhoMouK7-AE8W79GZJpmkR1n8ggUPu4K3kKaJuri2Ju3Bf2-WehhmDg_vvDyMXSLcIIC-zQiEhgNQGSm5OWILVFpwrejtuNzCSK4Mwik7y3kHAKoWsGBXm2kY-jRW--DylEKuYp-q9-SGj6pzoztnJ9F95XDxv5fs9eF-u3ri65fH59Xdmvta1yM32EqFtSIgcJ03MTSaMFJLAdvaiNLCCO-pM52KrQxBmkZAYXwpL9pGLNn1nDuk_mcKebS7fkrf5aUtPREEaSoQzpBPfc4pRDukz71LvxbBHjTYWYMtGuxBgzXiD2r9TXg</recordid><startdate>200609</startdate><enddate>200609</enddate><creator>Vanetik, N.</creator><creator>Shimony, S. E.</creator><creator>Gudes, E.</creator><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>8G5</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2O</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>Q9U</scope></search><sort><creationdate>200609</creationdate><title>Support measures for graph data</title><author>Vanetik, N. ; Shimony, S. E. ; Gudes, E.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c272t-81b451256060adc8fe9761f6b6e1b28375683cc6d8d5fb4ee48930976c0073b93</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2006</creationdate><topic>Algorithms</topic><topic>Data mining</topic><topic>Datasets</topic><topic>Graphs</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Vanetik, N.</creatorcontrib><creatorcontrib>Shimony, S. E.</creatorcontrib><creatorcontrib>Gudes, E.</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Research Library (Alumni Edition)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer science database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM global</collection><collection>Computing Database</collection><collection>ProQuest research library</collection><collection>Research Library (Corporate)</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central Basic</collection><jtitle>Data mining and knowledge discovery</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Vanetik, N.</au><au>Shimony, S. E.</au><au>Gudes, E.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Support measures for graph data</atitle><jtitle>Data mining and knowledge discovery</jtitle><date>2006-09</date><risdate>2006</risdate><volume>13</volume><issue>2</issue><spage>243</spage><epage>260</epage><pages>243-260</pages><issn>1384-5810</issn><eissn>1573-756X</eissn><abstract>The concept of support is central to data mining. While the definition of support in transaction databases is intuitive and simple, that is not the case in graph datasets and databases. Most mining algorithms require the support of a pattern to be no greater than that of its subpatterns, a property called anti-monotonicity, or admissibility. This paper examines the requirements for admissibility of a support measure. Support measures for mining graphs are usually based on the notion of an instance graph---a graph representing all the instances of the pattern in a database and their intersection properties. Necessary and sufficient conditions for support measure admissibility, based on operations on instance graphs, are developed and proved. The sufficient conditions are used to prove admissibility of one support measure--the size of the independent set in the instance graph. Conversely, the necessary conditions are used to quickly show that some other support measures, such as weighted count of instances, are not admissible.</abstract><cop>New York</cop><pub>Springer Nature B.V</pub><doi>10.1007/s10618-006-0044-8</doi><tpages>18</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1384-5810
ispartof Data mining and knowledge discovery, 2006-09, Vol.13 (2), p.243-260
issn 1384-5810
1573-756X
language eng
recordid cdi_proquest_journals_230103676
source ABI/INFORM global; Springer Nature
subjects Algorithms
Data mining
Datasets
Graphs
title Support measures for graph data
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-28T06%3A44%3A50IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Support%20measures%20for%20graph%20data&rft.jtitle=Data%20mining%20and%20knowledge%20discovery&rft.au=Vanetik,%20N.&rft.date=2006-09&rft.volume=13&rft.issue=2&rft.spage=243&rft.epage=260&rft.pages=243-260&rft.issn=1384-5810&rft.eissn=1573-756X&rft_id=info:doi/10.1007/s10618-006-0044-8&rft_dat=%3Cproquest_cross%3E1124428231%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c272t-81b451256060adc8fe9761f6b6e1b28375683cc6d8d5fb4ee48930976c0073b93%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=230103676&rft_id=info:pmid/&rfr_iscdi=true