A sub-graph matching method based on calibration of characteristics of topological footprint
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Nettleton, David F.
- dc.contributor.author Dries, Anton
- dc.date.accessioned 2020-03-09T17:06:45Z
- dc.date.available 2020-03-09T17:06:45Z
- dc.date.issued 2015
- dc.description.abstract Approximate sub-graph matching is important in many graph data mining fields. At present, current solutions can be difficult to implement, have an expensive pre-processing phase, or only work for given types of graph. In this paper a novel generic approach is presented which addresses these issues. An approximate sub-graph matcher (A-SGM) calculates the distance between the topological characteristics (footprint) of the sub-graphs to be matched, applying a weighting to the different sub-graph characteristics and those of neighbor nodes. The weights are calibrated for each dataset with a simulated annealing process using sample sets of graph nodes to reduce computational cost, and an exact isomorphism matcher as a fitness function which takes into account how well the match maintains the neighboring node degree distributions. Benchmarking is performed on several state of the art methods and real and synthetic graph datasets to evaluate the precision, recall and computational cost. The results show that the A-SGM is competitive with state of the art methods in terms of precision, recall and execution time.en
- dc.format.mimetype application/pdf
- dc.identifier.citation Nettleton DF, Dries A. A sub-graph matching method based on calibration of characteristics of topological footprint. Int J Comput Appl. 2015 Nov;130(10):29-38. DOI: 10.5120/ijca2015907098
- dc.identifier.doi http://dx.doi.org/10.5120/ijca2015907098
- dc.identifier.issn 0975-8887
- dc.identifier.uri http://hdl.handle.net/10230/43840
- dc.language.iso eng
- dc.publisher Foundation of Computer Science
- dc.relation.ispartof International journal of computer applications. 2015 Nov;130(10):29-38
- dc.rights © International Journal of Computer Applications (0975 – 8887) Volume 130 – No. 10, Nov 2015 http://dx.doi.org/10.5120/ijca2015907098
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.subject.keyword Graph Matchingen
- dc.subject.keyword Topologyen
- dc.subject.keyword Graph characteristicsen
- dc.subject.keyword Weight calibrationen
- dc.subject.keyword Simulated annealingen
- dc.subject.keyword Graph queries
- dc.title A sub-graph matching method based on calibration of characteristics of topological footprint
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/acceptedVersion