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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
International Journal of Machine Learning and Cybernetics
Erschienen in: International Journal of Machine Learning and Cybernetics 4/2014

01.08.2014 | Original Article

EM-type method for measuring graph dissimilarity

verfasst von: Lifei Chen

Erschienen in: International Journal of Machine Learning and Cybernetics | Ausgabe 4/2014

Einloggen

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

search-config
loading …

Abstract

Graph dissimilarity (or similarity) computation is one of the key intermediate operations for intelligent information processing. In this paper, a new dissimilarity measure is proposed to gauge the pairwise structural difference between graphs through constrained graph matching. The measure is obtained as a solution to an optimization problem that we formalize by a new objective function in matrix representation, based on the adjacency matrices of graphs and binary constraints. An EM-type algorithm based on the minimum-weight bipartite graph method is proposed to optimize the matrix in polynomial time. The suitability of the proposed measure is evaluated in nearest-neighbor classification on four real-world graph datasets and on synthetic datasets.
Vorheriger Artikel Hand gesture recognition and animation for local hand motions
Nächster Artikel N-dimensional (α, β)-fuzzy H-ideals in hemirings

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 "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

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
Weitere Produktempfehlungen anzeigen
Literatur
1.
Chakrabarti D, Faloutsos C (2006) Graph mining: laws, generators, and algorithms. ACM Comput Surv 38:1–69CrossRef
2.
Chen M, Yang Q, Tang X (2007) Directed graph embedding. In: Veloso MM (ed) Proceedings of IJCAI’07, pp 2707–2712
3.
Chen L, Wang S, Yan X (2012) Centroid-based clustering for graph datasets. In: IAPR (ed) Proceedings of ICPR’12, pp 2144–2147
4.
Dosch P, Valveny E (2005) Report on the second symbol recognition contest. In: Liu W, Llados J (ed) GREC 2005, LNCS 3926, pp 381–397
5.
Dhurandhar A, Dobra A (2013) Probabilistic characterization of nearest neighbor classifier. Int J Mach Learn Cybern 4(4):259–272CrossRef
6.
Hlaoui A, Wang S (2006) Median graph computation for graph clustering. Soft Comput 10:47–53CrossRef
7.
8.
Justice D, Hero A (2006) A binary linear programming formulation of the graph edit distance. IEEE T Pattern Anal Mach Intell 28:1200–1214CrossRef
9.
Kazius J, McGuire R, Bursi R (2005) Derivation and validation of toxicophores for mutagenicity prediction. J Med Chem 48:312–320CrossRef
10.
Luo B, Wilson RC, Hancock ER (2003) Spectral embedding of graphs. Pattern Recogn 36:2213–2230CrossRefMATH
11.
12.
Nikolic M (2012) Measuring similarity of graph nodes by neighbor matching. Intell Data Anal 16(6):865–878
13.
Reforgiato D, Gutierrez R, Shasha D (2008) GraphClust: A method for clustering database of graphs. J Inform Knowl 7:231–241CrossRef
14.
Riesen K, Bunke H (2008) IAM graph database repository for graph based pattern recognition and machine learning. In: da Vitora Lobo N et al (ed) SSPR&SPR 2008, LNCS 5342, pp 287–297
15.
Riesen K, Bunke H (2009) Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput 27:950–959CrossRef
16.
Umeyama S (1988) An eigendecomposition approach to weighted graph matching problems. IEEE T Pattern Anal Mach Intell 10:695–703CrossRefMATH
17.
Washio T, Motoda H (2003) State of the art of graph-based data mining. ACM SIGKDD Explor Newsl 5:59–68CrossRef
18.
Weskamp N, Hullermeier E, Kuhn D, Klebe G (2007) Multiple graph alignment for the structural analysis of protein active sites. IEEE ACM T Comput Biol Bioinform 4:310–320
19.
Zeng Z, Tung AKH, Wang J, Feng J, Zhou L (2009) Comparing stars: on approximating graph edit distance. Proc VLDB Endow 2:25–36CrossRef
Metadaten
Titel
EM-type method for measuring graph dissimilarity
verfasst von
Lifei Chen
Publikationsdatum
01.08.2014
Verlag
Springer Berlin Heidelberg
Erschienen in
International Journal of Machine Learning and Cybernetics / Ausgabe 4/2014
Print ISSN: 1868-8071
Elektronische ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-013-0210-4

Weitere Artikel der Ausgabe 4/2014

International Journal of Machine Learning and Cybernetics 4/2014 Zur Ausgabe

Original Article

N-dimensional (α, β)-fuzzy H-ideals in hemirings

Original Article

Hand gesture recognition and animation for local hand motions

Original Article

Automatic playlist generation by applying tabu search

Original Article

A new finger-knuckle-print ROI extraction method based on probabilistic region growing algorithm

Original Article

Hierarchical classification with a topic taxonomy via LDA

Original Article

A nonlinear least squares quasi-Newton strategy for LP-SVR hyper-parameters selection

Neuer Inhalt

    Bildnachweise