Tampere University of Technology

TUTCRIS Research Portal

Classification of large graphs by a local tree decomposition

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


Original languageEnglish
Title of host publicationProceedings of the 2005 International Conference on Data Mining, DMIN'05
Number of pages8
Publication statusPublished - 2005
Externally publishedYes
Publication typeA4 Article in a conference publication
Event2005 International Conference on Data Mining, DMIN'05 - Las Vegas, NV, United States
Duration: 20 Jun 200523 Jun 2005


Conference2005 International Conference on Data Mining, DMIN'05
CountryUnited States
CityLas Vegas, NV


We present a binary graph classifier (BGC) which allows to classify large, unweighted, undirected graphs. This classifier is based on a local decomposition of the graph for each node in generalized trees. The obtained trees, forming the tree set of the graph, are then pairwise compared by a generalized tree-similarity-algorithm (GTSA) and the resulting similarity scores determine a characteristic similarity distribution of the graph. Classification in this context is defined as mutual consistency for all pure and mixed tree sets and their resulting similarity distributions in a graph class. We demonstrate the application of this method to an artificially generated data set and for data from microarray experiments of cervical cancer.

ASJC Scopus subject areas