Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Knowledge and Information Systems
Erschienen in: Knowledge and Information Systems 2/2017

02.05.2016 | Regular Paper

Attributed graph mining in the presence of automorphism

verfasst von: Claude Pasquier, Frédéric Flouvat, Jérémy Sanhes, Nazha Selmaoui-Folcher

Erschienen in: Knowledge and Information Systems | Ausgabe 2/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Attributed directed graphs are directed graphs in which nodes are associated with sets of attributes. Many data from the real world can be naturally represented by this type of structure, but few algorithms are able to directly handle these complex graphs. Mining attributed graphs is a difficult task because it requires combining the exploration of the graph structure with the identification of frequent itemsets. In addition, due to the combinatorics on itemsets, subgraph isomorphisms (which have a significant impact on performances) are much more numerous than in labeled graphs. In this paper, we present a new data mining method that can extract frequent patterns from one or more directed attributed graphs. We show how to reduce the combinatorial explosion induced by subgraph isomorphisms thanks to an appropriate processing of automorphic patterns.
Vorheriger Artikel DIDES: a fast and effective sampling for clustering algorithm
Nächster Artikel Visual domain adaptation via transfer feature learning

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
Graphs with labeled edges can always be transformed into graphs with only labels on nodes (using, e.g., the method proposed by [11]). For this reason, we only consider attributed nodes in our study.
 
Literatur
1.
Agrawal R, Imieliński T, Swami A (1993) Mining association rules between sets of items in large databases. SIGMOD Rec 22(2):207–216CrossRef
2.
Agrawal R, Srikant R (1995) Mining sequential patterns. In: ICDE’95, pp 3–14
3.
Ayres J, Flannick J, Gehrke J, Yiu T (2002) Sequential pattern mining using a bitmap representation. In: KDD’02, pp 429–435
4.
Borgelt C (2007) Canonical forms for frequent graph mining. In: Decker R, Lenz H-J (eds) Advances in data analysis. Springer, Berlin, pp 337–349CrossRef
5.
Borgelt C, Berthold M (2002) Mining molecular fragments: finding relevant substructures of molecules. In: ICDM’02, pp 51–58
6.
Bringmann B, Nijssen S (2008) What is frequent in a single graph?. In: PAKDD’08, pp 858–863
7.
Chi Y, Yang Y, Xia Y, Muntz RR (2004) Cmtreeminer: mining both closed and maximal frequent subtrees. In: PAKDD’04, pp 63–73
8.
Fukuzaki M, Seki M, Kashima H, Sese J (2010) Finding itemset-sharing patterns in a large itemset-associated graph. In: PAKDD’10, pp 147–159
9.
Huan J, Wang W, Prins J (2003) Efficient mining of frequent subgraphs in the presence of isomorphism. In: ICDM’05, pp 549–552
10.
Inokuchi A, Washio T, Motoda H (2000) An apriori-based algorithm for mining frequent substructures from graph data. In: PKDD’00, pp 13–23
11.
Inokuchi A, Washio T, Motoda H (2003) Complete mining of frequent patterns from graphs: mining graph data. Mach Learn 50(3):321–354CrossRefMATH
12.
Jiang C, Coenen F, Zito M (2013) A survey of frequent subgraph mining algorithms. Knowl Eng Rev 28:75–105CrossRef
13.
Johnsonbaugh R, Kalin M (1991) A graph generation software package. SIGCSE Bull 23(1):151–154CrossRef
14.
Kuramochi M, Karypis G (2001) Frequent subgraph discovery. In: ICDM’01, pp 313–320
15.
Kuramochi M, Karypis G (2004) An efficient algorithm for discovering frequent subgraphs. IEEE Trans Knowl Data Eng 16(9):1038–1051CrossRef
16.
Mannila H, Toivonen H (2005) Multiple uses of frequent sets and condensed representations. In: KDD’05, pp 189–194
17.
McAuley J, Leskovec J (2012) Learning to discover social circles in ego networks. Neural Inf Process Syst 25:548–556
18.
Miyoshi Y, Ozaki T, Ohkawa T (2009) Frequent pattern discovery from a single graph with quantitative itemsets. In: ICDMW’09, pp 527–532
19.
Pasquier C, Sanhes J, Flouvat F, Selmaoui-Folcher N (2015) Frequent pattern mining in attributed trees: algorithms and applications. Knowl Inf Syst 46(3):491–514CrossRef
20.
Pasquier N, Bastide Y, Taouil R, Lakhal L (1999) Discovering frequent closed itemsets for association rules. In: ICDT’99, pp 398–416
21.
Wörlein M, Meinl T, Fischer I, Philippsen M (2005) A quantitative comparison of the subgraph miners mofa, gspan, ffsm, and gaston. In: PKDD’05, pp 392–403
22.
Yan X, Han J (2002) gspan: graph-based substructure pattern mining. In: ICDM’02, pp 721–724
23.
Yan X, Han J (2003) CloseGraph: mining closed frequent graph patterns. In: KDD’03, pp 286–295
24.
Yan X, Yu PS, Han J (2004) Graph indexing: a frequent structure-based approach. In: SIGMOD conference, pp 335–346
Metadaten
Titel
Attributed graph mining in the presence of automorphism
verfasst von
Claude Pasquier
Frédéric Flouvat
Jérémy Sanhes
Nazha Selmaoui-Folcher
Publikationsdatum
02.05.2016
Verlag
Springer London
Erschienen in
Knowledge and Information Systems / Ausgabe 2/2017
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI
https://doi.org/10.1007/s10115-016-0953-9

Weitere Artikel der Ausgabe 2/2017

Knowledge and Information Systems 2/2017 Zur Ausgabe

Regular Paper

Radius-aware approximate blank node matching using signatures

Regular Paper

Visual domain adaptation via transfer feature learning

Regular Paper

Fuzzy knowledge-based token-ordering policies for bullwhip effect management in supply chains

Regular Paper

Uncovering and predicting the dynamic process of information cascades with survival model

Regular Paper

k-Degree anonymity and edge selection: improving data utility in large networks

Regular Paper

DIDES: a fast and effective sampling for clustering algorithm

Premium Partner

    Bildnachweise