DSpace Repository

Descubrimiento eficiente de subgrafos densos en superposición y su aplicación para la compresión de grafos

Show simple item record

dc.contributor.advisor Hernández Rivas, Cecilia , supervisora de grado
dc.contributor.author Mella Ibáñez, Carlos Felipe
dc.date.accessioned 2017-04-10T13:50:49Z
dc.date.accessioned 2019-12-16T16:39:29Z
dc.date.available 2017-04-10T13:50:49Z
dc.date.available 2019-12-16T16:39:29Z
dc.date.issued 2016
dc.identifier.other 227485
dc.identifier.uri http://repositorio.udec.cl/jspui/handle/11594/2081
dc.description Ingeniero Civil Informatico Universidad de Concepción 2016 es
dc.description.abstract La exploración de algoritmos eficientes para descubrir patrones en grafos es un tema que ha recibido un renovado interés en los últimos años, debido al rápido crecimiento que se ha dado en grafos vistos en ámbitos como las redes sociales, la web, estudio de interacciones entre proteínas y muchos otros. El procesar estos grafos muy grandes es un desafío: los altos requerimientos de memoria principal pueden hacer infactible la ejecución directa de algoritmos de búsqueda de patrones, mientras que la alta complejidad computacional de algunos de estos algoritmos puede volver impráctica su aplicación. Para tratar las limitaciones de espacio y procesamiento, la comunidad científica ha propuesto, entre otras técnicas, el uso de representaciones compactas para grafos que soportan la ejecución de algunas operaciones básicas de consulta directamente sobre la estructura comprimida; a partir de estas operaciones básicas es posible implementar algoritmos clásicos de grafos. Esto permite relajar los requerimientos de memoria principal para su ejecución. En particular, en grafos de la web y redes sociales, Hernández y Navarro propusieron una estructura compacta para grafos basada en subgrafos densos que incluye una combinación de cliques y bicliques, que son descubiertos utilizando heurísticas eficientes. Estos subgrafos no tienen superposición de aristas entre ellos. Esta memoria de título presenta una propuesta para expandir las herramientas de descubrimiento de Hernández y Navarro para incluir subgrafos con superposición entre ellos. Los resultados obtenidos usando grafos reales de la web y redes sociales muestran un incremento del número, tamaño promedio y cobertura en el grafo de los subgrafos densos con respecto a los resultados obtenidos con las herramientas de Hernández y Navarro. El segundo objetivo principal de este trabajo es el diseño e implementación de una nueva representación compacta para grafos basada en subgrafos densos con superposición. Dos representaciones compactas fueron creadas: una construida a partir de los cliques maximales de un grafo no dirigido, y una segunda para grafos dirigidos y no dirigidos a partir de sus subgrafos densos maximales. En los resultados obtenidos destaca la obtención de una mejor tasa de compresión que las técnicas de referencia actuales con el grafo social no dirigido dblp-2011. es
dc.language.iso es es
dc.publisher Universidad de Concepción . Facultad de Ingeniería. Departamento de Ingeniería Informática y Ciencias de la Computación es
dc.subject Gráficos por Computador es
dc.subject Teoría de Grafos es
dc.subject Algoritmos Computacionales es
dc.subject Heurística es
dc.title Descubrimiento eficiente de subgrafos densos en superposición y su aplicación para la compresión de grafos es
dc.type Tesis es


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account