English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/139269
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

Approximate Matching of Neighborhood Subgraphs - An Ordered String Graph Levenshtein Method

AutorNettleton, David F.; Salas, Julian
Palabras claveEdit distance
String representation
Sub-graph matching
Tree representation
Online social networks
Fecha de publicación2016
EditorWorld Scientific Publishing
CitaciónInternational Journal of Uncertainty, Fuzziness and Knowlege-Based Systems 24: 411- 431 (2016)
ResumenGiven that exact pair-wise graph matching has a high computational cost, different representational schemes and matching methods have been devised in order to make matching more efficient. Such methods include representing the graphs as tree structures, transforming the structures into strings and then calculating the edit distance between those strings. However many coding schemes are complex and are computationally expensive. In this paper, we present a novel coding scheme for unlabeled graphs and perform some empirical experiments to evaluate its precision and cost for the matching of neighborhood subgraphs in online social networks. We call our method OSG-L (Ordered String Graph-Levenshtein). Some key advantages of the pre-processing phase are its simplicity, compactness and lower execution time. Furthermore, our method is able to match both non-isomorphisms (near matches) and isomorphisms (exact matches), also taking into account the degrees of the neighbors, which is adequate for social network graphs.
Identificadoresdoi: 10.1142/S0218488516500215
issn: 0218-4885
Aparece en las colecciones: (IIIA) Artículos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
accesoRestringido.pdf15,38 kBAdobe PDFVista previa
Mostrar el registro completo

NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.