Título
Representative frequent approximate subgraph mining on multi-graph collections
Autor
NIUSVEL ACOSTA MENDOZA
Colaborador
JESUS ARIEL CARRAZCO OCHOA (Asesor de tesis)
ANDRÉS GAGO ALONSO (Asesor de tesis)
Nivel de Acceso
Acceso Abierto
Materias
Mining of frequent graphs - (MINERÍA DE GRAFOS FRECUENTES) Correspondence between multi-graphs - (CORRESPONDENCIA ENTRE MULTI-GRAFOS) Representative frequent subgraphs - (SUBGRAFOS FRECUENTES REPRESENTATIVOS) INGENIERÍA Y TECNOLOGÍA - (CTI) CIENCIAS TECNOLÓGICAS - (CTI) TECNOLOGÍA DE LOS ORDENADORES - (CTI) LENGUAJES DE PROGRAMACIÓN - (CTI)
Resumen o descripción
Nowadays, there has been an increase in the use of frequent approximate subgraph (FAS)
mining for different real-world applications such as image classification, social network analysis and natural language processing, among others. In several of these applications, in the last years, multi-graphs have been used to model data, because, in the real-world, commonly there are more than one relation (edge) between the entities represented as vertices. However, the reported FAS miners have been designed to work with simple-graphs. Therefore, in order to solve the problem of mining FASs from multi-graph collections, we explore two alternatives in this research: (1) transforming the multi-graphs into simple-graphs and the FASs are obtained by applying conventional FAS miners over the transformed simple-graph collection, and (2) proposing algorithms for mining FAS directly from multi-graph collections. Following the first alternative, a method, called allEdges, based on graph transformations for mining all FASs on multi-graph collections by means of applying simple-graph FAS miners was proposed. Later, for speeding up the mining process, an alternative method, called onlyMulti, based on graph transformation for mining some FASs over multi-graph collections was proposed. Despite the fact that both allEdges and onlyMulti allow using simple-graph FAS miners for mining multi-graph FASs, the graph transformation processes increase the size of the graph collection and therefore, the mining process cost is increased. Thus, an algorithm, called MgVEAM, for mining all FASs directly over multi-graph collections without graph transformations was proposed. After, in order to accelerate the mining process, another algorithm, called AMgMiner, for directly mining all multi-graph FASs was proposed. AMgMiner is faster than MgVEAM, but the former requires more memory than the later. All the proposed methods and algorithms were evaluated and compared by using di_erent multi-graph datasets. The large number of mined FASs is one of the fundamental drawbacks of FAS mining, which makes difficult the further use of the mined FASs. Therefore, in order to mine only a subset of representative FASs from multi-graph collections, we proposed two algorithms; one for mining generalized closed FASs and another for mining clique FASs.
Experiments on different databases were carried out to show the performance of our
proposals.
Actualmente existe un incremento del uso de la minería de subgrafos frecuentes aproximados en diferentes aplicaciones, por ejemplo clasificación de imágenes, análisis de redes sociales y procesamiento del lenguaje natural, entre otros. En varias de estas aplicaciones, en los últimos años, los multi-grafos han sido utilizados para modelar los datos, porque en la realidad, comúnmente existen más de una relación (arista) entre las entidades representadas como vértices. Sin embargo, los algoritmos reportados para la minería de este tipo de patrones han sido diseñados para trabajar con grafos simples. Por tanto, con el objetivo de solucionar el problema de minar subgrafos frecuentes aproximados en colecciones de multi-grafos, en esta tesis se exploran dos alternativas: (1) transformar los multi-grafos en grafos simples, obteniendo los subgrafos frecuentes aproximados al aplicar algoritmos convencionales sobre los grafos simples transformados, y (2) proponer algoritmos para la minería de subgrafos frecuentes aproximados directamente sobre colecciones de multi-grafos. Siguiendo la primera alternativa se propone un método, llamado allEdges, que se basa en transformaciones de grafos para la minería de todos los subgrafos frecuentes aproximados en colecciones de multi-grafos mediante la aplicación de algoritmos que minan grafos simples. Luego, para acelerar el proceso de minería se propuso un método alternativo, llamado onlyMulti, el cual está basado en transformaciones de grafos para minar algunos subgrafos frecuentes aproximados en colecciones de multi-grafos. A pesar del hecho de que los métodos allEdges y onlyMulti permiten usar algoritmos que mina grafos simples para minar subgrafos frecuentes aproximados
en el contexto de multi-grafos, los procesos de transformación incrementan el tamaño de
la colección de grafos y por consiguiente se incrementa el costo del proceso de minería. Por lo que se propone un algoritmo, llamado MgVEAM, para minar todos los subgrafos frecuentes aproximados directamente de la colección de multi-grafos sin procesos de transformación de grafos. Después, con el objetivo de acelerar el proceso de minería, se propone otro algoritmo, llamado AMgMiner, para minar todos los subgrafos frecuentes aproximados directamente en colecciones de multi-grafos. AMgMiner es más rápido que MgVEAM, pero el primero requiere más memoria que el segundo.
Editor
Instituto Nacional de Astrofísica, Óptica y Electrónica
Fecha de publicación
20 de febrero de 2018
Tipo de publicación
Tesis de doctorado
Versión de la publicación
Versión aceptada
Recurso de información
Formato
application/pdf
Idioma
Inglés
Audiencia
Estudiantes
Investigadores
Público en general
Sugerencia de citación
Acosta-Mendoza N.
Repositorio Orígen
Repositorio Institucional del INAOE
Descargas
1057